List接口常用实现类的特点和底层实现
List接口常用的实现类有3个:ArrayList、LinkedList、Vector。
那么它们的特点和底层实现有哪些呢?
ArrayList特点和底层实现
ArrayList底层是用数组实现的存储。
特点:查询效率高,增删效率低,线程不安全。我们一般使用它。
查看源码,我们可以看出ArrayList底层使用Object数组来存储元素数据。所有的方法,都围绕这个核心的Object数组来开展。
ArrayList是可以存放任意数量的对象,数组长度是有限的,那么是怎么实现的呢?
本质上就是通过定义新的更大的数组,将旧数组内容拷贝到新数组,来实现扩容。
ArrayList的Object数组初始化长度为10,如果我们存储满了这个数组,需要存储第11个对象,就会定义新的数组长度长度更大的数组,并将将原数组内容和新的元素一起加入到新数组中,源码中代码如下:
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);
}
}
LinkedList特点和底层实现
LinkedList底层用双向链表实现的存储。
特点:查询效率低,增删效率高,线程不安全。
双向链表也叫双链表,是链表的一种,它的每个数据节点中都有两个指针,分别指向前一个节点和后一个节点。 所以,从双向链表中的任意一个节点开始,都可以很方便地找到所有节点。
每个节点都应该有3部分内容:
class Node {
Node previous; //前一个节点
Object element; //本节点保存的数据
Node next; //后一个节点
}
我们查看LinkedList的源码,可以看到里面包含了双向链表的相关代码:
注:entry在英文中表示“进入、词条、条目”的意思。在计算机英语中一般表示“项、条目”的含义。
Vector向量
Vector底层用数组实现的List,相关的方法都加了同步检查,因此“线程安全,效率低”。 比如,indexOf方法就增加了synchronized同步标记。
【图3】Vector的源码(indexOf方法)
建议
如何选用ArrayList、LinkedList、Vector?
·线程安全时,用Vector。
· 局部变量不存在线程安全问题时,并且查找较多用ArrayList(一般使用它)
·局部变量不存在线程安全问题时,增加或删除元素较多用LinkedList。