目前,我正在尋找以下數據結構。擅長插入,刪除和隨機訪問的數據結構
- 快速在尾部插入。
- 快速刪除頭部。
- 能夠執行隨機訪問。
我知道ArrayBlockingQueue
擅長於(1)和(2),並且ArrayList
擅長於(3)。是否有來自標準庫/ Apache庫/ Google庫的單一數據結構,這使我能夠同時滿足所有3個要求?
目前,我正在尋找以下數據結構。擅長插入,刪除和隨機訪問的數據結構
我知道ArrayBlockingQueue
擅長於(1)和(2),並且ArrayList
擅長於(3)。是否有來自標準庫/ Apache庫/ Google庫的單一數據結構,這使我能夠同時滿足所有3個要求?
我覺得你的情況最好的數據結構是一個ringbuffer/circular buffer。環緩衝器在恆定時間內執行所有三個操作。
編輯:與ringbuffers的問題是,你應該知道在一開始許多元素是如何在最壞的情況下緩衝。但也存在動態環形緩衝區。
的原因,我認爲環形緩衝區是你想要的數據結構。一個動態緩衝區可以爲你提供O(1)分期插入,和ArrayList一樣,也是O(1)刪除(通過移動指針)。我不知道它是否在通常的Java庫中實現。 –
+1。這正是OP正在尋找的東西。我不認爲在'java.util'中實現了一個,但是使用數組編寫一個很容易。 – MAK
LinkedList的可能是合適的,如果速度是不是3.注意ArrayBlockingQueue被設計用於多線程將訪問列表環境中非常重要。 ArrayList和LinkedList不是。如果您需要從多個線程訪問它們,則必須使用Collections.synchronizedList()
來包裝它們。
LinkedHashMap是一個U需要try.It插上U最重要的。
Hash和雙鏈表數據結構的組合。
可我知道後面使用ArrayBlockingQueue –