实现 List 的类 - 优点和缺点

该 List 接口是由不同的类实现的。他们每个人都有自己的方式来实施不同的策略，并提供不同的利弊。

实现 List 的类

这些是 Java SE 8 中实现 java.util.List 接口的所有 public 类：

1. 抽象类：
   • AbstractList 中
   • AbstractSequentialList
2. 具体类：
   • 数组列表
   • AttributeList
   • CopyOnWriteArrayList
   • 链表
   • RoleList
   • RoleUnresolvedList
   • 堆
   • 向量

在时间复杂性方面的每个实现的优点和缺点

数组列表

public class ArrayList<E>
extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, Serializable

ArrayList 是 List 接口的可调整大小的数组实现。将列表存储到数组中， ArrayList 提供了用于操作数组大小的方法（除了实现 List 接口的方法 ）。

初始化整数的 ArrayList，大小为 100

List<Integer> myList = new ArrayList<Integer>(100); // Constructs an empty list with the specified initial capacity.

- PROS：

size，isEmpty， get ， set ，iterator 和 listIterator 操作以恒定时间运行。因此获取和设置 List 的每个元素具有相同的时间成本 ：

int e1 = myList.get(0);  //   \
int e2 = myList.get(10); //    | => All the same constant cost => O(1)
myList.set(2,10);        //   /

- 缺点：

使用数组（静态结构）实现在数组大小上添加元素的成本很高，因为需要为所有数组进行新的分配。但是，从文档 ：

添加操作以分摊的常量时间运行，即添加 n 个元素需要 O(n) 时间

删除元素需要 O(n) 时间。

AttributeList

来了

CopyOnWriteArrayList

来了

链表

public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, Serializable

LinkedList 由双向 链表实现，链表数据结构由一组称为节点的顺序链接记录组成。

Iitialize Integer 的 LinkedList

List<Integer> myList = new LinkedList<Integer>(); // Constructs an empty list.

- PROS：

在列表的前面或末尾添加或删除元素具有恒定的时间。

myList.add(10);  // \
myList.add(0,2); //  | => constant time => O(1)
myList.remove(); // /

- CONS： 来自文档 ：

索引到列表中的操作将从开头或结尾遍历列表，以较接近指定索引为准。

操作如：

myList.get(10);    // \
myList.add(11,25); //  | => worst case done in O(n/2)
myList.set(15,35); // /

RoleList

来了

RoleUnresolvedList

来了

堆

来了

向量

来了