ArrayList和LinkedList底层实现原理

小鱼儿 2023-10-11 12:19 64阅读 0赞

### ArrayList和LinkedList底层实现原理 ###

*   *   *  ArrayList 底层实现方式(转)
         *  数组的特点(原)
         *  LinkedList 底层实现方式(原)
         *  关于ArrayList和LinkedList的索引问题(转)

该文章前半部分是采纳自以下链接,但因文章不全,我特意加上自己的理解进行发布,如有侵权,请联系本人,本人会进行有关内容的删除,或者进行删帖及重构

[ArrayList和LinkedList底层实现原理][ArrayList_LinkedList]

### ArrayList 底层实现方式(转) ###

①ArrayList 通过数组实现，一旦我们实例化且不声明容器大小的话, ArrayList 无参数构造函数默认为数组初始化长度为 10  
![ArrayList的底层构造说明][ArrayList]  
②add 方法底层实现如果增加的元素个数超过了 10 个，那么 ArrayList 底层会新生成一个数组，长度为原数组的 1.5 倍+1，然后将原数组的内容复制到新数组当中，并且后续增加的内容都会放到新数组当中。当新数组无法容纳增加的元素时，重复该过程。是一旦数组超出长度，就开始扩容数组。扩容数组调用的方法 Arrays.copyOf(objArr, objArr.length + 1)

### 数组的特点(原) ###

![数组和链表的区别][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lpaHVhaXlhbg_size_16_color_FFFFFF_t_70]

### LinkedList 底层实现方式(原) ###

![结点结构图][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lpaHVhaXlhbg_size_16_color_FFFFFF_t_70 1]  
*链表中的结点说明*  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lpaHVhaXlhbg_size_16_color_FFFFFF_t_70 2]

### 关于ArrayList和LinkedList的索引问题(转) ###

> LinkedList集合中的元素也是有序的，有索引，那为什么和ArrayList相比起来查找速度会比较慢，而增删快呢？  
> 我们来打个比方：LinkedList和ArrayList中都装了10个人。  
> 在ArrayList集合中  
> 因为Arraylist中本身就有标号0,1,2, 3,…。每个人都站在一个标号.  
> 比如我要找4号，我说4号出来，站在4号的人，一看自己的位置标号，就知道叫的是他，他就直接出来了，所以比较快。如果我要在4号位置加个人，那么从4号开始后面的的人都要往后移，把4号位置腾出来，所以比较麻烦。  
> 在LinkedList集合中  
> 而在LinkedList集合中的每个人都是随便站的。但是他们中的每个人都认识跟自己相连的人。并且每两个认识的人之间都有一条链子把他们连接起来。所有人都连接完之后，顺着链子看，就也有一个顺序，每个人就也有一个序号，但是这个序号并没有标出来。也不知道有多少个链子,每个人只知道自己旁边是否有认识的人,而超出了范围就不知道还有多少个链子,也就是顺着链子看相当于有一个隐式的序号。  
> 所以：比如我要叫4号出来的时候，他们并不知道到底谁是4号，所以就要顺着链子从头开始查一下，查到某个结点的值是4号是谁了，4号就出来了。也就是说，每次要找n号位置的人时，都要从头查一遍，看那个结点的值是n号。所以查找比较麻烦。至于增删效率高，就很容易理解了。因为链子上有结点,比如我要增加或者删除一个结点,只需对对应的结点进行操作即可  
> 其实就是一点，就是相当于说：ArrayList集合中的索引是标示出来的，而LinkedList集合中的索引是隐式的，看不见的。这样就很容易理解，这就是为什么LinkedList集合中也有索引为什么查找效率比Arraylist低的原因了。

[ArrayList_LinkedList]: https://blog.csdn.net/weixin_38422276/article/details/78978410
[ArrayList]: https://img-blog.csdnimg.cn/20190923154303555.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lpaHVhaXlhbg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lpaHVhaXlhbg_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20190923144523946.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lpaHVhaXlhbg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lpaHVhaXlhbg_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20190923152750366.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lpaHVhaXlhbg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lpaHVhaXlhbg_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20190923154710831.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lpaHVhaXlhbg==,size_16,color_FFFFFF,t_70