# `ArrayList`与`LinkedList`的区别

![Java 集合继承关系图](https://cs-wlei224.obs.cn-south-1.myhuaweicloud.com/blog-imgs/202312121816932.png)

首先，他们都是`List`的集合的实现方式之一。具体来说，集合`List`有`ArrayList`、`LinkedList`、`AbstractList`、`Vector`四种实现方式，因为实现方式的不同，所以效率也不同。其中`LinkedList`些许特别，具体看图。（留一个小问题：`LinkedList`可以实现队列与栈吗？）

如果说二者处理数据的效率区别的话，如果数据和运算量很小的情况下，那么就没有什么对比意义了，如果数据量很大，那么有着以下区别：

1. `ArrayList`底层是一个数组，因此它可以直接基于索引访问元素，查找和修改效率高，增加删除的话，如果是对于中间元素，则需要移动大量元素，那么效率低。当更多元素添加进来，其容量大小会动态增长，因为是基于数组的，所以内部元素可以通过`get()`与`set()`方法进行访问。

  > - 扩容策略：
  >
  >    - 初始默认容量`10`时，检查新增元素之后，是否超过数组容量，超过则扩容(检查容量)
  >    - 在`JDK 7 `之前，容量增加为原来的两倍，但最多不超过`Integer.MAX_VALUE`即`2^32 - 1`。`JDK 7`之后，增加为原来的1.5倍，即`newCapacity=oldCapacity+(oldCapacity >> 1)`，其实`JDK 8`中`ArrayList`的最大容量为`Integer.MAX_VALUE - 8`，是因为内部使用了数组复制的技巧对空间和内存做了优化，需要 8 个元素的空间。（设置新容量的数组）
  >    - 将旧数组的元素复制到扩容后的新数组中（复制数组）
  >
  > - 建议：
  >
  >   ​	因为`ArrayList`的初始容量很小，所以如果能预估数据量的话，尽量分配一个合理的初实容量，这样可以极大减少数据扩容的开销

2. `LinkedList`底层是一个双向链表，因此当增加或者删除一个元素时，通过直接移动指针的指向就能实现，增删效率高，但是对于查找或修改（也就是`get()`与`set()`），它需要从头结点遍历元素，因此效率低。

   > - `LinkedList`怎么实现队列与栈？
   >
   >   ​	通过上图我们可以看到，因为`LinkedList`继承于一个`AbstractSqquentiaList`的双向链表，然后就决定了它可以调用`push()和pop()`方法来当作栈使用；又因为`LinkedList`实现了`List`接口，所以可以调用里面的`add()和remove()`方法进行实现队列的操作。

