源码分析【三】ArrayList与LinkedList的比较

谁借莪１个温暖的怀抱￠ 2022-12-04 05:25 187阅读 0赞

**源码分析系列**

**[源码分析【一】LinkedList链表结构][LinkedList]**

**[源码分析【二】ArrayList数组][ArrayList]**

**[源码分析【三】ArrayList与LinkedList的比较][ArrayList_LinkedList]**

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

### 前言 ###

在做ArrayList与LinkedList的比较之前，必须先对这两个数据结构有一定的学习和掌握，之前2篇文章分别讲了ArrayList与LinkedList的介绍和源码讲解，感兴趣的伙伴可以戳下方链接分别查阅：

[1、ArrayList源码浅析][ArrayList]

[2、LinkedList源码分析][LinkedList]

### 一、数据结构 ###

CS专业的学生都学过一门课程叫：数据结构，里面专门讲了数据结构的原理知识和算法等。常见数据结构分为3大种：线性结构、树结构、图结构。

*  线性结构：数组（静态数组、动态数组）、线性表、链表（单向链表、双向链表、循环链表）、队列、栈。
 *  树：二叉树、查找树、平衡树、线索树、线索树、堆
 *  图：建模等

![format_png][]

其中，ArrayList与LinkedList就是属于线性结构，但一个是数组结构，一个是链表结构。有各自的特点和优势，在使用上也有各自的区别。

### 二、ArrayList的数组结构 ###

上面说了，线性结构中的数组分为动态数组和静态数组，那么ArrayList是属于哪种呢？答案是动态数组，Array是我们学习数组时的基本概念，在初始定义一个数组时，设置了数组大小，运行时数组大小固定不变这样就是静态数组。那么，ArrayList是Array的升级和复杂版，它能支持程序运行中动态扩展数组的大小，因此它是动态数组。

使用上，ArrayList是动态数组，支持随机快速访问get和set操作。

![format_png 1][]

### 三、LinkedList的链表结构 ###

链表结构包括：单向链表、双向链表、循环链表，由之前文章的源码解析（上方链接）可看出，LinkedList是一个双向链表结构，每个节点既存储了上一节点的引用又存储了当前节点的物理地址（内容），还存储了下一节点的引用。

单独节点元素：

![LinkedList1.jpg][]

LinkedList整体链表结构图：

![LinkedList2.jpg][]

### 四、ArrayList与LinkedList的比较 ###

1.  ArrayList是实现了**基于动态数组**的数据结构，而LinkedList是**基于链表**的数据结构；
2.   对于**随机访问get和set，ArrayList要优于LinkedList**，因为LinkedList要移动指针；
3.   对于添加和删除操作add和remove，一般大家都会说LinkedList要比ArrayList快，因为ArrayList要移动数据。但是实际情况并非这样，对于添加或删除，LinkedList和ArrayList**并不能明确说明谁快谁慢。**
4.  插入的数据量很小时，两者区别不太大，当插入的数据量大时，大约在容量的1/10之前，LinkedList会优于ArrayList，在其后就劣与ArrayList，且越靠近后面越差。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ZvbGxvd18yNA_size_16_color_FFFFFF_t_70][] 更多内容关注公众号： **程序大视界**

[LinkedList]: https://blog.csdn.net/xuri24/article/details/108110637
[ArrayList]: https://blog.csdn.net/xuri24/article/details/108310753
[ArrayList_LinkedList]: https://blog.csdn.net/xuri24/article/details/108425058
[format_png]: /images/20221123/4bf87095c81c4f72b216d3d91009ff3a.png
[format_png 1]: /images/20221123/428c5386f734462f84a7181fc2a1b1b1.png
[LinkedList1.jpg]: /images/20221123/626698d303e042c39db029eb23077649.png
[LinkedList2.jpg]: /images/20221123/3aa524a149a041aba075d706d16f88c3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ZvbGxvd18yNA_size_16_color_FFFFFF_t_70]: /images/20221123/704d8295b96a4ff990f996463c1f13c2.png