从源码分析ArrayList和LinkList的区别

旧城等待， 2022-07-16 23:13 208阅读 0赞

http://blog.csdn.net/u012734441/article/details/43342831

先写一段代码：

**\[java\]** [view plain][] [copy][view plain]

1.  **package** cn.com.ListDemo; 
2.  
3.  **import** java.util.ArrayList; 
4.  **import** java.util.LinkedList; 
5.  **import** java.util.List; 
6.  
7.  **import** org.junit.Test; 
8.  
9.  **public****class** test \{ 
10. @Test
11. **public****void** testArrayList()\{ 
12.  List<String> list=**new** ArrayList<String>(); 
13.  list.add("bingwen"); 
14.  list.add("tom"); 
15.  list.add("jack"); 
16.  list.add("john"); 
17.  list.add(2, "ruby"); 
18. **for**(String str:list)\{ 
19.  System.err.println(str); 
20.  \} 
21.  System.err.println(list.size()); 
22.  \} 
23. @Test
24. **public****void** testLinkList()\{ 
25.  LinkedList<String> list=**new** LinkedList<String>(); 
26.  list.add("java"); 
27.  list.add("python"); 
28.  list.add("C\#"); 
29.  list.add("php"); 
30. **for**(String str:list)\{ 
31.  System.err.println(str); 
32.  \} 
33.  \} 
34. \}

其运行结果分别为：

testArrayList():

![Center][]

testLinkList:

![Center 1][]

两个方法的运行结果相同，因此要转到各自源码再做分析：

先看LinkList的源码：

![Center 2][]

LinkList继承了AbstractSequentialList并实现了List接口，查看AbstractSequentialList源码，为：

![Center 3][]

AbstractSequentialList继承了AbstractList类，再转到AbstractList源码为：

![Center 4][]

AbstractList依然是实现了List接口。

再来看ArrayList的源码：

ArrayList为：

![Center 5][]

ArrayList继承了AbstractList类，并实现了List接口，并也继承了AbstractList类，我刚刚画了张图，

来描述这两个类之间的关系。其中画出了ArrayList和LinkList继承的主要的类和接口。

![Center 6][]

从该图中可以看出ArrayList和LinkList两个类之间其实在继承接口还有父类方面并没有太多的差别，

而其中更是有着许多相同的方法，因此，这两个类之间更多的不同是在于对各自的方法的实现不同。

先来看ArrayList的源码实现：

![Center 7][]

在ArrayList中声明了一个Object类的数组。

然后：

![Center 8][]

其次在构造函数中对elementData数组指定大小：

![Center 9][]

在ArrayList中另外的一个构造函数中：

![Center 10][]

在此size进行了初始化，在其后几乎所有的的方法中都有size的参与。

再看ArrayList中的indexof()方法的源码：

![Center 11][]

对数组进行遍历，然后返回一个对应元素的下标。

再看ArrayList中的两个add()方法，其一为：

![Center 12][]

首先扩大数组容量，其中ensureCapacity()方法的实现为：

![Center 13][]

扩大容量后，将富足进行复制，然后数组就变成了一个更大的数组，然后我们再回到之前的add方法，

将添进来的元素放入数组中，同时size++，然后返回true、

再看第二个add方法：

![Center 14][]

第二个add方法适用于在指定位置添加新元素，在指定的下标前的元素不作处理，

在指定下标的后面的所有元素全部向后移一位。

对ArrayList的分析就到这为止，终其究竟，就是对动态数组的增、删、改、查。

再对LinkList进行源码分析：

![Center 15][]

首先是声明了一个Entry类型的header，然后再声明了一个int类型的size，并且初始化为0；

构造函数为：

![Center 16][]

这一个默认的构造函数确立header为一个孤立的节点。

下一个带参数的构造函数为：

![Center 17][]

将传进来的参数使用addAll()方法全部添加到header中

![Center 18][]

在调用这个addAll()方法后，实质上仍然调用了另外一个addAll()方法，为：

![Center 19][]

从之前声明的header，以及这个AddAll()方法中，

可看出LinkList内部实际使用的是一个链表来进行值得增、删、改、查。

从另外一个add()方法中更可以看出这个特点：

![Center 20][]

再调用addBefore()方法，

![Center 21][]

在这个方法中，转到Entry的构造方法，

![Center 22][]

可看出就是链表的一个增加节点的操作。

LinkList的分析就到此为止，其他的所有的操作实质上都是基于链表进行的。

**总结：**

**综上，ArrayList实质上就是对Object类型的一个动态数组就行操作，而LinkList则是对一个链表进行各种操作，**

**而两个类均是实现List这个接口，以及AbstractList这个抽象类。**

**对于LinkList和ArrayList，ArrayList本身是基于数组，因此，在内存方面占用的空间应该会大一些，**

**而对应的LinkList基于链表，内存空间占用会小一点，但在查询数据方面，数组的效率明显要高于链表，**

**因此，ArrayList在查询元素方面会比LinkList快。**

**对ArrayList和LinkList的分析，就是如此。**

[view plain]: http://blog.csdn.net/u012734441/article/details/43342831#
[Center]: /images/20220717/296a4c4966ad418886951dd575704ff6.png
[Center 1]: /images/20220717/d89bec6828e445f283f72626879ca732.png
[Center 2]: /images/20220717/66aaa2b794bf47b2b63f14360332cca7.png
[Center 3]: /images/20220717/68ed745ed68a4106baa80d536662440e.png
[Center 4]: /images/20220717/3e170789b7f6473c8d3843d56f194e56.png
[Center 5]: /images/20220717/f8da8af4d1f64829ad3695be646feccd.png
[Center 6]: /images/20220717/2832066a4d7c411db251ac37979e6439.png
[Center 7]: /images/20220717/f3aac39030c047f5a18fac26b3ffec10.png
[Center 8]: /images/20220717/78cc8c47e9184d9891f45a80e56b8a3a.png
[Center 9]: /images/20220717/975bbcb90b0345ad9bd5ca66b0976018.png
[Center 10]: /images/20220717/30cbcd67ca174487b020028c15d6a3dd.png
[Center 11]: /images/20220717/fd51b2ebb7b343149bfe63aee9711a60.png
[Center 12]: /images/20220717/2f1351829de743919ceb5bbbc1851da4.png
[Center 13]: /images/20220717/7290bf9c18924c839d3deab368e125df.png
[Center 14]: /images/20220717/440e39dfc5eb40258b77c71f9c5a11a3.png
[Center 15]: /images/20220717/2e1101b3126c47a8a7138cb7a9fde4df.png
[Center 16]: /images/20220717/0d1547442dd641b6b240d5f44d55ad49.png
[Center 17]: /images/20220717/1ba2fa53f7eb49a4af71077854497faa.png
[Center 18]: /images/20220717/61f1eb16d7f84d37936be402f8939e36.png
[Center 19]: /images/20220717/101ff6980cea4300b46923242e369f6e.png
[Center 20]: /images/20220717/2aa0fb71a7b54ab28719ae1fc4293533.png
[Center 21]: /images/20220717/00162d8fb10044ff9a70b16a82b63c51.png
[Center 22]: /images/20220717/f015b2b73b614ec7b973373d98c9a248.png