JDK中LinkedList的remove的复杂度真为O(1)？

下面是网上别人的复杂度分析
LinkedList 是链表的操作
get() 获取第几个元素，依次遍历，复杂度O(n)
add(E) 添加到末尾，复杂度O(1)
add(index, E) 添加第几个元素后，需要先查找到第几个元素，直接指针指向操作，复杂度O(n)
remove（）删除元素，直接指针指向操作，复杂度O(1)

* 我看了jdk原代码

public E remove(int index) {    checkElementIndex(index);    return unlink(node(index));}
Node<E> node(int index) {    // assert isElementIndex(index);    if (index < (size >> 1)) {        Node<E> x = first;        for (int i = 0; i < index; i++)            x = x.next;        return x;    } else {        Node<E> x = last;        for (int i = size - 1; i > index; i--)            x = x.prev;        return x;    }}
E unlink(Node<E> x) {    // assert x != null;    final E element = x.item;    final Node<E> next = x.next;    final Node<E> prev = x.prev;    if (prev == null) {        first = next;    } else {        prev.next = next;        x.prev = null;    }    if (next == null) {        last = prev;    } else {        next.prev = prev;        x.next = null;    }    x.item = null;    size--;    modCount++;    return element;}

如果是调用remove（index）或者remove（Object），他本质不还是调用node（index）找到当前node节点，再进unlink操作吗？本质不应该是O(n)的复杂度吗？

* 还有一个问题，以前学java的时候，说arraylist的应用场景用于查询多，linkedlist用于增删多，arraylist的动态数组增删需要移动后面元素的位置之外所以是O(n)，而linkedlist需要检索到当前位置才能操作，其复杂度不应该也是O(n)吗？

* 下面这段来着博客园看到的一段话：“移动耗费的时间远比LinkedList中往后寻址来的快得多，所以，除非急切需要LinkedList的Deque功能，任何情况下都应该使用ArrayList。其实，即使要用Deque，也有ArrayDeque？”事实真是这样吗？照这样看，那双向链表远不如动态数组了。空间上动态数组浪费的尾部浪费的，双链表也浪费两个节点空间记录前后指针，时间上除了在头节点增删之外的优势，其他一无是处了吗？

慕UI4021841 2020-09-02

源自：动态数据结构基础：链表 1-5 从链表中删除元素

收起

2回答

liuyubobobo 回答被采纳获得+3积分 2020-09-02 16:41:28

JDK 中的 remove(index) 是 O(n) 的算法。

我们可以很轻易用下面的例子测试出来：

LinkedList<Integer> list = new LinkedList<>();
for(int i = 0; i < 10000; i ++) list.add(0);
long start = System.nanoTime();
while(!list.isEmpty()) list.remove(list.size() / 2);
System.out.println((System.nanoTime() - start) / 1000000000.0 + " s");

System.out.println();

list = new LinkedList<>();
for(int i = 0; i < 100000; i ++) list.add(0);
start = System.nanoTime();
while(!list.isEmpty()) list.remove(list.size() / 2);
System.out.println((System.nanoTime() - start) / 1000000000.0 + " s");

在上面的代码中，我先用一个 LinkedList，其中放了 10000 个元素，然后每次删除中间的元素，直到链表为空；

再将数据规模扩大十倍，其中放了 100000 个元素，然后每次删除中间的元素，知道链表为空；

在我的环境下，测试结果是这样的：

时间差距是 100 倍。这说明，删除链表所有元素的那重for循环是 O(n^2) 的，说明其中每一个 remove 操作是 O(n) 的。

这是一个非常常用的实测算法复杂度的方式，印象中课程里有讲：）

2）

是的，LinkedList 实际上在指定位置增加元素和删除元素的复杂度都是 O(n) 的，和 ArrayList 是一样的，课程中有详细介绍。

LinkedList 只是在头尾增删元素快而已。而 ArrayList 只有在尾部增删元素快。

3）

在实战中，如果空间允许，在大多数时候使用 ArrayList 是没毛病的。对于链表的性能问题，可以参考在这一章最后我的文字小节：https://class.imooc.com/lesson/1580#mid=36139

很多时候，链表的性能确实不尽人意。在实际操作上，如果是小数据量，可以使用链表；另外，如果动态增删，比如一边遍历元素，一边增删元素，这种需求，链表更合适。

继续加油！：）

收起回答

慕UI4021841 提问者 #1

非常感谢老师！文章和课程我都看了，然后我印象中，之前学习java的时候，对ArrayList和LinkedList对比，我记得书上说的是ArrayList用于查询多的场景，LinkedList用于增删的场景。然后就产生了些疑问，看了些博客，居然看到有人分析，remove操作是O(1)级别的，然后又特意看了JDK中LinkedList的源码，确实是O(n)级别复杂度。刚才看完老师再分析，确实是这样，我还以为是我理解错了。再次感谢老师。老师说的动态增删，也让我确实理解LinkedList的应用场景。最后再次感谢老师的细心回答！：）

2020-09-03 00:10:55