arraylist 和 linkedlist 的增加删除操作复杂度都是O(n)

Question

老师您好，ArrayList和LinkedList的增加删除操作的复杂度都是O(n)，为什么很多面试题里面都说LinkedList是更便于进行增加和删除操作的？谢谢老师

Answer 1

liuyubobobo 2018-09-25 12:04:13

LinkedList更常用的场景是在顺序表的头或者尾做添加和删除操作，此时，时间复杂度是O(1)的。

对比ArrayList，只有在尾部添加和删除元素是O(1)的，同时还有扩容和缩容带来的时间消耗以及浪费的静态空间。

但是，如果随时要在顺序表的中间添加或者删除元素的话（比如维护顺序表的有序性），链表和动态数组的添加和删除操作，时间复杂度都是O(n)的，链表是没有性能效率优势的：）

加油！：）

• 提问者 李爽爽爽爽 #1

  理解了，谢谢老师～