java - 在链表中指定元素之前插入一个元素

Question

如何在链表中指定元素之前插入一个元素，使得时间复杂度为n。例如我想在 7 之前插入 100

LinkedList<Integer> linkedList = new LinkedList<>();
for (int i = 1; i <= 10; i++) {
    linkedList.add(i);
}

我可以这样做

int index = linkedList.indexOf(7);
if (-1 != index) {
    linkedList.add(index, 100);
}

但是我这样就遍历了链表两次了。其实我们只要遍历一次就可以做到这一点。那么我该怎么做呢？
PS:使用LinkedList即可

Answer 1

有一种方法可以使用ListIterator一次性完成此操作。 ListIterator 与常规 Iterator 类似，只是您可以更改迭代方向，并且可以在当前位置添加 元素；请参阅javadoc .

所以代码是这样的:

    LinkedList<SomeType> list = ...
    SomeType a, b = ..

    // Insert 'b' before the first element equal to 'a' in 'list'
    ListIterator<SomeType> iterator = list.listIterator(0);
    while (iterator.hasNext()) {
        SomeType e = iterator.next();
        if (e.equals(a)) {
            iterator.previous();  // returns 'e' again.  But the real purpose
                                  // is to reset the iteration position
                                  // so that 'next()' would return 'e' again.
            iterator.add(b);      // inserts before 'next()'.
            break;
        }
    }

ListIterator::add 操作是一个“可选”操作，但它受 LinkedList 支持。 LinkedList javadoc假设上面的内容不会导致 ConcurrentModificationException。