序言
在我们的日常编码中，ArrayList、LinkedList、Vector 这三个是我们经常使用的几个集合，通常，我们会定义一个ArrayList类来存储一个对象的集合，那么 ，他和数组之间有什么不同呢，我们知道，ArrayList和LinkedList之间，当我们在不考虑线程安全情况下，我们通过是要做频繁的操作还是对的数据频繁的查找速度来判断是否采用哪个合适，这又是为什么呢，在多线程的情况下，为什么说ArrayList线程不安全呢， 接下来，带着这些问题， 我将带着大家从源码角度逐步分析，慢慢揭开他们神秘的面纱。
集合关系图
我们看这样一幅简图， 图中我们可以看出三者关系，ArrayList，Vector和LinkedList分别继承AbstractListList和AbstractSequentialList ，三者都实现了List接口。 在继续之前，我们先来学习些基础的位运算知识吧
ArrayList和Vector
平时，我们在使用ArrayList时候，我们可以常使用 add方法，可get方法，remove方法，等来操作ArrayList的数据。此处 ，我们可以采用数组模拟这样一个集合。如下虽然游标位置有所不同但确实实现了类似arraylist的效果。
/**
* @author zhangzt
*/
public class MyArrayList {
//初始化一个大小为10的数组
MyArrayList(){
data=new Object[10];
}
//数据的集合
Object[] data;
//MyArrayList的大小 int默认值为0
int size;
//添加数据
public void add(Object obj)
{
//判断要插入数据是否满足data数组的大小 不满足需要自动扩容
int temp =size+1;
if(temp>data.length)// 判断范围
{
//扩容
copy(data,data.length*2);
}
//满足条件就把数据插入数组
data[size++]=obj;
}
//获取指定位置的数据
public Object get(int index)
{
if(index<=size) {
return data[index-1];
}else {return null;}
}
//移除指定位置的数据
public boolean remove(int index)
{
if(index<=size){ // 判断是否在MyArrayList 大小范围里
data[index-1]=null;
for(int i=index-1;i<data.length;i++)
{
data[i]=i+1>=data.length?null:data[i+1];
}
size--;
return true;
}else
{
return false;
}
}
//复制数组到新数组
private void copy(Object[] olddata, int i) {
if (olddata != null && i > olddata.length) {
Object[] newdata = new Object[i];
for (int j = 0; j < olddata.length; j++) {
newdata[j] = olddata[j];
}
data = newdata;
}
}
}
class MyArrayListTest{
public static MyArrayList myArrayList = new MyArrayList();
public static void main(String[] args) {
myArrayList.add("11");
myArrayList.add("12");
myArrayList.add("13");
myArrayList.add("14");
myArrayList.add("15");
System.out.println(myArrayList.size);
System.out.println("第一个元素"+myArrayList.get(1));
System.out.println( "第二个元素"+myArrayList.get(2));
myArrayList.remove(1);
System.out.println("第一个元素"+myArrayList.get(1));
////////////////////////////////////////////////////////
ArrayList<String> arrayList= new ArrayList<>();
arrayList.add("11");
arrayList.add("12");
arrayList.add("13");
arrayList.add("14");
arrayList.add("15");
System.out.println(arrayList.size());
System.out.println("第一个元素"+arrayList.get(1));
System.out.println( "第二个元素"+arrayList.get(2));
arrayList.remove(1);
System.out.println("第一个元素"+arrayList.get(1));
}
}
接下来我们看下在真正的Arraylist中是如何实现的。首先我们可以看到他有很多的成员变量，其中最为重要的就是elementData和size 分别表示存储的数据和大小。
/**
* Default initial capacity.
* 默认初始化的容量大小
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* Shared empty array instance used for empty instances.
* 为 ArrayList(int initialCapacity) 分配一个空数组
*/
private static final Object[] EMPTY_ELEMENTDATA = {};
/**
* Shared empty array instance used for default sized empty instances. We
* distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
* first element is added.
*为ArrayList()分配一个空数组 通过当第一次add()时扩容来区分EMPTY_ELEMENTDATA
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
* The array buffer into which the elements of the ArrayList are stored.
* The capacity of the ArrayList is the length of this array buffer. Any
* empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
* will be expanded to DEFAULT_CAPACITY when the first element is added.
*任何一个ArrayList都用它存储，他的容量就是ArrayList的容量，任何一个ArrayList
*的elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA 当第一次add()时
*将扩容到DEFAULT_CAPACITY（10）
*/
transient Object[] elementData; // non-private to simplify nested class access
/**
* The size of the ArrayList (the number of elements it contains).
* ArrayList的大小
* @serial
*/
private int size;
*NOTE: transient 表示成员变量不参与序列化过程。
*NOTE: 声明的变量是临时变量是不会初始化的，只有类的成员变量才会被初始化 eg：ArrayList的size 全局默认为0
/**
* Appends the specified element to the end of this list.
* 追加明确的元素到list最后
* @param e element to be appended to this list
* @return <tt>true</tt> (as specified by {@link Collection#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) {//判断是不是初始那个数组（第一次add）
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;
//假设旧的大小为10
int newCapacity = oldCapacity + (oldCapacity >> 1);
//10>>1 10 右移 1
// 1010 --> 0101 -->5 十进制
//扩容后的为10 + 5 =15 扩容到15 原来的1.5倍
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);//数组复制
//Arrays.copyof 最终调用System.arraycopy 这是个native方法
//所有他会调用底层c++ 的 复制方法把一个数组向另一个数组复制
}
public static void arraycopy(Object src,int srcPos,Object dest, int destPos,int length)
/*
*Object src：源数组
*int srcPos：源数组下标
*Object dest：目标数组
*int destPos：目标数组下标
*int length：复制的长度
*
*/
接下来我们看get和remove方法
//获取指定位置元素
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
//移除指定位置元素 返回指定位置的旧值
public E remove(int index) {
rangeCheck(index);
modCount++;//迭代器使用暂不考虑
E oldValue = elementData(index);//获得旧值
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);//将自己的被删除位置向前复制一个位置，复制numMoved长度
elementData[--size] = null; // 置为null触发GC
return oldValue;
}
//校验移除的值是否是list的范围里
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
//和删除同理
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++;
}
看到这可能有很多让人会问他和数组间到底有啥区别呢，就我个人理解他们的区别在于数组的灵活性没有ArrayList高，如果你想在数组的指定位置插入数据将会非常的麻烦，而且我们知道，要声明一个数组就需要指定数组的大小，那么我们无法准确的确定这个值到底应该是多大，所有就可能会出现不够用，或浪费内存的问题，而ArrayList的自动扩缩容解决了这个问题。使之更加灵活，但相对数组会有微量的性能的牺牲。
接着，我们查看Vector的源码，我们看到，他和ArrayList拥有类似的方法，唯一较为特别的地方就是每个方法上都拥有synchronized关键字，他表示这个方法是同步的，，这时就涉及到了在多线程的环境下，为什么说ArrayList是不安全的，Vector是安全的，我们回看ArrayList的add方法，我们注意到，集合大小的增加采用size++ 的方式，size++表示我们首先要先将size加载到内存中，然后在执行加操作，也就是说这不是个原子性的操作，例如，启动了2个线程，线程A先把size加载到工作内存中，线程B也把size加载到工作内存中，当A执行完毕返回后，由于B线程中所使用的并不是A加完之后的结果，所有会导致，A线程添加的数据会被B线程替换掉，导致数据错乱，产生非常严重的后果。在Vector中，add方法被synchronized修饰，通过锁保证了size++的原子性，表示当A 正在执行的时候，B是不可以执行add操作的，会在add方法上添加monitorenter 和monitorexit 阻塞B的执行,B等待A执行完毕后再次执行add的操作。
public synchronized boolean add(E e) {
modCount++;
ensureCapacityHelper(elementCount + 1);
elementData[elementCount++] = e;
return true;
}
LinkedList
linkedlist由一个双向链表组成，他的每个节点包含指向它上一个的节点和指向下一个的节点。他与Arraylist不同，并非由连续的内存组成。LinkedList初始化可通过 LinkedList() 和LinkedList(Collection<? extends E> c) 两种方式，两种方式都没有初始化LinkedList大小的方法。说明LinkedList自动扩展大小的。
//LinkedList大小
transient int size = 0;
/**
指向第一个元素
* Pointer to first node.
* Invariant: (first == null && last == null) ||
* (first.prev == null && first.item != null)
*/
transient Node<E> first;
/**指向最后一个元素
* Pointer to last node.
* Invariant: (first == null && last == null) ||
* (last.next == null && last.item != null)
*/
transient Node<E> last;
/**初始化一个空的list
* Constructs an empty list.
*/
public LinkedList() {
}
/**通过一个特殊的集合构建一个list
* Constructs a list containing the elements of the specified
* collection, in the order they are returned by the collection's
* iterator.
*
* @param c the collection whose elements are to be placed into this list
* @throws NullPointerException if the specified collection is null
*/
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
public boolean addAll(Collection<? extends E> c) {
return addAll(size, c);
}
public boolean addAll(int index, Collection<? extends E> c) {
checkPositionIndex(index);
Object[] a = c.toArray();
int numNew = a.length;
if (numNew == 0)
return false;
Node<E> pred, succ;
if (index == size) {//如果要添加的位置和集合大小相同 则从last开始添加新节点
succ = null;
pred = last;
} else { //否则从指定节点开始
succ = node(index);
pred = succ.prev;
}
//遍历用来构建的集合转成的数组
for (Object o : a) {
@SuppressWarnings("unchecked") E e = (E) o;
Node<E> newNode = new Node<>(pred, e, null);
if (pred == null)
first = newNode;
else
pred.next = newNode; //pred（最后一个节点或指定节点的的上一个节点）的下一个节点是新节点
pred = newNode;//修改为新节点 用于数组中下一个节点的添加时从新结点开始
}
if (succ == null) {
last = pred;
} else {
pred.next = succ; //数组中的节点连接完成后 将最后一个节点连接到查找到的节点
succ.prev = pred; //查找到的节点的上一个节点连接为新节点
}
size += numNew;//原集合大小+数组大小
modCount++;
return true;
}
//校验索引是一个大于等于0 且在list范围内 的数
private void checkPositionIndex(int index) {
if (!isPositionIndex(index))
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private boolean isPositionIndex(int index) {
return index >= 0 && index <= size;
}
//查找节点 判断索引位置 小于一半时从头开始遍历 反之从尾开始遍历
Node<E> node(int index) {
// assert isElementIndex(index);
// eg: 10 右移1 等于5
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
添加节点方法有 add(E e) ,add(int index, E element)，addAll(int index, Collection<? extends E> c)，addFirst(E e),addLast(E e) 几种，分别表示在集合最后添加一个节点，在指定位置添加节点，在指定位置添加一个集合，在list开头添加一个节点，和在list最后添加一个节点。 删除节点同理， 就是修改指向要删除节点的指针，并把要删除的节点置为null有利于GC回收， 以下是Linkedlist源码。
//创建新的节点，使它的下个节点为原来的frist节点，修改原来frist节点的prev节点为新节点
private void linkFirst(E e) {
final Node<E> f = first;
final Node<E> newNode = new Node<>(null, e, f);
first = newNode;
if (f == null)
last = newNode;
else
f.prev = newNode;
size++;
modCount++;
}
//创建新的节点，使他prev节点为原来的last节点，修改原来的last节点的next节点为新节点
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++;
}
void linkBefore(E e, Node<E> succ) {
// assert succ != null;
final Node<E> pred = succ.prev;//要插入节点的上一个节点
final Node<E> newNode = new Node<>(pred, e, succ); //创建新结点时上一个节点是pred 下一个节点是要插入的节点
succ.prev = newNode;//改要插入节点的上一个节点是新结点
if (pred == null)
first = newNode;
else
pred.next = newNode;//pred的下一个节点是新结点
size++;
modCount++;
}
public boolean add(E e) {
linkLast(e);
return true;
}
public void add(int index, E element) {
checkPositionIndex(index);//校验大于0 小于List大小
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
public void addFirst(E e) {
linkFirst(e);
}
public void addLast(E e) {
linkLast(e);
}
获取节点元素有getFirst()，getLast()，get(int index)，他们可以通过首尾位置遍历，查找到对应的节点并获得到相应的数据。
public E getFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return f.item;
}
public E getLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return l.item;
}
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
Linkedlist同时实现了Deque接口，表示他可以成为一个没有大小限制的队列或栈，我们知道，队列满足”先进先出”原则，而栈则是符合”后进先出 ，先进后出”原则，我们可以通过offer(E e) 和poll() 方法实现入队出队，可以用push(E e)和pop()来实现栈。
public boolean offer(E e) {
return add(e);//在队尾添加元素
}
public E poll() {
final Node<E> f = first;
return (f == null) ? null : unlinkFirst(f);//获取第一个节点的元素
}
private E unlinkFirst(Node<E> f) {
// assert f == first && f != null;
final E element = f.item;
final Node<E> next = f.next;
f.item = null;
f.next = null; // help GC
first = next;
if (next == null)
last = null;
else
next.prev = null;
size--;
modCount++;
return element;
}
public void push(E e) {
addFirst(e);
}
public E pop() {
return removeFirst();
}
回到问题中 ， 通过源码， 我们知道Arraylist是有数组实现， 是一块连续的内存空间，在查找指定元素时，通过索引就可以快速的取得，而当要扩展时，通过copy数组的方式来实现，而LinkedList则是由一个双向链表实现，当我们要查找指定元素是，需要遍历整个链表获取，但是 ，由于它是不连续的内存空间，当需要扩展是，只需要修改链表中节点的指针就可以实现。这就是Arraylist和linkedlist之间最本质的区别。