List集合设计与实现

深藏阁楼爱情的钟 2022-06-09 06:41 213阅读 0赞

# 1 List #

List实现Collection接口，它的数据结构是有序可以重复的结合，它有三个实现类：ArrayList、LinkList、Vector；

*三个实现类的区别：*

> ArrayList:底层数据结构使**数组**结构，查询速度快，增删改慢，
> 
> LinkList:底层使用**链表**结构，增删速度快，查询稍慢；
> 
> Vector：底层是**数组**结构，线程同步；ArrayList是线程不同步；

*可变长度数组--不断new数组：*

> ArrayList当初始化容量超过10时，会new一个1.5倍新数组,把原来的东西放入新数组中；
> 
> Vector：当容量超过10时，会new一个100%的内存；

List接口对Collection进行了简单的扩充，它的具体实现类常用的有ArrayList和LinkedList。你可以将任何东西放到一个List容器中，并在需要时从中取出。ArrayList从其命名中可以看出它是一种类似数组的形式进行存储，因此它的随机访问速度极快，而LinkedList的内部实现是链表，它适合于在链表中间需要频繁进行插入和删除操作。在具体应用时可以根据需要自由选择。

**Iterator**只能对容器进行向前遍历，而**ListIterator**则继承了**Iterator**的思想，并提供了对List进行**双向遍历**的方法。

# **2 ArrayList** #

## 1. ArrayList概述 ##

ArrayList是List接口的**可变数组**的实现。实现了所有可选列表操作，并允许包括null在内的所有元素。除了实现 List 接口外，此类还提供一些方法来操作内部用来存储列表的数组的大小。  
**每个ArrayList实例都有一个容量**，**容量>=实际元素列表长度length**。

随着向ArrayList中不断添加元素，其容量也自动增长。自动增长会带来数据向新数组的重新拷贝，因此，**如果可预知数据量的多少，可在构造ArrayList时指定其容量。**在添加大量元素前，应用程序也可以使用**ensureCapacity操作来增加ArrayList实例的容量**，这可以减少递增式再分配的数量。  
注意，此实现**不是同步**的。如果多个线程同时访问一个ArrayList实例，而其中至少一个线程从结构上修改了列表，那么它必须保持外部同步。

## 2. ArrayList的实现 ##

对于ArrayList而言，它实现List接口、底层使用数组保存所有元素。其操作基本上是对数组的操作。

下面我们来分析ArrayList的源代码：

**1）数据结构**

> Java代码

>  private transient Object\[\] elementData;

**2)构造方法**：  
ArrayList提供了三种方式的构造器：

1.  1.  **构造一个默认初始容量为10的空列表**
    2.  **构造一个指定初始容量的空列表**
    3.  **构造一个包含指定collection的元素的列表**

这些元素按照该collection的迭代器返回它们的顺序排列的。

Java代码

public ArrayList() {  
             this(10);  
         }         
         public ArrayList(int initialCapacity) {  
             super();  
             if (initialCapacity < 0)  
                 throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);  
             this.elementData = new Object[initialCapacity];  
      }  
        
      public ArrayList(Collection<? extends E> c) {  
          elementData = c.toArray();  
          size = elementData.length;  
          // c.toArray might (incorrectly) not return Object[] (see 6260652)  
          if (elementData.getClass() != Object[].class)  
              elementData = Arrays.copyOf(elementData, size, Object[].class);  
      }

**3)存储**：

ArrayList提供了set(int index, E element)、add(E e)、add(int index, E element)、addAll(Collection<?extends E> c)、addAll(int index, Collection<?extends E> c)这些添加元素的方法。下面我们一一讲解：

> Java代码

// 用指定的元素替代此列表中指定位置上的元素，并返回以前位于该位置上的元素。  
         public E set(int index, E element) {  
             RangeCheck(index);  
           
             E oldValue = (E) elementData[index];  
             elementData[index] = element;  
             return oldValue;  
         }

> Java代码

// 将指定的元素添加到此列表的尾部。  
         public boolean add(E e) {  
             ensureCapacity(size + 1);   
             elementData[size++] = e;  
             return true;  
         }

> Java代码

