Java:有效地插入 LinkedList

Question

我正在优化排序的 LinkedList 的实现。

要插入一个元素，我遍历列表并比较每个元素，直到我有正确的索引，然后中断循环并插入。

我想知道是否有任何其他方式可以在遍历列表的同时插入元素以将插入从 O(n + (n capped at size()/2)) 减少到 O(n) .

ListIterator 几乎是我所追求的，因为它的 add() 方法，但不幸的是，在列表中存在等于插入的元素的情况下，插入必须放在列表中它们之后。要实现这个 ListIterator 需要一个它没有的 peek()。

编辑:我有我的答案，但无论如何都会添加这个，因为很多人没有正确理解:
我正在寻找一个插入点并插入，它的总和高于 O(n)

Answer 1

您可以考虑skip list ，这是使用多个不同粒度的链表实现的。例如。第 0 级的链表包含所有项目，第 1 级平均仅链接到每个第 2 个项目，第 2 级平均仅链接到第 4 个项目，等等....搜索从顶层开始，逐渐下降到较低级别，直到它找到完全匹配。这个逻辑类似于二分查找。因此搜索和插入是一个 O(log n) 操作。

Java 类库中的一个具体示例是 ConcurrentSkipListSet 。 (尽管它在这里可能无法直接用于您)。