11.ArrayList和LinkedList的区别？

ArrayList是java下的一个常见的数据结构，用于存放数据的。继承了AbstractList类，实现了List接口。
我们先从他的源码分析起：

成员变量

transient Object[] elementData; // non-private to simplify nested class access

    /**
     * The size of the ArrayList (the number of elements it contains).
     *
     * @serial
     */
private int size;

它的底层是基于数组的一个数据结构，大小是通过动态扩容动态变化的，一开始的默认大小是10。

/**
     * Default initial capacity.
     */
private static final int DEFAULT_CAPACITY = 10;

其实是因为一开始创建的时候，创建了一个空的数组，在第一次添加元素的时候，给他了一个初始的默认大小。

public ArrayList(int initialCapacity) {
	if (initialCapacity > 0) {
	    this.elementData = new Object[initialCapacity];
	} else if (initialCapacity == 0) {
	    this.elementData = EMPTY_ELEMENTDATA;
	} else {
	    throw new IllegalArgumentException("Illegal Capacity: "+
		                               initialCapacity);
	}
}

构造方法

public ArrayList(Collection<? extends E> c) {
	elementData = c.toArray();
	if ((size = elementData.length) != 0) {
	    // c.toArray might (incorrectly) not return Object[] (see 6260652)
	    if (elementData.getClass() != Object[].class)
		elementData = Arrays.copyOf(elementData, size, Object[].class);
	} else {
	    // replace with empty array.
	    this.elementData = EMPTY_ELEMENTDATA;
	}
}

add方法

在调用add方法时，每次的size都会+1，当达到最大容量时，会自动将size扩容到原来的1.5倍，将原数组的元素复制到新数组中。

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);
}

ArrayList总结

ArrayList 底层基于数组实现容量大小动态可变。 扩容机制为首先扩容为原始容量的 1.5 倍。如果1.5倍太小的话，则将我们所需的容量大小赋值给 newCapacity，如果1.5倍太大或者我们需要的容量太大，那就直接拿 newCapacity = (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE 来扩容。 扩容之后是通过数组的拷贝来确保元素的准确性的，所以尽可能减少扩容操作。 ArrayList 的最大存储能力：Integer.MAX_VALUE。 size 为集合中存储的元素的个数。elementData.length 为数组长度，表示最多可以存储多少个元素。 如果需要边遍历边 remove ，必须使用 iterator。且 remove 之前必须先 next，next 之后只能用一次 remove。

LinkedList：LinkedList继承于AbstractSequentialList，并且实现了Dequeue接口。但是他的本质是一个双向链表。

源码

transient int size = 0;

    /**
     * Pointer to first node.
     */
    transient Node<E> first;

    /**
     * Pointer to last node.
     */
    transient Node<E> last;

双链表（双向链表）：双链表和单链表相比，多了一个指向尾指针（tail），双链表的每个结点都有一个头指针head和尾指针tail,双链表相比单链表更容易操作，双链表结点的首结点的head指向为null，tail指向下一个节点的tail;尾结点的head指向前一个结点的head，tail
指向为null，是双向的关系；
在单链表中若需要查找某一个元素时，都必须从第一个元素开始进行查找，而双向链表除开头节点和最后一个节点外每个节点中储存有两个指针，这连个指针分别指向前一个节点的地址和后一个节点的地址，这样无论通过那个节点都能够寻找到其他的节点。

与ArrayList的一些差别：

1.ArrayList在随机访问方面比较擅长，LinkedList在随机增删方面比较擅长
2.对于需要快速插入，删除元素，使用LinkedList。因为ArrayList要想在数组中任意两个元素中间添加对象时，数组需要移动所有后面的对象。
3.对于需要快速随机访问元素（get()），应该使用ArrayList，因为LinkedList要移动指针、遍历节点来定位，所以速度慢。
4.对于“单线程环境” 或者 “多线程环境，但List仅仅只会被单个线程操作”，此时应该使用非同步的类(如ArrayList)。
5.对于“多线程环境，且List可能同时被多个线程操作”，此时，应该使用同步的类(如Vector)。