// 将指定的元素插入此列表中的指定位置。  
         // 如果当前位置有元素，则向右移动当前位于该位置的元素以及所有后续元素（将其索引加1）。  
         public void add(int index, E element) {  
             if (index > size || index < 0)  
                 throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);  
             // 如果数组长度不足，将进行扩容。  
             ensureCapacity(size+1);  // Increments modCount!!  
             // 将 elementData中从Index位置开始、长度为size-index的元素，  
             // 拷贝到从下标为index+1位置开始的新的elementData数组中。  
          // 即将当前位于该位置的元素以及所有后续元素右移一个位置。  
          System.arraycopy(elementData, index, elementData, index + 1, size - index);  
          elementData[index] = element;  
          size++;  
      }

> Java代码

// 按照指定collection的迭代器所返回的元素顺序，将该collection中的所有元素添加到此列表的尾部。  
         public boolean addAll(Collection<? extends E> c) {  
             Object[] a = c.toArray();  
             int numNew = a.length;  
             ensureCapacity(size + numNew);  // Increments modCount  
             System.arraycopy(a, 0, elementData, size, numNew);  
             size += numNew;  
             return numNew != 0;  
         }

> Java代码

// 从指定的位置开始，将指定collection中的所有元素插入到此列表中。  
        public boolean addAll(int index, Collection<? extends E> c) {  
             if (index > size || index < 0)  
                throw new IndexOutOfBoundsException(  
                    "Index: " + index + ", Size: " + size);  
          
            Object[] a = c.toArray();  
             int numNew = a.length;  
            ensureCapacity(size + numNew);  // Increments modCount  
       
         int numMoved = size - index;  
          if (numMoved > 0)  
             System.arraycopy(elementData, index, elementData, index + numNew, numMoved);  
        
         System.arraycopy(a, 0, elementData, index, numNew);  
          size += numNew;  
          return numNew != 0;  
    }

**4）读取**

> Java代码

// 返回此列表中指定位置上的元素。  
         public E get(int index) {  
             RangeCheck(index);  
           
             return (E) elementData[index];  
         }

**5) 删除**：  ArrayList提供了根据下标或者指定对象两种方式的删除功能。如下：

> Java代码

// 移除此列表中指定位置上的元素。  
         public E remove(int index) {  
             RangeCheck(index);  
           
             modCount++;  
             E oldValue = (E) elementData[index];  
           
             int numMoved = size - index - 1;  
             if (numMoved > 0)  
              System.arraycopy(elementData, index+1, elementData, index, numMoved);  
          elementData[--size] = null; // Let gc do its work  
        
          return oldValue;  
      }

> Java代码

// 移除此列表中首次出现的指定元素（如果存在）。这是应为ArrayList中允许存放重复的元素。  
         public boolean remove(Object o) {  
             // 由于ArrayList中允许存放null，因此下面通过两种情况来分别处理。  
             if (o == null) {  
                 for (int index = 0; index < size; index++)  
                     if (elementData[index] == null) {  
                         // 类似remove(int index)，移除列表中指定位置上的元素。  
                         fastRemove(index);  
                         return true;  
                  }  
      } else {  
          for (int index = 0; index < size; index++)  
              if (o.equals(elementData[index])) {  
                  fastRemove(index);  
                  return true;  
              }  
          }  
          return false;  
      }

注意：从数组中移除元素的操作，也会导致被移除的元素以后的所有元素的向左移动一个位置。

**6) 调整数组容量**   
从上面介绍的向ArrayList中存储元素的代码中，我们看到，每当向数组中添加元素时，都要去检查添加后元素的个数是否会超出当前数组的长度，如果超出，数组将会进行扩容，以满足添加数据的需求。数组扩容通过一个公开的方法ensureCapacity(int minCapacity)来实现。在实际添加大量元素前，我也可以使用ensureCapacity来手动增加ArrayList实例的容量，以减少递增式再分配的数量。

Java代码

public void ensureCapacity(int minCapacity) {  
             modCount++;  
             int oldCapacity = elementData.length;  
             if (minCapacity > oldCapacity) {  
                 Object oldData[] = elementData;  
                 int newCapacity = (oldCapacity * 3)/2 + 1;  
                     if (newCapacity < minCapacity)  
                         newCapacity = minCapacity;  
               // minCapacity is usually close to size, so this is a win:  
            elementData = Arrays.copyOf(elementData, newCapacity);  
          }  
      }

