ArrayList和LinkedList的区别、扩容机制以及底层的实现方式

　　目录

　　ArrayList和LinkedList区别、扩容机制及底层实现

　　ArrayList

　　ArrayList的底层实现为数组存储在内存中，线程不同步。可通过数组下标的形式进行查找，所以在查询方面的效率较为出色，常用在查询较多的情景下。

　　LinkedList

　　LinkedList的底层实现为链表形式，也为线程不同步。而链表的底层也决定了它在查询方面不如数组底层的ArrayList而在指定位置插入等修改操作下，性能优于ArrayList。

　　Vestor

　　另外还有Vestor，Vestor也是和ArrayList、LinkedList一样实现了java.util.List接口。最大的区别在于Vestor是线程同步的，所以在效率方面不如另外两者，适用于多线程项目中。

　　ArrayList的扩容机制

　　/**

　　* Constructs an empty list with the specified initial capacity.

　　*/

　　public ArrayList(int initialCapacity) {

　　super();

　　if (initialCapacity < 0)

　　throw new IllegalArgumentException("Illegal Capacity: "+

　　initialCapacity);

　　this.elementData = new Object[initialCapacity];

　　}

　　/**

　　* Constructs an empty list with an initial capacity of ten.

　　*/

　　public ArrayList() {

　　this(10);

　　}

　　翻阅源码会发现ArrayList初始化如果不指定大小的时候 初始大小为10。

　　public void ensureCapacity(int minCapacity) {

　　modCount++;

　　int oldCapacity = elementData.length;

　　if (minCapacity > oldCapacity) {

　　Object oldData[] = elementData;

　　int newCapacity = (oldCapacity * 3)/2 + 1;

　　if (newCapacity < minCapacity)

　　newCapacity = minCapacity;

　　// minCapacity is usually close to size, so this is a win:

　　elementData = Arrays.copyOf(elementData, newCapacity);

　　}

　　}

　　扩容的规则也在源码中有体现，扩容后的大小= 原始大小+原始大小/2 + 1。在进行插入等操作的时候，如果判断出大小不够，会依据此方法进行扩容。(以上是JDK1.6版本的源码，在JDK1.7中扩容规则进行了修改，改为了扩容后的大小= 原始大小+原始大小/2)

　　LinkedList的扩容机制

　　由于它的底层是用双向链表实现的，没有初始化大小，也没有扩容的机制。

　　ArrayList和LinkedList（常用方法、底层结构及扩容机制）

　　1.ArrayList解说

　　ArrayList初始长度为0（这里以jdk1.8为例），是一个Object类型的空数组，如下

　　当第一次调用add后，长度变为10

　　当数组首次扩容的10个空间用完需要扩容后，会第二次走grow方法来扩容（每次扩容为1.5倍）

　　总的来说：

　　ArrayList初始大小为10，每次1.5倍进行扩容；它的底层是用数组实现的，所以查询速度相对LinkedList要快。

　　2.LinkedList解说

　　（1）

　　* LinkedList 是一个继承于AbstractSequentialList的双向链表。它也可以被当作堆栈、队列或双端队列进行操作。

　　* LinkedList 实现 List 接口，能对它进行队列操作。

　　* LinkedList 实现 Deque 接口，即能将LinkedList当作双端队列使用。

　　* LinkedList 实现了Cloneable接口，即覆盖了函数clone()，能克隆。

　　* LinkedList 实现java.io.Serializable接口，这意味着LinkedList支持序列化，能通过序列化去传输。

　　* LinkedList 是非同步的。

　　由于它的底层是用双向链表实现的，所以它对元素的增加、删除效率要比ArrayList好；它是一个双向链表，没有初始化大小，也没有扩容的机制，就是一直在前面或者后面新增就好。

　　（2）LinkedList底层的数据结构是基于双向循环链表的，且头结点中不存放数据,如下：

　　private transient Entry header = new Entry(null, null, null);

　　private transient int size = 0;

　　header是双向链表的头节点，它是双向链表节点所对应的类Entry的实例。Entry中包含成员变量： previous, next, element。其中，previous是该节点的上一个节点，next是该节点的下一个节点，element是该

　　节点所包含的值。size是双向链表中节点实例的个数。

　　总之，addBefore(E e,Entry entry)实现在entry之前插入由e构造的新节点。而add(E e)实现在header节点之前插入由e构造的新节点。为了便于理解，下面给出插入节点的示意图。

　　总结

　　以上为个人经验，希望能给大家一个参考，也希望大家多多支持脚本之家。

　　您可能感兴趣的文章: