通过插入排序的数据结构可以获得子集的长度

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的太多，因为获得（指数）我敢打赌，需要线性时间运行。