java数据结构之List（列表）

List列表允许存储相同元素，插入元素和按照下标获取元素方便，具体实现有ArrayList，LinkedList和Vector，

ArrayList底层基于数组实现的，按顺序存储元素以及快速按照元素下标进行获取元素，不可同步的；

而Vector底层也是数组，可进行同步操作，在多线程环境下可以使用；

LinkedList链表的具体机制如下图：可以在具体下标位置删除和添加元素，在许多需要根据具体下标添加和删除元素的应用场景下比ArrayList有更好的性能。

LinkedList

ArrayList和Vector的部分源码分析：

//ArrayList的add()方法

public boolean add(E e) {

ensureCapacityInternal(size + 1); // Increments modCount!!

//在数组结尾下标添加元素

elementData[size++] = e;

return true;

}

//ArrayList的remove()方法

public E remove(int index) {

rangeCheck(index);

modCount++;

E oldValue = elementData(index);

//获取移动的元素的个数

int numMoved = size – index – 1;

if (numMoved > 0)

//将移除元素的下标位置后的数组元素都往前移一位来填补空位，调用System.arraycopy方法调用虚拟机自带的方法进行操作效率更高

System.arraycopy(elementData, index+1, elementData, index,

numMoved);

elementData[–size] = null; // clear to let GC do its work

return oldValue;

}

//Vector添加了synchronized 进行同步

public synchronized void addElement(E obj) {

modCount++;

ensureCapacityHelper(elementCount + 1);

elementData[elementCount++] = obj;

}

综上：Array List在不需要同步操作及不需要频繁删除任意下标的元素时推荐使用，Vector是在同步场景下使用，LinkedList是在需要频繁删除和添加任意下标的元素时使用