关于java中的list接口的认识（原码分析）

讲解jdk源码中List接口之前我们先来看一个模式，迭代器设计模式。

        迭代器设计模式主要是为了对容器提供统一的遍历接口，对于不同的数据结构的遍历方式由不同的iterator实现类所实现，而且也对原始数据进行了封装，不至于在用户使用时暴漏内部细节，类图如下。

 上面图中的各个类其实就是jdk中Collection容器对迭代器设计模式的一个实现，Itr是AbstractList的一个内部类，内部类的好处就是它可以直接访问AbstractList中的数据，Itr类实现了对元数据的遍历，部分代码如下。

Java代码  

1. public boolean hasNext() {  
2.     return cursor != size();  
3. }  
4.   
5. public E next() {  
6.     checkForComodification();  
7.     try {  
8.         E next = get(cursor);  
9.         lastRet = cursor++;  
10.         return next;  
11.     } catch (IndexOutOfBoundsException e) {  
12.         checkForComodification();  
13.         throw new NoSuchElementException();  
14.     }  
15. }  

        java中的List接口以及实现类，类图如下：

List中主要有2种数据结构的实现，一种是数组，另一种是链表。

    数组的实现有ArrayList、Vector、Stack、CopyOnWriteArrayList他们都继承了AbstractList，AbstractList实现了List中的部分接口，并且实现了数组结构的遍历，也就是上边说到的迭代器设计模式中Iterator部分，Stack实现了一个LIFO，Vector实现了线程安全，CopyOnWriteArrayList则是线程安全的一个变体，读的操作没有锁性能会更好，而写的时候存在锁并且在写的时候copy元数据，在新的数据上做修改，然后在同步回元数据，从而实现了在遍历的时候可以对其进行修改而不会抛出CurrentModificationException异常。基于数组实现的容器都实现了RandomAccess接口，这是一个空接口，实现了这个接口的类代表支持随机访问，而支持随机访问的类在遍历时正如RandomAccess类中描述的那样，上面的遍历方式性能会好于下面的遍历方式如下：

 * <pre>
 *     for (int i=0, n=list.size(); i &lt; n; i++)
 *         list.get(i);
 * </pre>
 * runs faster than this loop:
 * <pre>
 *     for (Iterator i=list.iterator(); i.hasNext(); )
 *         i.next();
 * </pre>

 

    链表的实现只有LinkedList。

    这里我们主要讲解ArrayList和LinkedList，首先看ArrayList，它的类声明如下：

Java代码  

1. public class ArrayList<E> extends AbstractList<E>  
2.         implements List<E>, RandomAccess, Cloneable, java.io.Serializable  

 

他实现了RandomAccess支持随机访问，因为底层是数组嘛，知道下标访问速度是非常快的哈，并且实现了Serializable接口，代表这个类可以序列化以及反序列化，Cloneable则代表这个类可以被克隆，这个克隆啊又涉及到原型设计模式，原型涉及模式分为深克隆和浅克隆，有兴趣的朋友可以自己了解下本节不做讲解。

Java代码  

1. /** 
2.  * The array buffer into which the elements of the ArrayList are stored. 
3.  * The capacity of the ArrayList is the length of this array buffer. 
4.  */  
5. private transient Object[] elementData;  
6.   
7. /** 
8.  * The size of the ArrayList (the number of elements it contains). 
9.  * 
10.  * @serial 
11.  */  
12. private int size;  

 

ArrayList中只有这2个成员变量，elementData则是用来存放具体数据的，size则用来标记数组实际大小，但是这里elementData为什么被transient修饰呢，被transient修饰则代表在序列化时会忽略elementData，难道elementData就不序列化了吗，并不是，而是ArrayList重写了writeObject方法，因为elementData每次满的时候都会扩充，会存在NULL没有使用的元素，所以重写了writeObject方法在序列化时只写入elementData的0到size实际使用的的数据。

Java代码  

