Java中ArrayList和LinkedList区别时间复杂度与空间复杂度

84 阅读 0 评论 56 点赞

我是靠谱客的博主聪慧季节，这篇文章主要介绍Java中ArrayList和LinkedList区别时间复杂度与空间复杂度，现在分享给大家，希望可以做个参考。

ArrayList 是线性表（数组）
get() 直接读取第几个下标，复杂度 O(1)
add(E) 添加元素，直接在后面添加，复杂度O（1）
add(index, E) 添加元素，在第几个元素后面插入，后面的元素需要向后移动，复杂度O（n）
remove（）删除元素，后面的元素需要逐个移动，复杂度O（n）

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

Arraylist 插入(非末项添加)和删除比较慢，那是因为Arraylist需要移动数组内的对象的位置。

在ArrayList的中间插入或删除一个元素意味着这个列表中剩余的元素都会被移动；而在LinkedList的中间插入或删除一个元素的开销是固定的。

LinkedList不支持高效的随机元素访问。