说说JDK中的List－ArrayList、Vector、LinkedList-

说说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莫属。

我们永远不要期待别人的拯救，只有自己才能升华自己。自己已准备好了多少容量，方能吸引对等的人与我们相遇，否则再美好的人出现、再动人的事情降临身边，我们也没有能量去理解与珍惜，终将擦肩而过。—— 姚谦《品味》

分享到：

新闻动态NEWS

说说JDK中的List－ArrayList、Vector、LinkedList

添加时间:2013-8-12 点击量:

新闻动态
NEWS