1. public boolean add(E e) {  
2.     ensureCapacity(size + 1);  // Increments modCount!!  
3.     elementData[size++] = e;  
4.     return true;  
5. }  

 add添加元素时首先调用了ensureCapacity方法，这个方法会进行判断当前数组容量是否小于size+1，如果小于则扩充，扩充是调用的system.arraycopy的native方法来将数组copy到另一个扩充之后的数组中，然后把要添加的数据存放在elementData中。其余的方法和类都比较简单类似就不在说了。

    LinkedList底层使用Entry类来存放数据元素。

Java代码  

1. private static class Entry<E> {  
2.     E element;  
3.     Entry<E> next;  
4.     Entry<E> previous;  
5.   
6.     Entry(E element, Entry<E> next, Entry<E> previous) {  
7.         this.element = element;  
8.         this.next = next;  
9.         this.previous = previous;  
10.     }  
11. }  

 链表，就是手拉手，通过一个元素可以知道上一个元素和下一个元素，这个链表不了解的话可以先学习下数据结构这里就不在多说了，链表的遍历方式实现和数组是不一样的，

 

Java代码  

1.    private class ListItr implements ListIterator<E> {  
2. private Entry<E> lastReturned = header;  
3. private Entry<E> next;  
4. private int nextIndex;  
5. private int expectedModCount = modCount;  
6.   
7. ListItr(int index) {  
8.     if (index < 0 || index > size)  
9.     throw new IndexOutOfBoundsException("Index: "+index+  
10.                         ", Size: "+size);  
11.     if (index < (size >> 1)) {  
12.     next = header.next;  
13.     for (nextIndex=0; nextIndex<index; nextIndex++)  
14.         next = next.next;  
15.     } else {  
16.     next = header;  
17.     for (nextIndex=size; nextIndex>index; nextIndex--)  
18.         next = next.previous;  
19.     }  
20. }  
21.   
22. public boolean hasNext() {  
23.     return nextIndex != size;  
24. }  
25.   
26. public E next() {  
27.     checkForComodification();  
28.     if (nextIndex == size)  
29.     throw new NoSuchElementException();  
30.   
31.     lastReturned = next;  
32.     next = next.next;  
33.     nextIndex++;  
34.     return lastReturned.element;  
35. }  

 构造方法中初始化了next的值，if（int < (size >> 1)）这里介绍下>>和>>>符号，>>代表向右移位，例如3>>1则代表二进制0011向右移动1位则是0001最终结果就是1，8>>>3代表8除以2的3次方最终结果则是1。

这里的if(int < (size >> 1))主要是为了判断这个元素时在前半段还是在后半段size >> 1相当于size/2，主要是为了更快的定位链表中第index元素的位置，不用从头遍历，这就是迭代器设计模式的好处，隐藏了内部实现的细节，对不同的数据结构提供了统一的迭代接口，就到这吧！

讲解jdk源码中List接口之前我们先来看一个模式，迭代器设计模式。

        迭代器设计模式主要是为了对容器提供统一的遍历接口，对于不同的数据结构的遍历方式由不同的iterator实现类所实现，而且也对原始数据进行了封装，不至于在用户使用时暴漏内部细节，类图如下。

 上面图中的各个类其实就是jdk中Collection容器对迭代器设计模式的一个实现，Itr是AbstractList的一个内部类，内部类的好处就是它可以直接访问AbstractList中的数据，Itr类实现了对元数据的遍历，部分代码如下。

Java代码  

1. public boolean hasNext() {  
2.     return cursor != size();  
3. }  
4.   
5. public E next() {  
6.     checkForComodification();  
7.     try {  
8.         E next = get(cursor);  
9.         lastRet = cursor++;  
10.         return next;  
11.     } catch (IndexOutOfBoundsException e) {  
12.         checkForComodification();  
13.         throw new NoSuchElementException();  
14.     }  
15. }  

        java中的List接口以及实现类，类图如下：

List中主要有2种数据结构的实现，一种是数组，另一种是链表。

    数组的实现有ArrayList、Vector、Stack、CopyOnWriteArrayList他们都继承了AbstractList，AbstractList实现了List中的部分接口，并且实现了数组结构的遍历，也就是上边说到的迭代器设计模式中Iterator部分，Stack实现了一个LIFO，Vector实现了线程安全，CopyOnWriteArrayList则是线程安全的一个变体，读的操作没有锁性能会更好，而写的时候存在锁并且在写的时候copy元数据，在新的数据上做修改，然后在同步回元数据，从而实现了在遍历的时候可以对其进行修改而不会抛出CurrentModificationException异常。基于数组实现的容器都实现了RandomAccess接口，这是一个空接口，实现了这个接口的类代表支持随机访问，而支持随机访问的类在遍历时正如RandomAccess类中描述的那样，上面的遍历方式性能会好于下面的遍历方式如下：

 * <pre>
 *     for (int i=0, n=list.size(); i &lt; n; i++)
 *         list.get(i);
 * </pre>
 * runs faster than this loop:
 * <pre>
 *     for (Iterator i=list.iterator(); i.hasNext(); )
 *         i.next();
 * </pre>

 

    链表的实现只有LinkedList。

    这里我们主要讲解ArrayList和LinkedList，首先看ArrayList，它的类声明如下：

Java代码  

1. public class ArrayList<E> extends AbstractList<E>  
2.         implements List<E>, RandomAccess, Cloneable, java.io.Serializable  

 

他实现了RandomAccess支持随机访问，因为底层是数组嘛，知道下标访问速度是非常快的哈，并且实现了Serializable接口，代表这个类可以序列化以及反序列化，Cloneable则代表这个类可以被克隆，这个克隆啊又涉及到原型设计模式，原型涉及模式分为深克隆和浅克隆，有兴趣的朋友可以自己了解下本节不做讲解。

Java代码  

1. /** 
2.  * The array buffer into which the elements of the ArrayList are stored. 
3.  * The capacity of the ArrayList is the length of this array buffer. 
4.  */  
5. private transient Object[] elementData;  
6.   
7. /** 
8.  * The size of the ArrayList (the number of elements it contains). 
9.  * 
10.  * @serial 
11.  */  
12. private int size;  

 

ArrayList中只有这2个成员变量，elementData则是用来存放具体数据的，size则用来标记数组实际大小，但是这里elementData为什么被transient修饰呢，被transient修饰则代表在序列化时会忽略elementData，难道elementData就不序列化了吗，并不是，而是ArrayList重写了writeObject方法，因为elementData每次满的时候都会扩充，会存在NULL没有使用的元素，所以重写了writeObject方法在序列化时只写入elementData的0到size实际使用的的数据。

Java代码  

1. public boolean add(E e) {  
2.     ensureCapacity(size + 1);  // Increments modCount!!  
3.     elementData[size++] = e;  
4.     return true;  
5. }  

 add添加元素时首先调用了ensureCapacity方法，这个方法会进行判断当前数组容量是否小于size+1，如果小于则扩充，扩充是调用的system.arraycopy的native方法来将数组copy到另一个扩充之后的数组中，然后把要添加的数据存放在elementData中。其余的方法和类都比较简单类似就不在说了。

    LinkedList底层使用Entry类来存放数据元素。

Java代码  

1. private static class Entry<E> {  
2.     E element;  
3.     Entry<E> next;  
4.     Entry<E> previous;  
5.   
6.     Entry(E element, Entry<E> next, Entry<E> previous) {  
7.         this.element = element;  
8.         this.next = next;  
9.         this.previous = previous;  
10.     }  
11. }  

 链表，就是手拉手，通过一个元素可以知道上一个元素和下一个元素，这个链表不了解的话可以先学习下数据结构这里就不在多说了，链表的遍历方式实现和数组是不一样的，

 

Java代码  

1.    private class ListItr implements ListIterator<E> {  
2. private Entry<E> lastReturned = header;  
3. private Entry<E> next;  
4. private int nextIndex;  
5. private int expectedModCount = modCount;  
6.   
7. ListItr(int index) {  
8.     if (index < 0 || index > size)  
9.     throw new IndexOutOfBoundsException("Index: "+index+  
10.                         ", Size: "+size);  
11.     if (index < (size >> 1)) {  
12.     next = header.next;  
13.     for (nextIndex=0; nextIndex<index; nextIndex++)  
14.         next = next.next;  
15.     } else {  
16.     next = header;  
17.     for (nextIndex=size; nextIndex>index; nextIndex--)  
18.         next = next.previous;  
19.     }  
20. }  
21.   
22. public boolean hasNext() {  
23.     return nextIndex != size;  
24. }  
25.   
26. public E next() {  
27.     checkForComodification();  
28.     if (nextIndex == size)  
29.     throw new NoSuchElementException();  
30.   
31.     lastReturned = next;  
32.     next = next.next;  
33.     nextIndex++;  
34.     return lastReturned.element;  
35. }  

 构造方法中初始化了next的值，if（int < (size >> 1)）这里介绍下>>和>>>符号，>>代表向右移位，例如3>>1则代表二进制0011向右移动1位则是0001最终结果就是1，8>>>3代表8除以2的3次方最终结果则是1。

这里的if(int < (size >> 1))主要是为了判断这个元素时在前半段还是在后半段size >> 1相当于size/2，主要是为了更快的定位链表中第index元素的位置，不用从头遍历，这就是迭代器设计模式的好处，隐藏了内部实现的细节，对不同的数据结构提供了统一的迭代接口，就到这吧！

讲解jdk源码中List接口之前我们先来看一个模式，迭代器设计模式。

        迭代器设计模式主要是为了对容器提供统一的遍历接口，对于不同的数据结构的遍历方式由不同的iterator实现类所实现，而且也对原始数据进行了封装，不至于在用户使用时暴漏内部细节，类图如下。

 上面图中的各个类其实就是jdk中Collection容器对迭代器设计模式的一个实现，Itr是AbstractList的一个内部类，内部类的好处就是它可以直接访问AbstractList中的数据，Itr类实现了对元数据的遍历，部分代码如下。

Java代码  

1. public boolean hasNext() {  
2.     return cursor != size();  
3. }  
4.   
5. public E next() {  
6.     checkForComodification();  
7.     try {  
8.         E next = get(cursor);  
9.         lastRet = cursor++;  
10.         return next;  
11.     } catch (IndexOutOfBoundsException e) {  
12.         checkForComodification();  
13.         throw new NoSuchElementException();  
14.     }  
15. }  

        java中的List接口以及实现类，类图如下：

List中主要有2种数据结构的实现，一种是数组，另一种是链表。

    数组的实现有ArrayList、Vector、Stack、CopyOnWriteArrayList他们都继承了AbstractList，AbstractList实现了List中的部分接口，并且实现了数组结构的遍历，也就是上边说到的迭代器设计模式中Iterator部分，Stack实现了一个LIFO，Vector实现了线程安全，CopyOnWriteArrayList则是线程安全的一个变体，读的操作没有锁性能会更好，而写的时候存在锁并且在写的时候copy元数据，在新的数据上做修改，然后在同步回元数据，从而实现了在遍历的时候可以对其进行修改而不会抛出CurrentModificationException异常。基于数组实现的容器都实现了RandomAccess接口，这是一个空接口，实现了这个接口的类代表支持随机访问，而支持随机访问的类在遍历时正如RandomAccess类中描述的那样，上面的遍历方式性能会好于下面的遍历方式如下：

 * <pre>
 *     for (int i=0, n=list.size(); i &lt; n; i++)
 *         list.get(i);
 * </pre>
 * runs faster than this loop:
 * <pre>
 *     for (Iterator i=list.iterator(); i.hasNext(); )
 *         i.next();
 * </pre>

    链表的实现只有LinkedList。

    这里我们主要讲解ArrayList和LinkedList，首先看ArrayList，它的类声明如下：

Java代码  

1. public class ArrayList<E> extends AbstractList<E>  
2.         implements List<E>, RandomAccess, Cloneable, java.io.Serializable  

他实现了RandomAccess支持随机访问，因为底层是数组嘛，知道下标访问速度是非常快的哈，并且实现了Serializable接口，代表这个类可以序列化以及反序列化，Cloneable则代表这个类可以被克隆，这个克隆啊又涉及到原型设计模式，原型涉及模式分为深克隆和浅克隆，有兴趣的朋友可以自己了解下本节不做讲解。

Java代码  

1. /** 
2.  * The array buffer into which the elements of the ArrayList are stored. 
3.  * The capacity of the ArrayList is the length of this array buffer. 
4.  */  
5. private transient Object[] elementData;  
6.   
7. /** 
8.  * The size of the ArrayList (the number of elements it contains). 
9.  * 
10.  * @serial 
11.  */  
12. private int size;  

ArrayList中只有这2个成员变量，elementData则是用来存放具体数据的，size则用来标记数组实际大小，但是这里elementData为什么被transient修饰呢，被transient修饰则代表在序列化时会忽略elementData，难道elementData就不序列化了吗，并不是，而是ArrayList重写了writeObject方法，因为elementData每次满的时候都会扩充，会存在NULL没有使用的元素，所以重写了writeObject方法在序列化时只写入elementData的0到size实际使用的的数据。

Java代码  

1. public boolean add(E e) {  
2.     ensureCapacity(size + 1);  // Increments modCount!!  
3.     elementData[size++] = e;  
4.     return true;  
5. }  

 add添加元素时首先调用了ensureCapacity方法，这个方法会进行判断当前数组容量是否小于size+1，如果小于则扩充，扩充是调用的system.arraycopy的native方法来将数组copy到另一个扩充之后的数组中，然后把要添加的数据存放在elementData中。其余的方法和类都比较简单类似就不在说了。

    LinkedList底层使用Entry类来存放数据元素。

Java代码  

1. private static class Entry<E> {  
2.     E element;  
3.     Entry<E> next;  
4.     Entry<E> previous;  
5.   
6.     Entry(E element, Entry<E> next, Entry<E> previous) {  
7.         this.element = element;  
8.         this.next = next;  
9.         this.previous = previous;  
10.     }  
11. }  

 链表，就是手拉手，通过一个元素可以知道上一个元素和下一个元素，这个链表不了解的话可以先学习下数据结构这里就不在多说了，链表的遍历方式实现和数组是不一样的，

Java代码  

1.    private class ListItr implements ListIterator<E> {  
2. private Entry<E> lastReturned = header;  
3. private Entry<E> next;  
4. private int nextIndex;  
5. private int expectedModCount = modCount;  
6.   
7. ListItr(int index) {  
8.     if (index < 0 || index > size)  
9.     throw new IndexOutOfBoundsException("Index: "+index+  
10.                         ", Size: "+size);  
11.     if (index < (size >> 1)) {  
12.     next = header.next;  
13.     for (nextIndex=0; nextIndex<index; nextIndex++)  
14.         next = next.next;  
15.     } else {  
16.     next = header;  
17.     for (nextIndex=size; nextIndex>index; nextIndex--)  
18.         next = next.previous;  
19.     }  
20. }  
21.   
22. public boolean hasNext() {  
23.     return nextIndex != size;  
24. }  
25.   
26. public E next() {  
27.     checkForComodification();  
28.     if (nextIndex == size)  
29.     throw new NoSuchElementException();  
30.   
31.     lastReturned = next;  
32.     next = next.next;  
33.     nextIndex++;  
34.     return lastReturned.element;  
35. }  

 构造方法中初始化了next的值，if（int < (size >> 1)）这里介绍下>>和>>>符号，>>代表向右移位，例如3>>1则代表二进制0011向右移动1位则是0001最终结果就是1，8>>>3代表8除以2的3次方最终结果则是1。

这里的if(int < (size >> 1))主要是为了判断这个元素时在前半段还是在后半段size >> 1相当于size/2，主要是为了更快的定位链表中第index元素的位置，不用从头遍历，这就是迭代器设计模式的好处，隐藏了内部实现的细节，对不同的数据结构提供了统一的迭代接口，就到这吧！