get(int index)是 O (n)(平均 N/4步) ，而 O (1)是 index = 0或 index = list.size() - 1(在这种情况下，也可以使用 getFirst()和 getLast())。的主要好处之一LinkedList<E>
add(int index, E element)是 O (n)(平均有 N/4步) ，而 O (1)是 index = 0或 index = list.size() - 1(在这种情况下，也可以使用 addFirst()和 addLast()/add())。index = 00 LinkedList<E>
remove(int index)是 O (n)(平均 N/4步) ，而 O (1)是 index = 0或 index = list.size() - 1(在这种情况下，也可以使用 removeFirst()和 removeLast())。的主要好处之一LinkedList<E>
Iterator.remove()是 O (1)的主要好处之一是 LinkedList<E>
ListIterator.add(E element)是 O (1)的主要好处之一是 LinkedList<E>
注意: 许多操作平均需要 N/4步骤，最佳情况下需要 不变步骤数(例如 index = 0) ，最差情况下需要 N/2步骤(列表中间)
LinkedList<E>允许固定时间的插入或删除 使用迭代器，但只允许元素的循序存取。换句话说，你可以在列表中前后行走，但是在列表中找到一个位置所花费的时间与列表的大小成正比。Javadoc 说是 索引到列表中的操作将从开始或结束遍历列表，以较近者为准，所以这些方法平均是 O (n)(N/4步) ，而 index = 0是 O (1)。
另一方面，ArrayList<E>允许快速随机读取访问，因此可以在恒定时间内获取任何元素。但是增加或删除从任何地方，但结束需要移动所有后者的元素，无论是作出一个开放或填补空白。另外，如果你添加的元素超过了底层数组的容量，一个新的数组(1.5倍的大小)将被分配，旧的数组将被复制到新的数组中，所以向 ArrayList中添加的元素在最坏的情况下是 O (n)，但是平均值是常数。
因此，根据您打算执行的操作，您应该相应地选择实现。对这两种 List 进行迭代实际上同样便宜。(在 ArrayList上迭代在技术上更快，但是除非您正在执行一些真正与性能相关的操作，否则不必担心这个问题——它们都是常量。)
使用 LinkedList的主要好处出现在重用现有迭代器插入和删除元素时。然后可以在 O (1)中通过仅在本地更改列表来完成这些操作。在数组列表中，数组的其余部分需要是 感动(即复制)。另一方面，在 LinkedList中寻找意味着在最坏的情况下遵循 O (n)(N/2步骤)中的链接，而在 ArrayList中，所需的位置可以通过数学计算并在 O (1)中访问。
使用 LinkedList的另一个好处是，当您从列表的头部添加或删除时，因为这些操作是 O (1)，而对于 ArrayList是 O (n)。请注意，ArrayDeque可能是一个很好的替代 LinkedList增加和删除从头，但它不是一个 List。
Algorithm ArrayList LinkedList
seek front O(1) O(1)
seek back O(1) O(1)
seek to index O(1) O(N)
insert at front O(N) O(1)
insert at back O(1) O(1)
insert after an item O(N) O(1)
作为一个在大规模 SOA Web 服务上从事操作性能工程已经有十年的人，我更喜欢 LinkedList 的行为而不是 ArrayList。虽然 LinkedList 的稳态吞吐量更差，因此可能导致购买更多的硬件——数组列表在压力下的行为可能导致集群中的应用程序以近乎同步的方式扩展它们的数组，对于较大的数组大小可能导致应用程序缺乏响应和中断，而在压力下，这是灾难性的行为。
对于 ArrayList 和 LinkedList，remove()和 insert()的运行时效率都是 O (n)。然而，线性处理时间背后的原因来自两个非常不同的原因:
在 ArrayList 中，您可以访问 O (1)中的元素，但是实际上移除或插入某些内容会使其成为 O (n) ，因为需要更改以下所有元素。
在 LinkedList 中，实际上需要 O (n)才能到达所需的元素，因为我们必须从最开始开始，直到到达所需的索引。实际上，移除或插入是常量，因为我们只需要为 remove()改变1个引用，为 insert()改变2个引用。
插入和删除两者中哪一个更快取决于它发生的位置。如果我们更接近开始，LinkedList 会更快，因为我们必须通过相对较少的元素。如果我们更接近结束，数组列表会更快，因为我们到达那里的时间是恒定的，只需要改变它后面的少数剩余元素。如果精确地在中间完成，LinkedList 会更快，因为遍历 n 个元素比移动 n 个值更快。
好处: 虽然没有办法为数组列表创建这两个方法 O (1) ，但实际上在 LinkedList 中有一种方法可以做到这一点。假设我们希望在执行的过程中完成整个 List 的删除和插入操作。通常，您可以从使用 LinkedList 的每个元素的最初开始，我们还可以“保存”使用迭代器处理的当前元素。在迭代器的帮助下，当我们在 LinkedList 中工作时，我们得到了 remove()和 insert()的 O (1)效率。让它成为我所知道的唯一性能优势，LinkedList 总是比 ArrayList 好。
public static void main(String[] args) {
List<Long> times = new ArrayList<>();
for (int i = 0; i < 100; i++) {
times.add(doIt());
}
System.out.println("avg = " + (times.stream().mapToLong(x -> x).average()));
}
static long doIt() {
long start = System.nanoTime();
List<Object> list = new LinkedList<>();
//uncomment line below to test with ArrayList
//list = new ArrayList<>();
for (int i = 0; i < 500; i++) {
list.add(i);
}
Iterator it = list.iterator();
while (it.hasNext()) {
it.next();
it.remove();
}
long end = System.nanoTime();
long diff = end - start;
//uncomment to see the JVM warmup and get faster for the first few iterations
//System.out.println(diff)
return diff;
}
