java - 什么时候在 Java 中使用 LinkedList 而不是 ArrayList?

标签 java arraylist collections linked-list

我一直是一个简单使用的人:

List<String> names = new ArrayList<>();

我使用接口(interface)作为可移植性的类型名称,这样当我提出诸如此类的问题时,我可以重新编写我的代码。

什么时候应该 LinkedList 超过 ArrayList 使用反之亦然?

最佳答案

总结 ArrayListArrayDeque 在比 LinkedList 多得多的用例中更可取。如果您不确定 - 只需从 ArrayList 开始。

TLDR,在 ArrayList 中访问一个元素需要常数时间 [O(1)] 并且添加一个元素需要 O(n) 时间 [最坏情况]。在 LinkedList 中,添加元素需要 O(n) 时间,访问也需要 O(n) 时间,但 LinkedList 使用的内存比 ArrayList 多。LinkedListArrayList 是 List 接口(interface)的两种不同实现。 LinkedList 使用双向链表实现它。 ArrayList 使用动态调整大小的数组来实现它。
与标准链表和数组操作一样,各种方法将具有不同的算法运行时。
对于 LinkedList<E>

  • get(int index) 是 O(n)(平均有 n/4 步),但是当 index = 0index = list.size() - 1 时是 O(1)(在这种情况下,您也可以使用 getFirst() 和 679104)。 getLast()
  • 的主要好处之一
  • LinkedList<E> 是 O(n)(平均有 n/4 步),但在 add(int index, E element)index = 0 时是 O(1)(在这种情况下,您也可以使用 index = list.size() - 1 和 079104 和 addFirst())。 addLast()
  • 的主要好处之一
  • add() 是 O(n)(平均有 n/4 步),但是当 LinkedList<E>remove(int index) 时是 O(1)(在这种情况下,您也可以使用 index = 0 和 679104)。 index = list.size() - 1
  • 的主要好处之一
  • removeFirst() 是 O(1)。 removeLast()
  • 的主要好处之一
  • LinkedList<E> 是 O(1)。 Iterator.remove()
  • 的主要好处之一

    注意:许多操作平均需要 n/4 步,在最好的情况下(例如索引 = 0)的步数保持不变,在最坏的情况下(列表的中间)需要 n/2 步
    对于 LinkedList<E>
  • ListIterator.add(E element) 是 O(1)。 LinkedList<E>
  • 的主要好处
  • ArrayList<E> 是 O(1) 摊销,但 O(n) 最坏情况,因为必须调整数组大小并复制
  • get(int index) 是 O(n)(平均 n/2 步)
  • ArrayList<E> 是 O(n)(平均 n/2 步)
  • add(E element) 是 O(n)(平均 n/2 步)
  • add(int index, E element) 是 O(n)(平均 n/2 步)

  • 注意:许多操作平均需要 n/2 步,最好情况下(列表末尾)的步数不变,最坏情况下(列表开头)n 步remove(int index) 允许使用迭代器进行恒定时间插入或删除,但只允许对元素进行顺序访问。换句话说,您可以向前或向后遍历列表,但在列表中查找位置所需的时间与列表的大小成正比。 Javadoc 说“索引到列表中的操作将从开始或结束遍历列表,以较近者为准”,因此这些方法平均为 O(n) (n/4 步),尽管 Iterator.remove() 为 O(1) 。
    另一方面, ListIterator.add(E element) 允许快速随机读取访问,因此您可以在恒定时间内获取任何元素。但是,除了结尾之外的任何地方添加或删除都需要将后面的所有元素都移过来,以形成开口或填补空白。此外,如果添加的元素多于底层数组的容量,则会分配一个新数组(大小的 1.5 倍),并将旧数组复制到新数组,因此添加到 LinkedList<E> 是 O(n)最坏的情况,但平均不变。
    因此,根据您打算执行的操作,您应该相应地选择实现。迭代任何一种 List 实际上同样便宜。 (在 index = 0 上迭代在技术上更快,但除非您正在做一些真正对性能敏感的事情,否则您不必担心这一点——它们都是常量。)
    当您重用现有迭代器来插入和删除元素时,使用 ArrayList<E> 的主要好处就出现了。然后可以通过仅在本地更改列表来在 O(1) 中完成这些操作。在数组列表中,数组的其余部分需要移动(即复制)。另一方面,在 ArrayList 中寻找意味着在最坏的情况下遵循 O(n)(n/2 步)中的链接,而在 ArrayList 中,所需的位置可以用数学方法计算并在 O(1) 中访问。
    使用 LinkedList 的另一个好处是在列表头部添加或删除时出现,因为这些操作是 O(1),而对于 LinkedList 则是 O(n)。请注意, ArrayList 可能是 LinkedList 的一个很好的替代,用于添加和删除头部,但它不是 ArrayList
    此外,如果您有大型列表,请记住内存使用情况也不同。 ArrayDeque 的每个元素都有更多的开销,因为还存储了指向下一个和前一个元素的指针。 LinkedList 没有这个开销。但是,List 占用的内存与为容量分配的内存一样多,无论是否实际添加了元素。LinkedList 的默认初始容量非常小(Java 1.4 - 1.8 中的 10)。但是由于底层实现是一个数组,如果添加很多元素,则必须调整数组的大小。当您知道要添加大量元素时,为了避免调整大小的高成本,请构建具有更高初始容量的 ArrayLists
    如果从数据结构的角度来理解这两种结构,LinkedList 基本上是一个包含头节点的顺序数据结构。 Node 是两个组件的包装器:一个 T 类型的值 [通过泛型接受] 和另一个对链接到它的 Node 的引用。因此,我们可以断言它是一个递归数据结构(一个节点包含另一个节点,该节点具有另一个节点等等......)。如上所述,在 LinkedList 中添加元素需要线性时间。
    一个ArrayList,是一个可增长的数组。它就像一个常规数组。在幕后,当一个元素被添加到索引 i 时,它会创建另一个大小比先前大小大 1 的数组(所以通常,当 n 个元素要添加到一个 ArrayList 时,一个大小为先前大小的新数组加上 n 被创建)。然后将元素从前一个数组复制到新数组,并且要添加的元素也放置在指定的索引处。

    关于java - 什么时候在 Java 中使用 LinkedList 而不是 ArrayList?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/322715/

    相关文章:

    java - 比较两个相同类型对象的列表

    java - 为什么 Java 中没有 SortedList?

    java - 如何仅当某个字符在匹配中出现 n 次时才匹配?

    java - 自定义查询正则表达式 MongoDB + Spring Data

    java - 在序列化期间从实体中删除代理代码

    java - 适配器上的 arraylist.remove() 删除 ListView 中的错误项目

    Java ArrayList.remove() 不减少 ArrayList 的大小

    java - 为什么以及何时使用 TreeMap

    scala - 具有过期和软值的基于 map 的缓存

    java - 在 GridView 上保持背景的纵横比