通過插入排序的數據結構可以獲得子集的長度

Question

我正在尋找Java中的數據結構，通過插入排序，可以快速找到並刪除特定元素並計算添加到此元素後的元素數。

LinkedHashSet理論上滿足這一要求，但接口沒有給出任何方法來例如建立一個迭代開始在指定的元素。我總是需要遍歷整個集合。

感謝您的任何建議。

編輯： OK，我簡單的執行情況（不是真的）LinkedHashSet的正是我和我的唯一的用例是目前以下，以防萬一有人有興趣。這可以改變，以包括實際遍歷元素的可能性，而不僅僅是爲了能夠計算元素的數量。可能需要一些重構，太...

public class DoublyLinkedHashSet<T> { 
private final Map<T, Entry> map; 
private Entry youngestEntry; 

public DoublyLinkedHashSet() { 
    this.map = new HashMap<T, Entry>(); 
} 

public int size() { 
    return map.size(); 
} 

public boolean contains(final T element) { 
    return map.containsKey(element); 
} 

public void add(final T element) { 
    final Entry newEntry = new Entry(); 
    final Entry entryForElement = map.put(element, newEntry); 
    boolean entryWasNotAlreadyInSet = entryForElement == null; 
    if (entryWasNotAlreadyInSet) { 
     newEntry.previousEntry = youngestEntry; 
     if (youngestEntry != null) { 
      youngestEntry.hasNext = true; 
      youngestEntry.nextEntry = newEntry; 
     } 
    } 
    youngestEntry = newEntry; 
} 

public void remove(final T element) { 
    removeEntry(element); 
} 

public int removeAndGetAmountOfEntriesAfter(final T element) { 
    Entry startEntry = removeEntry(element); 

    if (startEntry == null) { 
     return 0; 
    } 

    return countAllNextEntries(startEntry); 
} 

private int countAllNextEntries(final Entry startEntry) { 
    int amount = 0; 
    Entry currentEntry = startEntry; 
    while (currentEntry.hasNext) { 
     amount++; 
     currentEntry = currentEntry.nextEntry; 
    } 
    return amount; 
} 

private Entry removeEntry(final T element) { 
    final Entry removedEntry = map.remove(element); 

    if (removedEntry == null) { 
     return null; 
    } 

    if (hasPreviousAndNextEntry(removedEntry)) { 
     final Entry previousEntry = removedEntry.previousEntry; 
     final Entry nextEntry = removedEntry.previousEntry; 
     connect(previousEntry, nextEntry); 
    } else if (isEndOfList(removedEntry)) { 
     final Entry previousEntry = removedEntry.previousEntry; 
     resetEndTo(previousEntry); 
    } else if (isHead(removedEntry)) { 
     final Entry nextEntry = removedEntry.nextEntry; 
     resetHeadTo(nextEntry); 
    } 

    return removedEntry; 
} 

private boolean hasPreviousAndNextEntry(final Entry entry) { 
    return entry.hasPrevious && entry.hasNext; 
} 

private void connect(final Entry previousEntry, final Entry nextEntry) { 
    previousEntry.nextEntry = nextEntry; 
} 

private boolean isHead(final Entry entry) { 
    return !entry.hasPrevious && entry.hasNext; 
} 

private void resetHeadTo(final Entry entry) { 
    entry.previousEntry = null; 
    entry.hasPrevious = false; 
} 

private boolean isEndOfList(final Entry removedEntry) { 
    return removedEntry.hasPrevious && !removedEntry.hasNext; 
} 

private void resetEndTo(final Entry entry) { 
    entry.nextEntry = null; 
    entry.hasNext = false; 
    youngestEntry = entry; 
} 

private static final class Entry { 
    private boolean hasNext; 
    private boolean hasPrevious; 
    private Entry nextEntry; 
    private Entry previousEntry; 
} 
} 

Answer 1

我認爲你正在尋找一個ArrayList，或者是有一些原因，你不能使用它？

public int removeAndCount(Object o){ 
    int i = list.indexOf(o); 
    list.remove(o); 
    return list.size() - i; 
} 

Answer 2

您應該可以使用SortedSet。它提供了一個tailSet方法，應該做你需要的。

您可以按照插入順序對它們進行排序，方法是向對象中添加序列號並對其進行排序。

Answer 3

有一個散列集合，它包含你的對象，並在它們旁邊維護一個列表（這就是LinkedHashMap所做的例子，對你來說這很好，但它隱藏了它的內部列表）。如果散列集合的元素具有列表中相同元素的索引，則可以跳轉到給定索引處的列表並輕鬆遍歷其餘部分。我認爲你提到的所有操作都需要用這個解決方案運行的次線性時間，但不能更快（對〜n個元素的迭代總是需要〜n次）

使用HashMap和LinkedList的示例解決方案：

找到：HashMap.get(key)在您的列表中保存索引，key是您的元素。日誌（n）時間

刪除：LinkedList.remove(HashMap.get(key))，HashMap.remove（key），你的元素不見了。日誌（n）的時間

迭代：

for (i=HashMap.get(key); i<LinkedList.size(); i++){ 
    //etc 
} 

你可能需要解開LinkedList的太多，因爲獲得（指數）我敢打賭，需要線性時間運行。