第四章 java中ArrayList和LinkedList的区别


常见的面试问题之一是“ArrayList 和 LinkedList 有什么区别”。在我们真正看到区别之前,让我先简单介绍一下两者。

数组列表

  • ArrayList 是列表接口的实现。
  • ArrayList 未同步(因此不是线程安全的)
  • ArrayList 是使用数组作为内部数据结构实现的,可以动态调整大小。

链表

  • LinkedList 是 list 和 deque 接口的实现。
  • LinkedList 不同步
  • LinkedList 是使用双向链表作为内部数据结构来实现的。

ArrayList 与 LinkedList:

范围 数组列表 链表
内部数据结构 它使用动态数组在内部存储元素 它使用双向链表在内部存储元素
操纵 如果我们需要在 ArrayList 中插入或删除元素,可能需要 O(n),因为它内部使用数组,我们可能需要在插入或删除的情况下移动元素 如果我们需要在 LinkedList 中插入或删除元素,则需要 O(1),因为它内部使用了双重 LinkedList
搜索 ArrayList 中的搜索速度更快,因为在内部使用基于索引的数组。所以这里的时间复杂度是 O(1) LinkedList 中的搜索速度较慢,因为内部使用了双链表所以这里的时间复杂度是 O(n)
接口 ArrayList 只实现了 List 接口,所以只能作为 List 使用 LinkedList 实现了 List、Deque 接口,因此可以作为 List、Stack 或 Queue 使用

何时使用 ArrayList 或 LinkedList?

这实际上取决于我们的需要。

  • 如果我们有更多的插入或删除,那么我们应该使用 LinkedList。
  • 如果我们有较少的插入或删除和更多的搜索操作,那么我们应该使用 ArrayList。


原文链接:https://codingdict.com/