Java 集合 1：Collection，List，ArrayList，Vector，LinkedList（实现方式，对比）

Collection 与 List

Collection 是 Java 集合的一个根接口，JDK 没有它的实现类。内部仅仅做 add()，remove()，contains()，size() 等方法的声明。

List 接口是Collection 接口的一个子类，在Collection 基础上扩充了方法。同时可以对每个元素插入的位置进行精确的控制，它的主要实现类有 ArrayList，Vector，LinkedList。

这里需要注意的是，List 接口的实现类

插入的值允许为空，也允许重复。
插入的值允许为空，也允许重复。
插入的值允许为空，也允许重复。

ArrayList

ArrayList 实现了 List 接口，意味着可以插入空值，也可以插入重复的值，非同步，它是基于数组的一个实现。

部分成员变量如下：

private static final int DEFAULT_CAPACITY = 10;                        //默认初始值 
transient Object[] elementData;                                        //存放数据的数组

这里可以看出，elementData 提示了是基于数组的实现， DEFAULT_CAPACITY 指名了默认容量为 10 个。

下面重点理解 add()方法，这将有助于理解 ArrayList 的应用场景和性能消耗：

add():

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
return true;
}

private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }

    ensureExplicitCapacity(minCapacity);
}

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

// overflow-conscious code
if (minCapacity - elementData.length > 0)
    grow(minCapacity);
}

private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity);
}

这里可以看到，进行一个 add()方法，首先通过 ensureCapacityInternal(size + 1); 判断需不需要扩容;然后再进行 elementData[size++] = e。插入的时间复杂度O(1)。是非常高效的。（But，这不是在固定位置插入的情况下），如果在固定位置插入，那么代码：

public void add(int index, E element) {
        rangeCheckForAdd(index);

        ensureCapacityInternal(size + 1);  // Increments modCount!!
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        elementData[index] = element;
        size++;
    }

System.arraycopy(elementData, index, elementData, index + 1, size - index); 这个可以看出，这时候就是比较低效的了。

那么网上很多说 ArrayList 不适合增删操作非常多的操作，这是怎么回事呢？首先可以看到这句话： elementData = Arrays.copyOf(elementData, newCapacity); 需要知道的是， Arrays.copyOf 函数的内部实现是再创建一个数组，然后把旧的数组的值一个个复制到新数组中。当经常增加操作的时候，容量不够的时候，就会进行上述的扩容操作，这样性能自然就下来了。或者说，当我们在固定位置进行增删的时候，都会进行 System.arraycopy(elementData, index, elementData, index + 1, size - index); 也是非常低效的。

分析了低效出现的原因，那么我们就可以知道：如果我们需要经常进行特定位置的增删操作，那么最好还是不要用这个了，但是，如果我们基本上没有固定位置的增删操作，最好是要预估数据量的大小，然后再初始化最小容量，这样可以有效的避免扩容。如下代码：

ArrayList arrayList = new ArrayList(20);

总结：

1、ArrayList 可以插入空值，也可以插入重复值
2、ArrayList 是基于数组的时候，所以很多数组的特性也直接应用到了 ArrayList。
3、ArrayList 的性能消耗主要来源于扩容和固定位置的增删。
4、ArrayList 创建的时候需要考虑是否要初始化最小容量，以此避免扩容带来的消耗。

Vector

上述的 ArrayList 不是线程安全的。那么 Vector 就可以看作是 ArrayList 的一个线程安全版本。由于也是实现了 List 接口，所以也是可以插入空值，可以插入重复的值。它和 HashTable 一样，是属于一种同步容器，而不是一种并发容器。（参考《Java并发编程实战》，类似CopyOnWriteArrayList，ConcurrentHashMap这种就属于并发容器）

内部成员变量：

protected Object[] elementData;
public Vector() {
this(10);
}

可以看到，也是基于数组的实现，初始化也是 10 个容量。那么，再来看看 add()方法是否和 ArrayList 相同。

public synchronized boolean add(E e) {
    modCount++;
    ensureCapacityHelper(elementCount + 1);
    elementData[elementCount++] = e;
return true;
}

可以看到，和 ArrayList 也是一样的，只是加了 synchronized 进行同步，其实很多其他方法都是通过加 synchronized 来实现同步。

总结：

1、可以插入空值，也可以插入重复值
2、也是基于数组的时候，所以很多数组的特性也直接应用到了 Vector。
3、性能消耗也主要来源于扩容。
4、创建的时候需要考虑是否要初始化最小容量，以此避免扩容带来的消耗。
5、相当于 ArrayList 的线程安全版本，实现同步的方式是通过 synchronized。

LinkedList

LinkedList 实现了 List 接口，所以LinkedList 也可以放入重复的值，也可以放入空值。LinkedList不支持同步。LinkedList 不同于ArrayList 和Vector，它是使用链表的数据结构，不再是数组。

成员变量：

transient int size = 0;    //数量 
transient Node<E> first;   //首节点 
transient Node<E> last;    //最后节点 

private static class Node<E> {    
    E item;    
    Node<E> next;    
    Node<E> prev;    
    Node(Node<E> prev, E element, Node<E> next) {    
this.item = element;    
this.next = next;    
this.prev = prev;    
    }    
}

那么，在进行 add() 方法的时候：

public boolean add(E e) {    
    linkLast(e);    
return true;    
}   
void linkLast(E e) {    
final Node<E> l = last;    
final Node<E> newNode = new Node<>(l, e, null);    
    last = newNode;    
if (l == null)    
        first = newNode;    
else    
        l.next = newNode;    
    size++;    
    modCount++;    
}

当进行增删的时候，只需要改变指针，并不会像数组那样出现整体数据的大规模移动，复制等消耗性能的操作。

ArrayList，Vector，LinkedList 的整体对比

实现方式：

1、ArrayList，Vector 是基于数组的实现。

2、LinkedList 是基于链表的实现。

同步问题：

1、ArrayList,LinkedList 不是线程安全的。

2、Vector 是线程安全的，实现方式是在方法中加 synchronized 进行限定。

适用场景和性能消耗

1、ArrayList 和 Vector 由于是基于数组的实现，所以在固定位置插入，固定位置删除这方面会直接是 O(n)的时间复杂度，另外可能会出现扩容的问题，这是非常消耗性能的。

2、LinkedList 不会出现扩容的问题，所以比较适合增删的操作。但是由于不是数组的实现，所以在定位方面必须使用遍历的方式，这也会有 O(n)的时间复杂度

秒客网

Java 集合 1：Collection，List，ArrayList，Vector，LinkedList（实现方式，对比）

相关文章