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

来源：8-3 向堆中添加元素和Sift Up

李爽爽爽爽

2018-09-25

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

写回答

1回答

liuyubobobo

2018-09-25

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

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

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

加油！：）

李爽爽爽爽

理解了，谢谢老师～

2018-09-25

共1条回复

玩转数据结构

动态数组/栈/队列/链表/BST/堆/线段树/Trie/并查集/AVL/红黑树…

6221 学习 · 1704 问题

相似问题

回答 1

回答 1

回答 1

回答 1

回答 2