3

我期待在 Java 的 LinkedList 中找到它，因为链表的目的是能够在任何地方有效地插入（和删除）（假设您有某种指向要插入或删除的位置的指针）。我在 API 中没有找到任何东西。我忽略了什么吗？

我能找到的最接近的是 ListIterator 中的 add 和 remove 方法。不过，这有一些限制。特别是，根据 API，一旦底层的 LinkedList 通过 remove 被修改，其他迭代器就会变得无效。这也出现在我的测试中；以下程序导致 IllegalStateException：

import java.util.*;
public class RemoveFromLinkedList {
    public static void main(String[] args) {
        LinkedList<Integer> myList= new LinkedList<Integer>();
        for (int i = 0; i < 10; ++i) {
            myList.add(i);
        }

        ListIterator<Integer> i1 = myList.listIterator();
        ListIterator<Integer> i2 = myList.listIterator();
        for (int i = 0; i < 3; ++i) {
            i1.next();
            i2.next();
        }

        System.out.println("i1.next() should be 3: " + i1.next());
        i1.remove();
        i1.remove();

        // Exception!
        System.out.println("i2.next() should be 5: " + i2.next());
    }
}

理想情况下，我期待的是这样的：

// In my imagination only. This is the way Java actually works, afaict.

// Construct two insertion/deletion points in LinkedList myLinkedList.
myIterator = myLinkedList.iterator();
for (...) {
 myIterator.next();
}
start = myIterator.clone();
for (...) {
 myIterator.next();
}

// Later...

after = myLinkedList.spliceAfter(myIterator, someOtherLinkedList);
// start, myIterator, and after are still all valid; thus, I can do this:
// Removes everything I just spliced in, as well as some other stuff before that.
myLinkedList.remove(start, after);
// Now, myIterator is invalid, but not start, nor after.

C++ 的列表类（模板）有类似的东西。只有指向移动元素的迭代器才会失效，而不是所有的迭代器。

4

3 回答 3

2

如果您使用迭代器删除某些内容，您仍然不能继续使用相同的迭代器。这是可能的

iterator.remove();
iterator.next();
iterator.remove();
iterator.next();

据我所知，这是最接近的事情。

于 2012-10-21T22:44:49.967 回答
2

你可以用List.subList(startIndex, endIndex). 有了这个，您可以清除“源”列表中的整个范围。您还可以使用addAllat 子列表将新内容插入源列表。

如果LinkedList对此有有效的实施 - 我不知道。

于 2012-10-21T22:57:32.250 回答
1

使用 java.util.LinkedList，引用列表中的位置以便以后有效操作的唯一方法是迭代器，如果底层列表被此迭代器以外的其他东西修改，则迭代器无效。

如果您确实需要该功能，则必须超越 Java API，或者自己编写。

于 2012-10-21T23:27:39.247 回答