ArrayList简介
ArrayList是list接口的可变数组的实现。与一般数组不同的是，它的容量可以动态增长。
ArrayList继承了AbstractList抽象类，实现了List，RandomAccess, Cloneable, java.io.Serializable接口，根据实现的接口看，它支持随机访问，支持克隆，支持序列化。
Arraylist的特点：1）保证元素按照规定的顺序排列--元素的输出顺序和输入顺序一致；2）可快速随机访问；3）元素可以为null
插播一下
RandomAccess接口是一个标记接口（marker），它没有任何方法，被list的子类使用，如果list的子类实现了此接口，则代表它可以快速随机访问存储的元素.
他的意义在于当要实现某些算法时，会判断当前类是否实现了RandomAccess接口,会根据结果选择不同的算法.例如：
public static void shuffle(List<?> var0, Random var1) {
int var2 = var0.size();
if (var2 >= 5 && !(var0 instanceof RandomAccess)) {
Object[] var6 = var0.toArray();
for(int var4 = var2; var4 > 1; --var4) {
swap(var6, var4 - 1, var1.nextInt(var4));
}
ListIterator var7 = var0.listIterator();
for(int var5 = 0; var5 < var6.length; ++var5) {
var7.next();
var7.set(var6[var5]);
}
} else {
for(int var3 = var2; var3 > 1; --var3) {
swap(var0, var3 - 1, var1.nextInt(var3));
}
}
}
View Code
jdk建议实现了RandomAccess接口的list遍历时使用loop去遍历，并未实现（例如LinkedList）的使用迭代器去遍历（因为效率原因，在最后我会测试完贴代码上来的）。
RandomAccess源码的注释里面都写了，啦啦啦：
/*
* Copyright (c) 2000, 2006, Oracle and/or its affiliates. All rights reserved.
* ORACLE PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*/
package java.util;
/**
* Marker interface used by <tt>List</tt> implementations to indicate that
* they support fast (generally constant time) random access. The primary
* purpose of this interface is to allow generic algorithms to alter their
* behavior to provide good performance when applied to either random or
* sequential access lists.
*
* <p>The best algorithms for manipulating random access lists (such as
* <tt>ArrayList</tt>) can produce quadratic behavior when applied to
* sequential access lists (such as <tt>LinkedList</tt>). Generic list
* algorithms are encouraged to check whether the given list is an
* <tt>instanceof</tt> this interface before applying an algorithm that would
* provide poor performance if it were applied to a sequential access list,
* and to alter their behavior if necessary to guarantee acceptable
* performance.
*
* <p>It is recognized that the distinction between random and sequential
* access is often fuzzy. For example, some <tt>List</tt> implementations
* provide asymptotically linear access times if they get huge, but constant
* access times in practice. Such a <tt>List</tt> implementation
* should generally implement this interface. As a rule of thumb, a
* <tt>List</tt> implementation should implement this interface if,
* for typical instances of the class, this loop:
* <pre>
* for (int i=0, n=list.size(); i < n; i++)
* list.get(i);
* </pre>
* runs faster than this loop:
* <pre>
* for (Iterator i=list.iterator(); i.hasNext(); )
* i.next();
* </pre>
*
* <p>This interface is a member of the
* <a href="{@docRoot}/../technotes/guides/collections/index.html">
* Java Collections Framework</a>.
*
* @since 1.4
*/
public interface RandomAccess {
}
View Code
每个ArrayList实例都有一个容量，该容量是指用来存储列表元素的数组的大小。它总是至少等于列表的大小。随着向ArrayList中不断添加元素，其容量也自动增长。自动增长会带来数据向新数组的重新拷贝，因此，如果可预知数据量的多少，可在构造ArrayList时指定其容量。但是扩容这个操作不是同步的，所以不要在并发情况下使用ArrayList啊，如果多个线程都在改它的结构（数量发生变化，一会多了，一会少了）的话，那么恭喜你，你的代码要崩掉了。并发情况下可以用vector，CopyOnWriteArrayList（建议使用），或者你就想用ArrayList，这样也可以的：
List list = Collections.synchronizedList(new ArrayList(...));
ArrayList源码解析（jdk版本1.8.0_144）
1）几个比较不对很重要的初始化的值
private static final int DEFAULT_CAPACITY = 10;//默认的大小
private static final Object[] EMPTY_ELEMENTDATA = {};//空数组
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA {};
//没有给定size的时候，构造方法就默认给这个啦，默认大小是10
transient Object[] elementData; // 数据就是在这个数组里面村的
private int size;//list的大小啦
View Code
其中最最重要的两个对象：
elementData 是"Object[] 类型的数组"，它保存了添加到ArrayList中的元素。实际上，elementData是个动态数组，我们能通过构造函数 ArrayList(int initialCapacity)来执行它的初始容量为initialCapacity；如果通过不含参数的构造函数ArrayList()来创建 ArrayList，则elementData的容量默认是10。elementData数组的大小会根据ArrayList容量的增长而动态的增长。
size 则是动态数组的实际大小
2）构造方法
ArrayList提供了三种构造器：
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);
}
}
/**
* Constructs an empty list with an initial capacity of ten.
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
/**
* 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 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;
}
}
1）自己指定大小
2）不指定大小，默认给一个，默认值为10（第一次添加元素的时候，设置的size为默认大小10）
3）构造一个指定初始容量的空列表以及构造一个包含指定collection的元素的列表
ArrayList时怎么构造一个默认初始容量为10的空列表：
初始情况：elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}； size = 0;
当向数组中添加第一个元素时，通过add(E e)方法中调用的ensureCapacityInternal(size + 1)方法，即ensureCapacityInternal(1)；
在ensureCapacityInternal(int minCapacity)方法中，可得的minCapacity=DEFAULT_CAPACITY=10，然后再调用ensureExplicitCapacity(minCapacity)方法，即ensureExplicitCapacity(10)；
在ensureExplicitCapacity(minCapacity)方法中调用grow(minCapacity)方法，即grow(10)，此处为真正具体的数组扩容的算法，在此方法中，通过**elementData = Arrays.copyOf(elementData, 10)**设置了默认的初始大小10.
所以如果你没有定义arrayList的大小的话，他在第一次添加元素的时候，调用了给list调整大小的方法grow()，给list设置了默认大小10.具体还是不太明白为啥的，再本地debug仔细看下最好了，我也是debug看的。
3）扩展容量
我们经常说数据和arrayList有啥区别，会说数组的容量时固定的，不可变的；arrayList可以动态调整大小 。
那arrayList时如何调整大小呢？
请看源码：
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()方法举个栗子哈，addAll()同理。
从以上源码可以看出，每当向数组中添加元素时，都要去检查添加元素后的个数是否会超出当前数组的长度，如果超出，数组将会进行扩容，以满足添加数据的需求。数组扩容实质上是通过私有的方法ensureCapacityInternal(int minCapacity) -> ensureExplicitCapacity(int minCapacity) -> grow(int minCapacity)来实现的。看代码也可以看出来，扩容了1.5倍啦。
Vector
Vector就不多说了，因为它其实就跟arrayList差不多啦，就时一个同步的arrayList，可以再并发情况下使用，来看看源码：
public synchronized boolean add(E e) {
modCount++;
ensureCapacityHelper(elementCount + 1);
elementData[elementCount++] = e;
return true;
}
用add()方法举个栗子，其实很多方法都加入了synchronized同步语句，来保证线程安全。但是我很少见到有人使用vector的，因为再并发下，效率确实不怎么高。如果有并发的需求，可以用之前提到CopyOnWriteArrayList。
LinkedList简介
LinkedList基于链表（双端链表）实现，删除和插入操作速度快于arrayList，但也是因为基于链表，所以不支持随机访问，查询速度比arrayList慢。
LinkedList继承AbstractSequentialList类，实现了List，Deque，Cloneable, java.io.Seriaizable接口。
LinkedList源码解析（jdk版本1.8.0_144）
transient int size = 0;
transient Node<E> first;
transient Node<E> last;
size代表的时链表的长度，也就是list的大小了；两个变量，first指向链表头部，last指向链表尾部。
再看一下Node的定义：
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;
}
}
很明显可以看出来这是一个双端链表了，分别保存了对上一个节点及下一个节点的引用。
再看几个常用的方法：
1，添加操作。
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);//以当前的尾部节点为新节点的pre，创建新节点。
last = newNode;//将链表尾部指向新节点
if (l == null)//如果链表为空，那么新节点是头节点也是尾节点
first = newNode;
else//链表不为空，那么将该结点作为原链表尾部的next
l.next = newNode;
size++;
modCount++;
}
2，在指定位置添加元素
public void add(int index, E element) {
checkPositionIndex(index);//检查index时否合法
if (index == size)//如果index等于size，那就添加到尾部
linkLast(element);
else
linkBefore(element, node(index));//否则就往中间插入啦
}
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);
succ.prev = newNode;
if (pred == null)
first = newNode;
else
pred.next = newNode;
size++;
modCount++;
}
Node<E> node(int index) {
// assert isElementIndex(index);
//如果index位置在链表前半部分，从头开始遍历，否则，从尾部开始遍历
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;
}
}
3，获取指定索引的数据
public E get(int index) {
checkElementIndex(index);//检查索引是否合法
return node(index).item;//查找数据
}
这就是为啥说linkedList查找数据慢了，它是用链表实现的，不像数组有索引标识，所以当然慢啊。
好了就这么多吧，举几个栗子就行，我这一篇都写了好久了，快懒死我了，写完我好写别的啊。
我不是大神啊，如果有人不小心看到我的文章，觉得我说得不对，大家就提出来啊，别骂我啊。
