ArrayList或LinkedList？

---

本文为Java开发人员选择适当的顺序数据结构提供了指导。

ArrayList和LinkedList 两个类的Java集合框架用于存储对象引用的名单。ArrayList并且 LinkedList 都实现了List接口。让我们首先尝试了解它们最重要的父接口List（哪个）。

列表界面 列表只是元素的有序集合（也称为序列）。它添加了面向位置的操作，这些操作对于快速访问，添加和删除列表中特定索引位置的元素很有用。列表接口具有Collection和Iterable作为超级接口。它可以允许存储重复项和空值。它提供对其元素的索引访问。

Usage 下面是声明ArrayList 和LinkedList使用List接口的代码段。

import java.util.*;
public class MyClass {

  // Unsynchronized or Not thread safe
  List<Object> arrayList = new ArrayList<>(); // declares an array list
  List<Object> linkedList = new LinkedList(); // declares a linked list   

    // ensures thread safety 
  List<Object> tsArrayList = Collections.synchronizedList(new LinkedList<>());
  List<Object> tsLinkedList = Collections.synchronizedList(new LinkedList<>());   
}

Vector与ArrayList 它们相似，不同之处在于它们具有自动同步功能，这使它们具有线程安全性，但会导致性能开销。

内部实施

链表 该LinkedList数据结构包含一组有序的数据元素（如知道节点），使得每个元素包含到其后继（链接或参考下一个元素）。序列的最后一个元素（或tail）指向空元素。链接列表本身包含对列表的第一个元素（称为head元素）的引用。Java中的LinkedList是List接口的双链列表实现。在双向链接列表中，每个节点都指向其上一个和下一个节点。它实现的其他接口是Serializable，Cloneable和Deque（将超级接口作为Queue））。

数组列表

ArrayList是List接口的可调整大小的数组实现。它在内部实现为对象数组，可以根据需要增加大小以支持集合中更多的元素。可以ArrayList 通过构造函数指定a的初始容量，ArrayList(int initialCapacity) 然后void ensureCapacity(int minCapacity)在需要时使用来增加容量 ，以确保它可以容纳至少由minimum Capacity参数指定的元素数量。

它还包括一种基于现有元素减小大小的方法。 void trimToSize()

// calling constructure ArrayList<type>(initialCapacity)
List arr = new ArrayList<Integer>(10);

默认情况下，an创建一个初始容量为10的列表，而LinkedList仅构建一个没有任何初始容量的空列表。 LinkedList 不实现RandomAccess接口，而实现接口（而不是Deque接口）。

各种行动的时空复杂性

特征	数组列表	链表
添加（或删除）元素	这涉及将所有现有元素向后（或向前）移动一个位置，这需要通过调用System.arraycopy（）复制完成的项目 。**-最佳情况下 时间复杂度为O（1）。平均情况下的时间复杂度O（n）为System.arraycopy（）将是线性时间。	这涉及为元素分配（或取消分配）内部记录，然后重新对齐几个链接，并且具有固定成本。-时间复杂度为O（1）。在列表的中间添加（或删除）元素的时间复杂度为O（n），因为它将涉及遍历列表。
追加元素	通常，这涉及到以O（1）的时间复杂度将内部数组位置设置为元素引用。但是，有时在发生溢出的情况下，这会导致重新分配数组并具有固定的平均成本，再次涉及触发调用到System.arraycopy（）， 最坏情况下的时间复杂度为O（n）。	这仅涉及分配内部对象，并且成本是统一的。
内存空间开销	它具有存储空间开销，因为必须预先分配对象列表，这意味着在列表末尾有空元素。	它具有存储空间开销，用于存储对每个元素的列表中上一个和下一个元素的引用。
随机访问其元素	随机访问具有固定的时间-时间复杂度为O（1）。	进行随机访问的时间与列表的大小成正比（除非这是固定成本的第一个或最后一个元素）-平均情况下的时间复杂度为O（n）。
空值	是的，它可以存储	是的，它可以存储
重复项	是的，它可以存储	是的，它可以存储

Tips 考虑下面的代码示例遍历A。LinkedList下面的代码非常慢，因为LinkedList它不支持随机访问，并且每次迭代遍历时都有巨大的开销。

LinkedList ll = new LinkedList();
…
…
Object o = null;
for (int i = 0; i < list.size(); i++)
{
o = list.get(i);
…
}

改善性能的更好方法是改为使用以下代码。

LinkedList ll = new LinkedList();
…
…
Object o = null;
ListIterator li = list.listIterator(0);
while (li.hasNext()){
o = ll.next();
…
}

结论 AnArrayList 更快更好，因为它支持对其元素的随机访问。遍历链表或在中间插入项目非常昂贵，因为您必须遍历每个项目，并且很可能会发生缓存未命中的情况。如果您需要在单次迭代中对列表的多个项目执行处理，则迭代的开销LinkedList要比ArrayList涉及多次复制数组元素的开销要少。

要分享您对这个主题的经验和更多见解，请在下面的评论部分中留下您的想法。

---

原文链接：http://codingdict.com

---