在链接列表中的指定元素之前插入元素

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，除了你可以改变迭代的方向，你可以在当前位置add元素;见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。

Answer 2

这个怎么样：

LinkedList<Integer> linkedList = new LinkedList<>();
int addNumber = 100, beforeTheNumber = 7;
for(int i = 1; i <= 10; i++) {
    if(i == beforeTheNumber)
        linkedList.add(addNumber);
    linkedList.add(i);
}

linkedList的元素现在应该是：1,2,3,4,5,6,100,7,8,9,10。

编辑：如果要在已存在的LinkedList中插入一些值：

linkedList.add((linkedList.indexOf(beforeTheNumber) >= 0 ? linkedList.indexOf(beforeTheNumber) : linkedList.size()), addNumber);

此代码假定：

1. linkedList存在并且是LinkedList<Integer>。
2. beforeTheNumber和addNumber存在并且是整数。

如果linkedList没有beforeTheNumber，addNumber将被添加到最后。