说说JDK中的List－ArrayList、Vector、LinkedList
添加时间:2013-8-12 点击量:
为便利开辟人员，JDK供给了一套首要数据布局的实现，比如List、Map等。今儿说说List接口。
List接口的一些列实现中，最常用最首要的就是这三个：ArrayList、Vector、LinkedList。
JDK中这三个类的定义：
public class ArrayList<E> extends AbstractList<E>
implements List<E>， RandomAccess， Cloneable， java.io.Serializable
public class Vector<E>
extends AbstractList<E>
implements List<E>， RandomAccess， Cloneable， java.io.Serializable
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>， Deque<E>， Cloneable， java.io.Serializable
从这三个类定义就可以看出一些信息：
- 三个都直接实现了AbstractList这个抽象类
- ArrayList和Vector都实现了RandomAccess接口，而LinkedList没有，这是什么意思呢？在JDK中，RandomAccess接口是一个空接口，所以它没有实际意义，就是一个标识表记标帜，标识表记标帜这个类支撑快速随机接见，所以，arrayList和vector是支撑随机接见的，然则LinkedList不支撑
- serializbale接口表名，他们都支撑序列化
下面具体说说这三个List实现。
这三个里面，ArrayList和Vector应用了数组的实现，相当于封装了对数组的操纵。这也恰是他们可以或许支撑快速随机接见的原因，多说一句，JDK中所有基于数组实现的数据布局都可以或许支撑快速随机接见。
ArrayList和Vector的实现上几乎都应用了雷同的算法，他们的首要差别就是ArrayList没有对任何一个办法做同步，所以不是线程安然的；而Vector中大项目组办法都做了线程同步，是线程安然的。
LinkedList应用的是双向轮回链表的数据布局。因为是基于链表的，所所以没法实现随机接见的，只能次序接见，这也正式它没有实现RandomAccess接口的原因。
正式因为ArrayList、Vector和LinkedList所采取的数据布局不合，注定他们实用的是完全不合的场景。
经由过程浏览这几个类的源码，我们可以看到他们实现的不合。ArrayList和Vector根蒂根基一样，我们就拿ArrayList和LinkedList做对比。
在末尾增长一个元素
ArrayList中的add办法实现如下：
1 public boolean add（E e） {
2 ensureCapacityInternal（size + 1）; // Increments modCount!!
3 elementData[size++] = e;
4 return true;
5 }
这个办法做两件工作，起首确保数组空间足够大，然后在数组末尾增长元素并且经由过程后++使得完成size+1。
从这个代码可以看出，若是数组空间足够大，那么只是数组的add操纵就是O（1）的机能，很是高效。
在看看ensureCapacityInternal这个办法的实现：
1 private void ensureCapacityInternal（int minCapacity） {
2 modCount++;
3 // overflow-conscious code
4 if （minCapacity - elementData.length > 0）
5 grow（minCapacity）;
6 }
7
8 private void grow（int minCapacity） {
9 // overflow-conscious code
10 int oldCapacity = elementData.length;
11 int newCapacity = oldCapacity + （oldCapacity >> 1）;
12 if （newCapacity - minCapacity < 0）
13 newCapacity = minCapacity;
14 if （newCapacity - MAX_ARRAY_SIZE > 0）
15 newCapacity = hugeCapacity（minCapacity）;
16 // minCapacity is usually close to size， so this is a win:
17 elementData = Arrays.copyOf（elementData， newCapacity）;
18 }
可以看出，若是数组空间不敷，那么这个办法就会做数组扩容和数组复制操纵，看第11行，JDK哄骗移位运算符进行扩容策画，>>1右移一位默示除2，所以newCapacity就是扩容为本来的1.5倍。
PS：这里的代码都是JDK1.7中的实现，JDK1.7对1.6的很多代码做了优化，比如上方这段扩容代码，在JDK1.6中第11行是直接除2，显然，移位运算要更高效。
在看看LinkedList中的add办法：
1 public boolean add（E e） {
2 linkLast（e）;
3 return true;
4 }
5
6 void linkLast（E e） {
7 final Node<E> l = last;
8 final Node<E> newNode = new Node<>（l， e， null）;
9 last = newNode;
10 if （l == null）
11 first = newNode;
12 else
13 l.next = newNode;
14 size++;
15 modCount++;
16 }
1 Node（Node<E> prev， E element， Node<E> next） {
2 this.item = element;
3 this.next = next;
4 this.prev = prev;
5 }
从这段add代码可以看出，LinkedList因为应用了链表，所以不须要进行扩容，直接把元素加到链表最后，把新元素的前驱指向之前的last元素，并把last元素指向新元素就ok。这也是一个O（1）的机能。
测试一下：
1 public static void main（String[] args） {
2 // TODO Auto-generated method stub
3 long begin = System.currentTimeMillis（）;
4
5 // List<Object> list = new ArrayList<Object>（）;
6 List<Object> list = new LinkedList<Object>（）;
7 Object obj = new Object（）;
8 for（int i=0; i<50000; i++）{
9 list.add（obj）;
10 }
11
12 long end = System.currentTimeMillis（）;
13 long time = end - begin;
14 System.out.println（time+）;
15
16 }
分别对ArrayList和LinkedList做末尾add操纵，轮回50000次，ArrayList耗时6ms，而LinkedList耗时8ms，这是因为LinkedList在add时辰须要更多的对象创建和赋值操纵。
在随便率性地位插入元素
ArrayList中的实现如下：
1 public void add（int index， E element） {
2 rangeCheckForAdd（index）;
3
4 ensureCapacityInternal（size + 1）; // Increments modCount!!
5 System.arraycopy（elementData， index， elementData， index + 1，
6 size - index）;
7 elementData[index] = element;
8 size++;
9 }
这段代码，起首先搜检数组容量，容量不敷先扩容，然后把index之后的数组往后挪一个，最后在index地位放上新元素。因为数组是一块连气儿内存空间，所以在随便率性地位插入，都邑导致这个厥后数组后挪一位的景象，须要做一次数组复制操纵，很明显，若是有多量的随机插入，那么这个数组复制操纵开销会很大，并且插入的越靠前，数组复制开销越大。
LinkedList中的实现：
1 public void add（int index， E element） {
2 checkPositionIndex（index）;
3
4 if （index == size）
5 linkLast（element）;
6 else
7 linkBefore（element， node（index））;
8 }
9
10 void linkBefore（E e， Node<E> succ） {
11 // assert succ != null;
12 final Node<E> pred = succ.prev;
13 final Node<E> newNode = new Node<>（pred， e， succ）;
14 succ.prev = newNode;
15 if （pred == null）
16 first = newNode;
17 else
18 pred.next = newNode;
19 size++;
20 modCount++;
21 }
这段代码，取到本来index处节点的前驱，变成新节点的前驱 ，同时把本来index变成新节点的后驱，如许就完成了新节点的插入。这个就是链表的上风，不存在数据复制操纵，机能和在最后插入是一样的。
测试一种极端景象，每次都在前端插入元素：
1 public static void main（String[] args） {
2 // TODO Auto-generated method stub
3 long begin = System.currentTimeMillis（）;
4
5 // List<Object> list = new ArrayList<Object>（）;
6 List<Object> list = new LinkedList<Object>（）;
7 Object obj = new Object（）;
8 for（int i=0; i<50000; i++）{
9 list.add（0，obj）;
10 }
11
12 long end = System.currentTimeMillis（）;
13 long time = end - begin;
14 System.out.println（time+）;
15
16 }
测试成果是：ArrayList耗时1400ms，而LinkedList只耗时12ms。可以看出，在随机插入的时辰，两者的机能差别就很明显了。
小结一下，从上方的源码解析和测试成果可以看出这三种List实现的一些典范实用处景，若是经常对数组做随机插入操纵，希罕是插入的斗劲靠前，那么LinkedList的机能上风就很是明显，而若是都只是末尾插入，则ArrayList更占领上风，若是须要线程安然，则非Vector莫属。
我们永远不要期待别人的拯救，只有自己才能升华自己。自己已准备好了多少容量，方能吸引对等的人与我们相遇，否则再美好的人出现、再动人的事情降临身边，我们也没有能量去理解与珍惜，终将擦肩而过。—— 姚谦《品味》
为便利开辟人员，JDK供给了一套首要数据布局的实现，比如List、Map等。今儿说说List接口。
List接口的一些列实现中，最常用最首要的就是这三个：ArrayList、Vector、LinkedList。
JDK中这三个类的定义：
public class ArrayList<E> extends AbstractList<E>
implements List<E>， RandomAccess， Cloneable， java.io.Serializable
public class Vector<E>
extends AbstractList<E>
implements List<E>， RandomAccess， Cloneable， java.io.Serializable
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>， Deque<E>， Cloneable， java.io.Serializable
从这三个类定义就可以看出一些信息：
- 三个都直接实现了AbstractList这个抽象类
- ArrayList和Vector都实现了RandomAccess接口，而LinkedList没有，这是什么意思呢？在JDK中，RandomAccess接口是一个空接口，所以它没有实际意义，就是一个标识表记标帜，标识表记标帜这个类支撑快速随机接见，所以，arrayList和vector是支撑随机接见的，然则LinkedList不支撑
- serializbale接口表名，他们都支撑序列化
下面具体说说这三个List实现。
这三个里面，ArrayList和Vector应用了数组的实现，相当于封装了对数组的操纵。这也恰是他们可以或许支撑快速随机接见的原因，多说一句，JDK中所有基于数组实现的数据布局都可以或许支撑快速随机接见。
ArrayList和Vector的实现上几乎都应用了雷同的算法，他们的首要差别就是ArrayList没有对任何一个办法做同步，所以不是线程安然的；而Vector中大项目组办法都做了线程同步，是线程安然的。
LinkedList应用的是双向轮回链表的数据布局。因为是基于链表的，所所以没法实现随机接见的，只能次序接见，这也正式它没有实现RandomAccess接口的原因。
正式因为ArrayList、Vector和LinkedList所采取的数据布局不合，注定他们实用的是完全不合的场景。
经由过程浏览这几个类的源码，我们可以看到他们实现的不合。ArrayList和Vector根蒂根基一样，我们就拿ArrayList和LinkedList做对比。
在末尾增长一个元素
ArrayList中的add办法实现如下：
1 public boolean add（E e） {
2 ensureCapacityInternal（size + 1）; // Increments modCount!!
3 elementData[size++] = e;
4 return true;
5 }
这个办法做两件工作，起首确保数组空间足够大，然后在数组末尾增长元素并且经由过程后++使得完成size+1。
从这个代码可以看出，若是数组空间足够大，那么只是数组的add操纵就是O（1）的机能，很是高效。
在看看ensureCapacityInternal这个办法的实现：
1 private void ensureCapacityInternal（int minCapacity） {
2 modCount++;
3 // overflow-conscious code
4 if （minCapacity - elementData.length > 0）
5 grow（minCapacity）;
6 }
7
8 private void grow（int minCapacity） {
9 // overflow-conscious code
10 int oldCapacity = elementData.length;
11 int newCapacity = oldCapacity + （oldCapacity >> 1）;
12 if （newCapacity - minCapacity < 0）
13 newCapacity = minCapacity;
14 if （newCapacity - MAX_ARRAY_SIZE > 0）
15 newCapacity = hugeCapacity（minCapacity）;
16 // minCapacity is usually close to size， so this is a win:
17 elementData = Arrays.copyOf（elementData， newCapacity）;
18 }
可以看出，若是数组空间不敷，那么这个办法就会做数组扩容和数组复制操纵，看第11行，JDK哄骗移位运算符进行扩容策画，>>1右移一位默示除2，所以newCapacity就是扩容为本来的1.5倍。
PS：这里的代码都是JDK1.7中的实现，JDK1.7对1.6的很多代码做了优化，比如上方这段扩容代码，在JDK1.6中第11行是直接除2，显然，移位运算要更高效。
在看看LinkedList中的add办法：
1 public boolean add（E e） {
2 linkLast（e）;
3 return true;
4 }
5
6 void linkLast（E e） {
7 final Node<E> l = last;
8 final Node<E> newNode = new Node<>（l， e， null）;
9 last = newNode;
10 if （l == null）
11 first = newNode;
12 else
13 l.next = newNode;
14 size++;
15 modCount++;
16 }
1 Node（Node<E> prev， E element， Node<E> next） {
2 this.item = element;
3 this.next = next;
4 this.prev = prev;
5 }
从这段add代码可以看出，LinkedList因为应用了链表，所以不须要进行扩容，直接把元素加到链表最后，把新元素的前驱指向之前的last元素，并把last元素指向新元素就ok。这也是一个O（1）的机能。
测试一下：
1 public static void main（String[] args） {
2 // TODO Auto-generated method stub
3 long begin = System.currentTimeMillis（）;
4
5 // List<Object> list = new ArrayList<Object>（）;
6 List<Object> list = new LinkedList<Object>（）;
7 Object obj = new Object（）;
8 for（int i=0; i<50000; i++）{
9 list.add（obj）;
10 }
11
12 long end = System.currentTimeMillis（）;
13 long time = end - begin;
14 System.out.println（time+）;
15
16 }
分别对ArrayList和LinkedList做末尾add操纵，轮回50000次，ArrayList耗时6ms，而LinkedList耗时8ms，这是因为LinkedList在add时辰须要更多的对象创建和赋值操纵。
在随便率性地位插入元素
ArrayList中的实现如下：
1 public void add（int index， E element） {
2 rangeCheckForAdd（index）;
3
4 ensureCapacityInternal（size + 1）; // Increments modCount!!
5 System.arraycopy（elementData， index， elementData， index + 1，
6 size - index）;
7 elementData[index] = element;
8 size++;
9 }
这段代码，起首先搜检数组容量，容量不敷先扩容，然后把index之后的数组往后挪一个，最后在index地位放上新元素。因为数组是一块连气儿内存空间，所以在随便率性地位插入，都邑导致这个厥后数组后挪一位的景象，须要做一次数组复制操纵，很明显，若是有多量的随机插入，那么这个数组复制操纵开销会很大，并且插入的越靠前，数组复制开销越大。
LinkedList中的实现：
1 public void add（int index， E element） {
2 checkPositionIndex（index）;
3
4 if （index == size）
5 linkLast（element）;
6 else
7 linkBefore（element， node（index））;
8 }
9
10 void linkBefore（E e， Node<E> succ） {
11 // assert succ != null;
12 final Node<E> pred = succ.prev;
13 final Node<E> newNode = new Node<>（pred， e， succ）;
14 succ.prev = newNode;
15 if （pred == null）
16 first = newNode;
17 else
18 pred.next = newNode;
19 size++;
20 modCount++;
21 }
这段代码，取到本来index处节点的前驱，变成新节点的前驱 ，同时把本来index变成新节点的后驱，如许就完成了新节点的插入。这个就是链表的上风，不存在数据复制操纵，机能和在最后插入是一样的。
测试一种极端景象，每次都在前端插入元素：
1 public static void main（String[] args） {
2 // TODO Auto-generated method stub
3 long begin = System.currentTimeMillis（）;
4
5 // List<Object> list = new ArrayList<Object>（）;
6 List<Object> list = new LinkedList<Object>（）;
7 Object obj = new Object（）;
8 for（int i=0; i<50000; i++）{
9 list.add（0，obj）;
10 }
11
12 long end = System.currentTimeMillis（）;
13 long time = end - begin;
14 System.out.println（time+）;
15
16 }
测试成果是：ArrayList耗时1400ms，而LinkedList只耗时12ms。可以看出，在随机插入的时辰，两者的机能差别就很明显了。
小结一下，从上方的源码解析和测试成果可以看出这三种List实现的一些典范实用处景，若是经常对数组做随机插入操纵，希罕是插入的斗劲靠前，那么LinkedList的机能上风就很是明显，而若是都只是末尾插入，则ArrayList更占领上风，若是须要线程安然，则非Vector莫属。
我们永远不要期待别人的拯救，只有自己才能升华自己。自己已准备好了多少容量，方能吸引对等的人与我们相遇，否则再美好的人出现、再动人的事情降临身边，我们也没有能量去理解与珍惜，终将擦肩而过。—— 姚谦《品味》
