ArrayList 与 LinkedList 的区别？

ArrayList 是一个基于数组的列表。LinkedList - 基于元素和它们之间的链接的链表。作为 LinkedList，串联连接的火车车厢的表示最适合。

当索引访问优先时，应使用ArrayList ，因为这些操作是在恒定时间内执行的。添加到列表的末尾，平均而言，也需要常数时间。此外，在 ArrayList 中，在元素之间存储捆绑包不会产生额外成本。插入/删除不在列表末尾的元素的速度不足，因为在此操作期间，添加/删除右侧的所有元素都会移动。

当插入/删除操作的性能更为重要时， LinkedList很有用，这在 LinkedList 中是在恒定时间内执行的。索引访问操作是通过从开头或结尾（以较近者为准）迭代到所需元素来执行的。在元素之间存储捆绑包的额外成本。

总之 - 如果你经常插入/删除 - 选择LinkedList，否则ArrayList

ArrayList基于普通数组。这个集合动态增加数组的大小，如果没有足够的空间，调用add(T element)方法时addAll(Collection<T> other)trimToSize()

LinkedList它是由节点组成的普通链表。每个节点存储指向下一个/上一个节点和值的链接。在列表本身中，有指向最后一个和第一个节点的链接，以及大小。

为了评估这些数据结构，可以求助于操作的渐近复杂性：

                          |  ArrayList  |  LinkedList 
 add (в начало)           |     O(n)    |   O(1)
 add (в середину)         |     O(n)    |   O(n)
 add (в конец списка)     |     O(n)    |   O(1)   

LinkedList插入按如下方式执行：找到元素，插入的元素必须遵循该元素，更改其中的链接和紧随其后的链接。

ArrayList如果当前数组中没有空间，则会创建一个新数组。插入元素之前的那些元素保留在原位，或被复制到新元素中。接下来，添加插入的元素。然后复制原始文件中的剩余元素。

get (первый элемент)        |   O(1)    |   O(1)
get (из середины)           |   O(1)    |   O(n)
get (последний элемент)     |   O(1)    |   O(1)

为了LinkedList找到具有所需索引的元素，您需要从第一个元素到最后一个元素（在最坏的情况下）一个一个地遍历链接。ArrayList通过简单地从数组中按索引获取元素来获取元素。

delete (первый элемент)     |   O(n)    |   O(1)
delete (из середины)        |   O(n)    |   O(n)
delete (последний элемент)  |   O(1)    |   O(1)

删除LinkedList类似于插入。在ArrayList中，与添加时大致相同。

正如我们平均看到的那样，困难是相同的。但我不建议使用LinkedList，除非在列表的开头或结尾删除或插入占主导地位。

ArrayList就数据布局而言，处理器的可预测性更高。这是一个数组，里面的元素是顺序排列的，占据一块连续的内存区域 。这很好，因为它允许您在没有cache miss'ов. 处理器没有空闲，正在等待来自 RAM 的数据。没有LinkedList这样的事情，因为 元素位于内存的不同部分，处理器无法预测下一个元素的位置。

显示性能差异的代码：

@Fork(1)
@Warmup(iterations = 10)
@Measurement(iterations = 10)
@BenchmarkMode(Mode.AverageTime)
@Threads(1)
@State(Scope.Benchmark)
@OutputTimeUnit(TimeUnit.MILLISECONDS)
public class PerformanceTest {
   private static List<Object> arrayList;
   private static List<Object> linkedList;

   private static final int count = 100_000;

   public static void main(String[] args) throws Exception {
    Main.main(args);
   }

   @Setup
   public static void setup() {
      arrayList = new ArrayList<>(count);
      linkedList = new LinkedList<>();

      for (int i = 0; i < count; i++)
         arrayList.add(new Object());

      linkedList.addAll(arrayList);
   }

   @Benchmark
   public void removeFromLinkedList(Blackhole blackhole) throws Exception {
      Object object = new Object();
      linkedList.remove(count / 2);
      linkedList.add(count / 2, object);
   }

   @Benchmark
   public void removeFromArrayList(Blackhole blackhole) throws Exception {
      Object object = new Object();
      arrayList.remove(count / 2);
      arrayList.add(count / 2, object);
   }
} 

在我的电脑上，情况是这样的：

Benchmark                             Mode  Cnt  Score    Error  Units
PerformanceTest.removeFromArrayList   avgt   10  0.011 ±  0.001  ms/op
PerformanceTest.removeFromLinkedList  avgt   10  0.148 ±  0.001  ms/op

结果表明它LinkedList慢了14倍。

在选择ArrayList列表作为实现时，应该明白添加元素的操作可能会导致需要增加数组的大小，这将导致将所有元素从一个数组复制到另一个数组的操作。对此要注意初始容量，可以在创建列表时在构造函数中指定public ArrayList(int initialCapacity)。

如果您无法估计集合中将存储的元素的估计数量并且您不需要通过索引访问元素，那么最好注意LinkedList。

了解不同类型的集合有何不同非常重要，但在实践中，对于大多数应用程序任务，我们谈论的是数十个和数百个元素，特定集合实现的选择在性能和内存使用情况。更重要的是您将要使用的集合接口的选择：

• java.util.集合
• java.util.列表
• java.util.Set

接口的选择将直接影响你代码的逻辑。接口还可以更好地用作公共方法的参数和返回类型。