WHCSRL 技术网

ArrayList 和 LinkedList

关系和差异:

  • ArrayList:底层使用数组存储元素(动态类型顺序表),查询快,增删慢,线程不安全
    LinkedList:底层使用双向链表结构存储管理元素(双向链表),查询慢,增删快,线程不安全
  • LinkedList不支持高效的随机元素访问
  • ArrayList的空间浪费主要体现在表尾预留空间容量,
    LinkedList的空间开销体现在每个元素都需要消耗相当大的空间
  • ArrayList和LinkedList,在表尾添加一个元素的开销为修复
  • 都实现了List接口

时间复杂度分析:

ArrayList

<块引用>

1.add(E e) — O(1) < /font>
直接在后面添加元素
2.add(int index, E e) — O(N)
添加一个元素并插入到index元素之后,后面的元素需要往后移
3.get(int index) — O(1)
直接在index下读取底层元素
4.remove(int index) — O(N)
删除指定位置的元素

LinkedList

<块引用>

1.add(E e) — O(1) < /font>
将元素直接追加到列表的末尾
2.add(int index, E e) — O(N)
要在这个列表的指定位置插入指定元素,需要先找到指定位置
3.get(int index) — O(N)
返回这个链表中指定位置需要依次遍历的元素
4.remove() — O(1)
检索并删除这个链表的头部

补充

如果ArrayList添加了无限元素,会抛出异常吗?

每个ArrayList实例都有一个容量,是指用于存储列表元素的数组的大小,它总是至少等于列表的大小。 ,随着你不断向ArrayList添加元素,它的容量会自动增长,而自动增长会再次将数据带到新的数组副本中,所以如果可以预测数据量,可以在构造ArrayList时指定它的容量
ArrayList扩容时,一般情况下会扩容1.5倍。(newCapacity = oldCapacity + (oldCapacity >> 1)

推荐阅读