我有一個大型的數據集Person列表中排隊的對象。我希望數據結構能夠有效地執行以下操作。數據結構，有恆定的時間插入，包含，刪除和獲取索引的元素
Person。Person。Person，如果存在，請將其刪除並將其放在隊列末尾。Person。對於所有這些操作，是否可能有O（1）次？ 到目前爲止，我已經提出了兩種方法，但它們並不是最優的。
ArrayList<Person> + HashMap<Person, Integer>
的HashMap存儲Person對象的索引。這給出O（n）的時間進行操作2和3（除去元件在ArrayList）
ArrayDeque<Person>/LinkedList<Person>
他們給O代表第一2點的操作（1），但爲O（n）的最後二。
在我的情況下，空間複雜度不能大於O（n）。操作4不太密集，所以我可以容忍一個稍微低效的方法來做到這一點。
任何建議，將不勝感激。提前致謝！
我假設條件3的意思是「通過某個鍵找人」（例如，它的姓氏）？我有一種強烈的感覺，你不能在O（1）中擁有所有這些要求，甚至沒有攤銷時間（這種事情會是衆所周知的）。但是你可以把它們全部放在O（log N）中。你必須從紅黑樹（C++中的std :: map，我相信這是Java中的SortedMap）的實現開始，並修改節點結構以保持其子樹中所有節點的計數。這會給你索引O（log N）的訪問權限，以及O（log N）插入和刪除樹中的任何地方。在O（1）中通過外部散列表（紅黑樹節點）可以完成某個鍵的查找。
如果你對O（N）滿足要求4，那麼我會建議在Java中使用類似LinkedHashMap的東西，它在O（1）中給你需求1到3，而請求。 4可以通過在O（N）中迭代完成。
感謝您的建議！不知道使用紅黑樹可以通過O（log n）中的索引獲取元素。並感謝提及LinkedHashMap。我以前一定忽視過它。 – Dabiuteef
如果問題還沒有被標記java，但c++的std::deque和std::unordered_map會幾乎足矣組合。我說幾乎是因爲第三次請求是相當複雜的，我不知道如何在O(1)與其他三個結合。
std::unordered_map有它在Java中，HashMap相當，但什麼std::deque提供和ArrayDeque不，是O(1)隨機存取 - >您的申請排名第四。儘管它has already been discussed，這個功能仍然在ArrayDeque中缺失，但我認爲手動添加它並不那麼困難。畢竟，std::deque只是一個指向固定大小緩衝區的向量。
前兩個操作是O(1)在任何體面deque執行。根據第三個請求，HashMap（或std::unordered_map）會告訴您一個特定的Person是否存在於O(1)時間中，並且您可以將它放在最後，具有相同的複雜性。移除是一個問題，因爲其他元素必須移位，並且不能通過使用此策略在O(1)中獲得。
感謝您的建議。但是，在我的情況下，O（n）去除不是最佳的。無論如何，'std :: deque'上的好點。 – Dabiuteef
我不認爲你可以減少最後兩個操作的複雜性。爲了搜索列表，時間複雜度肯定是O（n），直到列表被排序。 – Karan
@Karan使用散列表可以在O（1）時間內搜索。我認爲至少有三個操作可以在O（1）中，如果不是全部的話。 – Dabiuteef