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。