从上述代码中可以看出，数组进行扩容时，会将老数组中的元素重新拷贝一份到新的数组中，每次数组容量的增长大约是其原容量的1.5倍。这种操作的代价是很高的，因此在实际使用时，我们应该尽量避免数组容量的扩张。当我们可预知要保存的元素的多少时，要在构造ArrayList实例时，就指定其容量，以避免数组扩容的发生。或者根据实际需求，通过调用e**nsureCapacity**方法来手动增加ArrayList实例的容量。  
ArrayList还给我们提供了将底层数组的容量调整为当前列表保存的实际元素的大小的功能。它可以通过trimToSize方法来实现。

> Java代码

public void trimToSize() {  
             modCount++;  
             int oldCapacity = elementData.length;  
             if (size < oldCapacity) {  
                 elementData = Arrays.copyOf(elementData, size);  
             }  
         }

**7) Fail-Fast机制**   
ArrayList也采用了快速失败的机制，通过记录modCount参数来实现。在面对并发的修改时，迭代器很快就会完全失败，而不是冒着在将来某个不确定时间发生任意不确定行为的风险。具体介绍请参考我之前的文章[深入Java集合学习系列：HashMap的实现原理][Java_HashMap] 中的Fail-Fast机制。  
8) 关于其他的一些方法的实现都很简单易懂，读者可参照API文档和源代码，比较容易，不再多说。

**ArrayList和Vector区别：**

1)**Vector是线程同步的，所以它也是线程安全的,而ArratList是线程异步的，不安全**。如果不考虑安全因素，一般用Arralist效率比较高，查看JDK文档，给出提示：

如果要实现Arraylist线程同步，可以通过下面方式：

如果多个线程同时访问一个 ArrayList 实例，而其中至少一个线程从结构上修改了列表，那么它必须 保持外部同步。（结构上的修改是指任何添加或删除一个或多个元素的操作，或者显式调整底层数组的大小；仅仅设置元素的值不是结构上的修改。）这一般通过对自然封装该列表的对象进行同步操作来完成。如果不存在这样的对象，则应该使用[Collections.synchronizedList][] 方法将该列表“包装”起来。这最好在创建时完成，以防止意外对列表进行不同步的访问：

List list = Collections.synchronizedList(new ArrayList(...));

2)如果集合中的元素数量大于当前集合数组的长度时，Vector的增长是目前数组长度的2倍，而ArryaList的增长为目前数组长度的1.5倍，所以，**如果集合中使用数据量比较大的数据，用Vector有一定优势**。

# 3 LinkList #

## 3.1 LinkList简介 ##

LinkedList与Collection关系如下图：

![Center][]

LinkedList的本质是**双向链表**。

1) LinkedList继承于AbstractSequentialList，并且实现了Dequeue接口。

2) LinkedList包含两个重要的成员：**header 和 size**。

**header**是双向链表的**表头**，它是双向链表节点所对应的类**Entry的实例**。Entry中包含成员变量：**previous, next, element**。其中，previous是该节点的上一个节点，next是该节点的下一个节点，element是该节点所包含的值。

**size**是双向链表中**节点的个数**。

上面说到，LinkedList实际上是通过**双向链表**去实现的。既然是双向链表，那么它的**顺序访问会非常高效**，而**随机访问效率比较低**。

