ArrayList 与 LinkedList 区别

野性酷女 2023-10-04 08:14 163阅读 0赞

在 [ArrayList 源码解析][ArrayList] 中，我们说了 ArrayList 的成员变量、初始化、常用方法以及通过举例子说了 ArrayList 的扩容机制；在 [LinkedList 源码解析][LinkedList] 中，我们也说到了 LinkedList 的成员变量、构造方法、以及花大量的篇幅介绍了 LinkedList 的方法，另外还说到了 LinkedList 的结构是一个双向链表。

今天我们将对 ArrayList 与 LinkedList 做一次对比。

#### 数据结构 ####

这个很简单，也很基础，后续的区别都是基于它们的底层数据结构引起的：

1.  ArrayList 的底层是一个数组
2.  LinkedList 的底层是双向链表（可以访问 [双向链表][Link 1] 来对双向链表进行学习）

#### 空间占用 ####

1.  ArrayList 空间浪费在其初始化以及扩容时会有一些预留空间
2.  LinkedList 的空间浪费在它的每个元素都得花「3 格」来存储，分别为前驱、元素值、后继。

#### 操作时间复杂度 ####

关于时间复杂度，请参考博主写的 [算法时间复杂度][Link 2]，欢迎斧正。

##### 插入 #####

就先说 ArrayList 吧，分两种情况：

1.  插入到列表最后，对应方法为 `add(E e)`，此时的时间复杂度就是 O(n)；
2.  在位置 i 处插入元素的话，对应方法为 `add(int index, E element)`，时间复杂度就为O(n-i) 。为什么是 O(n-1) 呢，因为涉及到要将位置 i 之后的元素都向右移动一位；

再说下 LinkedList 吧，也是分两种情况：

1.  插入到链表最后，此时的时间复杂度为 O(1)，对应方法为 `add(E e)`；
2.  插入到链表指定位置，对应方法为 `add(int index, E element)`，此时时间复杂复杂度为 O(n)，因为涉及到先要找到指定位置才进行插入。

##### 读取 #####

由于 ArrayList 底层是数组，有下标，所以可以实现高效的随机元素访问；而 LinkedList 底层是链表，就不支持高效的随机元素访问。

> 关于二者在操作的时间复杂度，推荐阅读：[When to use LinkedList over ArrayList in Java? - Stack Overflow][When to use LinkedList over ArrayList in Java_ - Stack Overflow]。访问可能慢，就直接把结论贴出来吧：  
> ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01yQmF5bWF4_size_16_color_FFFFFF_t_70]

#### 线程安全问题 ####

ArrayList 和 LinkedList 二者都是线程不安全的。

> 至于原因和解决方案，请期待以后有关多线程的源码博客。

--------------------

这篇文章整体比较简单，欢迎读者阅读斧正。

关联阅读：

1.  [线性表][Link 3]
2.  [双向链表][Link 1]
3.  [ArrayList 源码解析][ArrayList]
4.  [LinkedList 源码解析][LinkedList]
5.  [算法时间复杂度][Link 2]

[ArrayList]: https://mindartisan.blog.csdn.net/article/details/114650148
[LinkedList]: https://mindartisan.blog.csdn.net/article/details/114702017
[Link 1]: https://mindartisan.blog.csdn.net/article/details/114501996
[Link 2]: https://mindartisan.blog.csdn.net/article/details/112691301
[When to use LinkedList over ArrayList in Java_ - Stack Overflow]: https://stackoverflow.com/questions/322715/when-to-use-linkedlist-over-arraylist-in-java/322742#322742
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01yQmF5bWF4_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20210314015100940.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01yQmF5bWF4,size_16,color_FFFFFF,t_70
[Link 3]: https://mindartisan.blog.csdn.net/article/details/113271849