关于链表

Question

刘老师，我之前所了解的链表java.util.LinkedList底层概念增删改是不需要遍历的，java.util.LinkedList增删改的执行效率是大于java.util.ArrayList的，可是您所实现的LinkedList增删改查都要进行循环遍历，都是O(n)，显然增删改查的执行舒服都不如ArrayList，我想问下是我之前理解的LinkedList的概念是不正确的，还是您实现的LinkedList和java.util.LinkedList的结构是有所区别的？

Answer 1

liuyubobobo 2018-05-13 01:51:16

首先，我实现的链表和java.util.LinkedList底层实现的链表确实有区别。我实现的链表是单链表；java.util.LinkedList底层是循环双链表。这一点在课程第五章最后一小节会提及。

不过即使如此，java.util.LinkedList的时间复杂度为：

查询特定元素：O(n)；

修改特定元素：由于需要先查询，再修改，时间复杂度也是O(n)的；

插入：如果在链表头或者在链表尾插入元素，时间复杂度是O(1)的，否则，在特定位置插入元素，时间复杂度是O(n)；

删除：和插入一样，如果在链表头或者在链表尾删除元素，时间复杂度是O(1)的，否则，删除特定位置元素或者删除特定元素，时间复杂度是O(n)；

如果你之前认为链表的增删改的时间复杂度是小于O(n)的，那么这个认识是错误的。

链表的优势在于：

1，节省空间，由于不是静态分配内存，没有空间浪费

2，不需要resize。在不停的添加且删除元素的过程中，如果经常触发resize，resize本身会很耗时。

3，如果你存储的数据没有顺序性要求，换句话说，如果你不会在特定位置插入或者删除元素，而只会在头尾插入或者删除元素的话，链表的时间复杂度是O(1)的！对于数组，只有在数组末尾添加元素，才是O(1)级别，而且是均摊后的结果。

4，另外，对于java.util.LinkedList底层的循环双链表来说，在指定位置插入元素，或者删除指定位置的元素，实际最多只需要遍历n/2个元素就好了。虽然复杂度依然是O(n)的，但当元素个数没有超过一定限制的时候（不同计算机不一样，大概100万级别），平均比动态数组的O(n)快。

• 提问者 慕田峪6134623 #1

  好的，谢谢老师的解答