上海人物摄像交流群

JDK源码学习之Arraylist与LinkedList

只看楼主 收藏 回复
  • - -
楼主


ArrayList和LinkedList是我们在开发过程中常用的两种集合类,本文将从底层源码实现对其进行简单介绍。


下图是Java集合类所涉及的类图。




一.ArrayList


从上面的集合类图可以看出,ArrayList实现了List接口。ArrayList是顺序的集合容器,容器中可以存放null元素,而底层则是通过一个可自动增长大小的动态数组实现的。ArrayList不是线程安全的,也没有实现同步


1.1 ArrayList操作性能


访问数组中第 n 个数据的时间花费是 O(1) ,但是要在数组中查找一个指定的数据则是 O(N)。当向数组中插入或者删除数据的时候,最好的情况是在数组的末尾进行操作,时间复杂度是 O(1),但是最坏情况是插入或者删除第一个数据,时间复杂度是O(N)。在数组的任意位置插入或者删除数据的时候,后面的数据全部需要移动,移动的数据还是和数据个数有关所以总体的时间复杂度仍然是O(N)




1.2 私有属性


ArrayList有两个私有属性,一个是实现数据存储的数组,一个是表示数组中元素的个数。值得注意的是关键字transient




ArrayList这个类实现了Serializable接口。Java的Serializable提供了一种持久化对象实例的机制,当持久化对象时,可能某个特殊的对象数据成员我们不想让其用Serializable机制保存它,可以使用关键字transient进行屏蔽。此外还有个保护的属性:modCount,含义为已从结构上修改此列表的次数。从结构上修改是指更改列表的大小,或者打乱列表,从而使正在进行的迭代产生错误的结果。


1.3 构造方法


ArrayList中有三个构造函数,一个是默认构造一个容量为10的数组,一个指定容量的空列表和一个Collection类型的空列表。我们可以在使用时通过指定我们预估到的数组容量,来减少扩容次数


1.4 数组扩容


每一个ArrayList的实例都有一个容量,用来表示存储数据的数组大小。容器内的元素不能大于当前当前的容器大小。当向容器中添加数据时,若容器的容量不足,容器会自动扩容。通过对比jdk1.7的ArrayList源码发现,扩容两个方法是不一样的,jdk1.6中使用的是除法对其容量进行计算(加0.5倍),而jdk1.7中则使用的是移运算。 




位运算是CPU直接操作的,除法等四则运算都是基于移位运算的,所以当有大量计算的时候,移位运算可以大大节约CPU的时间。通过1千万次位运算和四则运算做对比数据结果如下:


    


可以看出,在计算大量数据的情况下,移位运算的花费时间比乘除法快很多。


1.5 数组复制方法




可以看到在ensureCapacity(intminCapacity)中调用的是Arrays的copyOf()方法,而在add方法中,调用的数组复制方法为:


native void arraycopy();Arrays的copyOf方法的实现:




实现copyOf的时候会新创建一个大小为newCapcity的数组,然后将旧的elementData放入其中。


1.6 小节


1、通过查看ArrayList的源码,注意到有三个不同的构造方法,合理使用构造方法能减少数组扩容拷贝造成的额外开销。


2、ArrayList大量调用了Arrays.copyOf和System.arrayCopy的方法,注意这两个方法的区别。


3、jdk1.6和1.7中数组扩容的方法不一致,注意比较有差异的地方。


二.LinkedList




LinkedList与ArrayList一样实现List接口,只是ArrayList是List接口的大小可变数组的实现LinkedList是List接口链表的实现。基于链表实现的方式使得LinkedList在插入和删除时更优于ArrayList,而随机访问则比ArrayList逊色些


除了实现 List 接口外,LinkedList类还实现 Deque接口,为 add、poll 提供先进先出队列操作,以及其他堆栈和双端队列操作


LinkedList定义:

public class LinkedList<E > extends AbstractSequentialList<E>

    implements List<E>,Deque<E>, Cloneable, java.io.Serializable


2.1 底层数据结构


与ArrayList的区别在于,LinkedList底层是基于双向链表实现的:




以上的数据结构可以从LinkedList的私有属性看出:

private transient Entry<E> header = newEntry<E>(null, null, null);//头结点是不存放元素的

private transient int size = 0;//双向循环链表的大小


2.2 双向循环列表的操作性能


对于双向循环链表的插入和删除操作只是多移动几个指针。




备注:这里只是单纯的描述双向链表这种数据结构的插入和删除性能,下文将对比ArrayList与LinkedList的性能。


2.3 构造函数


LinkedList类有两个构造函数,一个是无参数的,一个是构造任意类型的集合类的列表




该构造函数构造一个空的列表,header头结点表示如下, 形成一个闭环。




有参构造方法,参数为collection的c,this()调用默认的无参构造函数,然后再调用addAll()方法,将c中的元素添加加入列表。



三.LinkedList与ArrayList比较


1.ArrayList是基于数组的数据结构,LinkedList是基于链表的数据结构。


2.ArrayList内部的元素可以直接通过get与set方法进行访问,因为ArrayList本质上就是一个数组.但LinkedList在get与set方面弱于ArrayList.


当然,这些对比都是指数据量很大或者操作很频繁的情况下的对比,如果数据和运算量很小,那么对比将失去意义.


3.此外 LinkedList 还实现了 Queue 接口,该接口比List提供了更多的方法,包括 offer(),peek(),poll()等.


注意: 默认情况下ArrayList的初始容量非常小,所以如果可以预估数据量的话,分配一个较大的初始值属于最佳实践,这样可以减少调整大小的开销。


4.对于ArrayList与LinkedList性能下图做个简单比较




* 表中的 add() 代表 add(E e),而 remove()代表 remove(int index)


ArrayList 对于随机位置的add/remove,时间复杂度为 O(n),但是对于列表末尾的添加/删除操作,时间复杂度是 O(1). 而LinkedList对于随机位置的add/remove,时间复杂度为 O(n),但是对于列表 末尾/开头 的添加/删除操作,时间复杂度是 O(1).


下面是测试代码:






输出结果截图如下:




上述测试可以看出LinkedList在 进行add和remove操作时更快,而在进行get操作时较慢.  

通过本次源码学习之旅,我从LinkedList、ArrayList的底层结构出发,更深刻地了解了这两个类的一些基本操作方法,文章中有不周全的地方欢迎指正,共同学习。



我们是

58招聘技术 

在这里

有我们的技术实践

我们探索新技术

带给你不一样的收获



58招聘



举报 | 1楼 回复

友情链接