既然LinkedList是通过双向链表的，但是它也实现了List接口\{也就是说，它实现了get(int location)、remove(int location)等“根据索引值来获取、删除节点的函数”；

**双线链表和索引值联系起来”的方法：**

【实际原理非常简单，它就是通过一个计数索引值来实现的。例如，当我们调用get(int location)时，首先会比较“location”和“双向链表长度的1/2”；若前者大，则从链表头开始往后查找，直到location位置；否则，从链表末尾开始先前查找，直到location位置。】

下面开始阅读LinkList源码 。

## **3.2 LinkedList源码解析** ##

(基于JDK1.6.0\_45)

package java.util;
     
      public class LinkedList<E>   extends AbstractSequentialList<E>
          implements List<E>, Deque<E>, Cloneable,java.io.Serializable
      {
          // 链表的表头，表头不包含任何数据。Entry是个链表类数据结构。
          private transient Entry<E> header = new Entry<E>(null, null,null);
     
         // LinkedList中元素个数
         private transient int size = 0;
     
         // 默认构造函数：创建一个空的链表
         public LinkedList() {
             header.next = header.previous = header;
          }
     
         // 包含“集合”的构造函数:创建一个包含“集合”的LinkedList
         public LinkedList(Collection<? extends E> c) {
             this();
             addAll(c);
          }
     
         // 获取LinkedList的第一个元素
         public E getFirst() {
             if (size==0)
                 throw newNoSuchElementException();
     
             // 链表的表头header中不包含数据。
             // 这里返回header所指下一个节点所包含的数据。
             return header.next.element;
          }
     
         // 获取LinkedList的最后一个元素
         public E getLast()  {
             if (size==0)
                 throw new NoSuchElementException();
     
             // 由于LinkedList是双向链表；而表头header不包含数据。
             // 因而，这里返回表头header的前一个节点所包含的数据。
             return header.previous.element;
          }
     
         // 删除LinkedList的第一个元素
         public E removeFirst() {
             return remove(header.next);
          }
     
         // 删除LinkedList的最后一个元素
         public E removeLast() {
             return remove(header.previous);
          }
    
         // 将元素添加到LinkedList的起始位置
         public void addFirst(E e) {
             addBefore(e, header.next);
          }
     
         // 将元素添加到LinkedList的结束位置
         public void addLast(E e) {
             addBefore(e, header);
          }
     
         // 判断LinkedList是否包含元素(o)
         public boolean contains(Object o) {
             return indexOf(o) != -1;
          }
     
         // 返回LinkedList的大小
         public int size() {
             return size;
          }
     
         // 将元素(E)添加到LinkedList中
         public boolean add(E e) {
             // 将节点(节点数据是e)添加到表头(header)之前。
             // 即，将节点添加到双向链表的末端。
             addBefore(e, header);
             return true;
          }
     
         // 从LinkedList中删除元素(o)
         // 从链表开始查找，如存在元素(o)则删除该元素并返回true；
         // 否则，返回false。
         public boolean remove(Object o) {
             if (o==null) {
                 // 若o为null的删除情况
                 for (Entry<E> e = header.next; e != header; e = e.next) {
                      if (e.element==null) {
                         remove(e);
                          return true;
                      }
                 }
             } else {
                 // 若o不为null的删除情况
                 for (Entry<E> e = header.next; e != header; e = e.next) {
                      if (o.equals(e.element)) {
                          remove(e);
                          return true;
                     }
                 }
             }
             return false;
         }
    
         // 将“集合(c)”添加到LinkedList中。
         // 实际上，是从双向链表的末尾开始，将“集合(c)”添加到双向链表中。
         public boolean addAll(Collection<?extends E> c) {
             return addAll(size, c);
         }
    
         // 从双向链表的index开始，将“集合(c)”添加到双向链表中。
         public boolean addAll(int index,Collection<? extends E> c) {
             if (index < 0 || index > size)
                 throw newIndexOutOfBoundsException("Index: "+index+
                                                    ", Size: "+size);
             Object[] a = c.toArray();
             // 获取集合的长度
             int numNew = a.length;
             if (numNew==0)
                 return false;
             modCount++;
    
             // 设置“当前要插入节点的后一个节点”
             Entry<E> successor =(index==size ? header : entry(index));
             // 设置“当前要插入节点的前一个节点”
             Entry<E> predecessor =successor.previous;
             // 将集合(c)全部插入双向链表中
             for (int i=0; i<numNew; i++) {
                 Entry<E> e = newEntry<E>((E)a[i], successor, predecessor);
                 predecessor.next = e;
                 predecessor = e;
             }
             successor.previous = predecessor;
    
             // 调整LinkedList的实际大小
             size += numNew;
             return true;
         }
    
         // 清空双向链表
         public void clear() {
             Entry<E> e = header.next;
             // 从表头开始，逐个向后遍历；对遍历到的节点执行一下操作：
             // (01) 设置前一个节点为null
             // (02) 设置当前节点的内容为null
             // (03) 设置后一个节点为“新的当前节点”
             while (e != header) {
                 Entry<E> next = e.next;
                 e.next = e.previous = null;
                 e.element = null;
                 e = next;
             }
             header.next = header.previous =header;
             // 设置大小为0
             size = 0;
             modCount++;
         }
    
         // 返回LinkedList指定位置的元素
         public E get(int index) {
             return entry(index).element;
         }
    
         // 设置index位置对应的节点的值为element
         public E set(int index, E element) {
             Entry<E> e = entry(index);
             E oldVal = e.element;
             e.element = element;
             return oldVal;
         }
     
         // 在index前添加节点，且节点的值为element
         public void add(int index, E element) {
             addBefore(element, (index==size ?header : entry(index)));
         }
    
         // 删除index位置的节点
         public E remove(int index) {
             return remove(entry(index));
         }
    
         // 获取双向链表中指定位置的节点
         private Entry<E> entry(int index) {
             if (index < 0 || index >= size)
                 throw newIndexOutOfBoundsException("Index: "+index+
                                                    ", Size: "+size);
             Entry<E> e = header;
             // 获取index处的节点。
             // 若index < 双向链表长度的1/2,则从前先后查找;
             // 否则，从后向前查找。
             if (index < (size >> 1)) {
                 for (int i = 0; i <= index;i++)
                     e = e.next;
             } else {
                 for (int i = size; i > index;i--)
                     e = e.previous;
             }
             return e;
         }
    
         // 从前向后查找，返回“值为对象(o)的节点对应的索引”
         // 不存在就返回-1
         public int indexOf(Object o) {
             int index = 0;
             if (o==null) {
                 for (Entry e = header.next; e !=header; e = e.next) {
                     if (e.element==null)
                         return index;
                     index++;
                 }
             } else {
                 for (Entry e = header.next; e !=header; e = e.next) {
                     if (o.equals(e.element))
                         return index;
                     index++;
                 }
             }
             return -1;
         }
    
         // 从后向前查找，返回“值为对象(o)的节点对应的索引”
         // 不存在就返回-1
         public int lastIndexOf(Object o) {
             int index = size;
             if (o==null) {
                 for (Entry e = header.previous; e!= header; e = e.previous) {
                     index--;
                     if (e.element==null)
                         return index;
                 }
             } else {
                 for (Entry e = header.previous; e !=header; e = e.previous) {
                     index--;
                     if (o.equals(e.element))
                         return index;
                 }
             }
             return -1;
         }
    
         // 返回第一个节点
         // 若LinkedList的大小为0,则返回null
         public E peek() {
             if (size==0)
                 return null;
             return getFirst();
         }
    
         // 返回第一个节点
         // 若LinkedList的大小为0,则抛出异常
         public E element() {
             return getFirst();
         }
    
         // 删除并返回第一个节点
         // 若LinkedList的大小为0,则返回null
         public E poll() {
             if (size==0)
                 return null;
             return removeFirst();
         }
    
         // 将e添加双向链表末尾
         public boolean offer(E e) {
             return add(e);
         }
    
         // 将e添加双向链表开头
         public boolean offerFirst(E e) {
             addFirst(e);
             return true;
         }
    
         // 将e添加双向链表末尾
         public boolean offerLast(E e) {
             addLast(e);
             return true;
         }
    
         // 返回第一个节点
         // 若LinkedList的大小为0,则返回null
         public E peekFirst() {
             if (size==0)
                 return null;
             return getFirst();
         }
    
         // 返回最后一个节点
         // 若LinkedList的大小为0,则返回null
         public E peekLast() {
             if (size==0)
                 return null;
             return getLast();
         }
    
         // 删除并返回第一个节点
         // 若LinkedList的大小为0,则返回null
         public E pollFirst() {
             if (size==0)
                 return null;
             return removeFirst();
         }
    
         // 删除并返回最后一个节点
         // 若LinkedList的大小为0,则返回null
         public E pollLast() {
             if (size==0)
                 return null;
             return removeLast();
         }
    
         // 将e插入到双向链表开头
         public void push(E e) {
             addFirst(e);
         }
    
         // 删除并返回第一个节点
         public E pop() {
             return removeFirst();
         }
    
         // 从LinkedList开始向后查找，删除第一个值为元素(o)的节点
         // 从链表开始查找，如存在节点的值为元素(o)的节点，则删除该节点
         public booleanremoveFirstOccurrence(Object o) {
             return remove(o);
         }
    
         // 从LinkedList末尾向前查找，删除第一个值为元素(o)的节点
         // 从链表开始查找，如存在节点的值为元素(o)的节点，则删除该节点
         public boolean removeLastOccurrence(Objecto) {
             if (o==null) {
                 for (Entry<E> e =header.previous; e != header; e = e.previous) {
                     if (e.element==null) {
                         remove(e);
                         return true;
                     }
                 }
             } else {
                 for (Entry<E> e =header.previous; e != header; e = e.previous) {
                     if (o.equals(e.element)) {
                         remove(e);
                         return true;
                     }
                 }
             }
             return false;
         }
    
         // 返回“index到末尾的全部节点”对应的ListIterator对象(List迭代器)
         public ListIterator<E> listIterator(intindex) {
             return new ListItr(index);
         }
    
         // List迭代器
         private class ListItr implementsListIterator<E> {
             // 上一次返回的节点
             private Entry<E> lastReturned =header;
             // 下一个节点
             private Entry<E> next;
             // 下一个节点对应的索引值
             private int nextIndex;
             // 期望的改变计数。用来实现fail-fast机制。
             private int expectedModCount =modCount;
    
             // 构造函数。
             // 从index位置开始进行迭代
             ListItr(int index) {
                 // index的有效性处理
                 if (index < 0 || index >size)
                     throw newIndexOutOfBoundsException("Index: "+index+ ", Size:"+size);
                 // 若“index 小于‘双向链表长度的一半’”，则从第一个元素开始往后查找；
                 // 否则，从最后一个元素往前查找。
                 if (index < (size >> 1)){
                     next = header.next;
                     for (nextIndex=0;nextIndex<index; nextIndex++)
                         next = next.next;
                 } else {
                     next = header;
                     for (nextIndex=size;nextIndex>index; nextIndex--)
                         next = next.previous;
                 }
             }
    
             // 是否存在下一个元素
             public boolean hasNext() {
                 // 通过元素索引是否等于“双向链表大小”来判断是否达到最后。
                 return nextIndex != size;
             }
    
             // 获取下一个元素
             public E next() {
                 checkForComodification();
                 if (nextIndex == size)
                     throw newNoSuchElementException();
    
                 lastReturned = next;
                 // next指向链表的下一个元素
                 next = next.next;
                 nextIndex++;
                 return lastReturned.element;
             }
    
             // 是否存在上一个元素
             public boolean hasPrevious() {
                 // 通过元素索引是否等于0，来判断是否达到开头。
                 return nextIndex != 0;
             }
    
             // 获取上一个元素
             public E previous() {
                 if (nextIndex == 0)
                 throw newNoSuchElementException();
    
                 // next指向链表的上一个元素
                 lastReturned = next =next.previous;
                 nextIndex--;
                 checkForComodification();
                 return lastReturned.element;
             }
    
             // 获取下一个元素的索引
             public int nextIndex() {
                 return nextIndex;
             }
    
             // 获取上一个元素的索引
             public int previousIndex() {
                 return nextIndex-1;
             }
    
             // 删除当前元素。
             // 删除双向链表中的当前节点
             public void remove() {
                 checkForComodification();
                 Entry<E> lastNext =lastReturned.next;
                 try {
                    LinkedList.this.remove(lastReturned);
                } catch (NoSuchElementException e){
                     throw newIllegalStateException();
                 }
                 if (next==lastReturned)
                     next = lastNext;
                 else
                     nextIndex--;
                 lastReturned = header;
                 expectedModCount++;
             }
    
             // 设置当前节点为e
             public void set(E e) {
                 if (lastReturned == header)
                     throw newIllegalStateException();
                 checkForComodification();
                 lastReturned.element = e;
             }
    
             // 将e添加到当前节点的前面
             public void add(E e) {
                 checkForComodification();
                 lastReturned = header;
                 addBefore(e, next);
                 nextIndex++;
                 expectedModCount++;
             }
    
             // 判断“modCount和expectedModCount是否相等”，依次来实现fail-fast机制。
             final void checkForComodification() {
                 if (modCount != expectedModCount)
                 throw newConcurrentModificationException();
             }
         }
    
         // 双向链表的节点所对应的数据结构。
         // 包含3部分：上一节点，下一节点，当前节点值。
         private static class Entry<E> {
             // 当前节点所包含的值
             E element;
             // 下一个节点
             Entry<E> next;
             // 上一个节点
             Entry<E> previous;
    
             /**
              * 链表节点的构造函数。
              * 参数说明：
              *  element  —— 节点所包含的数据
              *  next      —— 下一个节点
              *  previous —— 上一个节点
              */
             Entry(E element, Entry<E> next,Entry<E> previous) {
                 this.element = element;
                 this.next = next;
                 this.previous = previous;
             }
         }
    
         // 将节点(节点数据是e)添加到entry节点之前。
         private Entry<E> addBefore(E e,Entry<E> entry) {
             // 新建节点newEntry，将newEntry插入到节点e之前；并且设置newEntry的数据是e
             Entry<E> newEntry = newEntry<E>(e, entry, entry.previous);
             newEntry.previous.next = newEntry;
             newEntry.next.previous = newEntry;
             // 修改LinkedList大小
             size++;
             // 修改LinkedList的修改统计数：用来实现fail-fast机制。
             modCount++;
             return newEntry;
         }
    
         // 将节点从链表中删除
         private E remove(Entry<E> e) {
             if (e == header)
                 throw newNoSuchElementException();
    
             E result = e.element;
             e.previous.next = e.next;
             e.next.previous = e.previous;
             e.next = e.previous = null;
             e.element = null;
             size--;
             modCount++;
             return result;
         }
    
         // 反向迭代器
         public Iterator<E>descendingIterator() {
             return new DescendingIterator();
         }
    
         // 反向迭代器实现类。
         private class DescendingIteratorimplements Iterator {
             final ListItr itr = newListItr(size());
             // 反向迭代器是否下一个元素。
             // 实际上是判断双向链表的当前节点是否达到开头
             public boolean hasNext() {
                 return itr.hasPrevious();
             }
             // 反向迭代器获取下一个元素。
             // 实际上是获取双向链表的前一个节点
             public E next() {
                 return itr.previous();
             }
             // 删除当前节点
             public void remove() {
                 itr.remove();
             }
         }
    
    
         // 返回LinkedList的Object[]数组
         public Object[] toArray() {
         // 新建Object[]数组
         Object[] result = new Object[size];
             int i = 0;
             // 将链表中所有节点的数据都添加到Object[]数组中
             for (Entry<E> e = header.next; e!= header; e = e.next)
                 result[i++] = e.element;
         return result;
         }
    
         // 返回LinkedList的模板数组。所谓模板数组，即可以将T设为任意的数据类型
         public <T> T[] toArray(T[] a) {
             // 若数组a的大小 < LinkedList的元素个数(意味着数组a不能容纳LinkedList中全部元素)
             // 则新建一个T[]数组，T[]的大小为LinkedList大小，并将该T[]赋值给a。
             if (a.length < size)
                 a =(T[])java.lang.reflect.Array.newInstance(
                                     a.getClass().getComponentType(),size);
             // 将链表中所有节点的数据都添加到数组a中
             int i = 0;
             Object[] result = a;
             for (Entry<E> e = header.next; e!= header; e = e.next)
                 result[i++] = e.element;
    
             if (a.length > size)
                 a[size] = null;
    
             return a;
         }
    
    
         // 克隆函数。返回LinkedList的克隆对象。
         public Object clone() {
             LinkedList<E> clone = null;
             // 克隆一个LinkedList克隆对象
            try {
                 clone = (LinkedList<E>)super.clone();
             } catch (CloneNotSupportedException e){
                 throw new InternalError();
             }
    
             // 新建LinkedList表头节点
             clone.header = new Entry<E>(null,null, null);
             clone.header.next =clone.header.previous = clone.header;
             clone.size = 0;
             clone.modCount = 0;
    
             // 将链表中所有节点的数据都添加到克隆对象中
             for (Entry<E> e = header.next; e!= header; e = e.next)
                 clone.add(e.element);
    
             return clone;
         }
    
         // java.io.Serializable的写入函数
         // 将LinkedList的“容量，所有的元素值”都写入到输出流中
         private voidwriteObject(java.io.ObjectOutputStream s)
             throws java.io.IOException {
             // Write out any hidden serializationmagic
             s.defaultWriteObject();
    
             // 写入“容量”
             s.writeInt(size);
    
             // 将链表中所有节点的数据都写入到输出流中
             for (Entry e = header.next; e != header;e = e.next)
                 s.writeObject(e.element);
         }
    
         // java.io.Serializable的读取函数：根据写入方式反向读出
         // 先将LinkedList的“容量”读出，然后将“所有的元素值”读出
         private voidreadObject(java.io.ObjectInputStream s)
             throws java.io.IOException,ClassNotFoundException {
             // Read in any hidden serializationmagic
             s.defaultReadObject();
    
             // 从输入流中读取“容量”
             int size = s.readInt();
    
             // 新建链表表头节点
             header = new Entry<E>(null,null, null);
             header.next = header.previous =header;
    
             // 从输入流中将“所有的元素值”并逐个添加到链表中
             for (int i=0; i<size; i++)
                 addBefore((E)s.readObject(),header);
         }
    
    }

**总结：**

> 1) LinkedList 实际上是通过**双向链表**去实现的，包含一个内部类：Entry。Entry是双向链表节点所对应的数据结构，它包括**previous, next, element**三个属性；
> 
> 2) 从LinkedList的实现方式中可知道它**不存在LinkedList容量不足的问题**。
> 
> 3) LinkedList的克隆函数是将**全部元素克隆到一个新的LinkedList对象中**。
> 
> 4) LinkedList实现java.io.Serializable。当写入到输出流时，先写入“容量”，再依次写入“每一个节点保护的值”；
> 
> 当读出输入流时，先读取“容量”，再依次读取“每一个元素”。
> 
> 5) 由于LinkedList实现了Deque，而Deque接口定义了在双端队列两端访问元素的方法，提供**插入**、**移除**和**检查**元素的方法。每种方法都存在两种形式：一种形式在操作失败时抛出异常，另一种形式返回一个特殊值（null 或 false，具体取决于操作）。

> > 总结起来如下表格：
> > 
> >  **第 一 个 元 素 （头部） 最 后 一 个 元 素 （尾部）**
> > 
> >  **抛出异常 特殊值 抛出异常 特殊值**
> > 
> > **插入 addFirst(e) offerFirst(e) addLast(e) offerLast(e)**
> > 
> > **移除 removeFirst() pollFirst() removeLast() pollLast()**
> > 
> > **检查 getFirst() peekFirst() getLast() peekLast()**

> 6) LinkedList可以作为**FIFO(先进先出)**的队列，作为FIFO的队列时，下表的方法等价：
> 
> 复制代码
> 
> 队列方法 等效方法
> 
> add(e) addLast(e)
> 
> offer(e) offerLast(e)
> 
> remove() removeFirst()
> 
> poll() pollFirst()
> 
> element() getFirst()
> 
> peek() peekFirst()

> 7) LinkedList可以作为LIFO(后进先出)的栈，作为LIFO的栈时，下表的方法等价：
> 
> 栈方法 等效方法
> 
> push(e) addFirst(e)
> 
> pop() removeFirst()
> 
> peek() peekFirst()
> 
> 最后，最好不要通过随机访问去遍历LinkedList！

# **4 Vector** #

相对于ArrayList来说，**Vector线程是安全的，也就是说是同步的**

创建了一个**向量类**的对象后，可以往其中随意地插入不同的类的对象，既不需顾及类型也不需预先选定向量的容量，并可方便地进行查找。对于预先不知或不愿预先定义数组大小，并需频繁进行查找、插入和删除工作的情况，可以考虑使用向量类。向量类提供了三种构造方法：

**public vector()**

**public vector(intinitialcapacity,int capacityIncrement)**

**public vector(intinitialcapacity)**

使用第一种方法，系统会自动对向量对象进行管理。

若使用后两种方法，则系统将根据参数initialcapacity设定向量对象的容量（即向量对象可存储数据的大小），当真正存放的数据个数超过容量时，系统会扩充向量对象的储存容量。

参数capacityIncrement给定了每次扩充的扩充值。当capacityIncrement为**0**时，则每次扩充一倍。利用这个功能可以**优化存储**。在Vector类中提供了各种方法方便用户使用

[Java_HashMap]: http://zhangshixi.iteye.com/blog/672697
[Collections.synchronizedList]: http://blog.csdn.net/daoqin121/article/details/39337967
[Center]: /images/20220609/9a36e8c9a4bb44d9a1759adbb02eccb4.png