Java 集合系列05之 LinkedList详细介绍(源码解析)和使用示例

古城微笑少年丶 2022-05-22 02:24 240阅读 0赞

### **概要 ** ###

前面，我们已经学习了ArrayList，并了解了fail-fast机制。这一章我们接着学习List的实现类——LinkedList。  
和学习ArrayList一样，接下来呢，我们先对LinkedList有个整体认识，然后再学习它的源码；最后再通过实例来学会使用LinkedList。内容包括：  
[第1部分 LinkedList介绍][1_ LinkedList]  
[第2部分 LinkedList数据结构][2_ LinkedList]  
[第3部分 LinkedList源码解析(基于JDK1.6.0\_45)][3_ LinkedList_JDK1.6.0_45]  
[第4部分 LinkedList遍历方式][4_ LinkedList]  
[第5部分 LinkedList示例][5_ LinkedList]

转载请注明出处：[http://www.cnblogs.com/skywang12345/p/3308807.html][http_www.cnblogs.com_skywang12345_p_3308807.html]

### 第1部分 LinkedList介绍 ###

**LinkedList简介**

LinkedList 是一个继承于AbstractSequentialList的双向链表。它也可以被当作堆栈、队列或双端队列进行操作。  
LinkedList 实现 List 接口，能对它进行队列操作。  
LinkedList 实现 Deque 接口，即能将LinkedList当作双端队列使用。  
LinkedList 实现了Cloneable接口，即覆盖了函数clone()，能克隆。  
LinkedList 实现java.io.Serializable接口，这意味着LinkedList支持序列化，能通过序列化去传输。  
LinkedList 是非同步的。

**LinkedList构造函数**

// 默认构造函数
    LinkedList()
    
    // 创建一个LinkedList，保护Collection中的全部元素。
    LinkedList(Collection<? extends E> collection)

**LinkedList的API**

![复制代码][copycode.gif]

LinkedList的API
    boolean       add(E object)
    void          add(int location, E object)
    boolean       addAll(Collection<? extends E> collection)
    boolean       addAll(int location, Collection<? extends E> collection)
    void          addFirst(E object)
    void          addLast(E object)
    void          clear()
    Object        clone()
    boolean       contains(Object object)
    Iterator<E>   descendingIterator()
    E             element()
    E             get(int location)
    E             getFirst()
    E             getLast()
    int           indexOf(Object object)
    int           lastIndexOf(Object object)
    ListIterator<E>     listIterator(int location)
    boolean       offer(E o)
    boolean       offerFirst(E e)
    boolean       offerLast(E e)
    E             peek()
    E             peekFirst()
    E             peekLast()
    E             poll()
    E             pollFirst()
    E             pollLast()
    E             pop()
    void          push(E e)
    E             remove()
    E             remove(int location)
    boolean       remove(Object object)
    E             removeFirst()
    boolean       removeFirstOccurrence(Object o)
    E             removeLast()
    boolean       removeLastOccurrence(Object o)
    E             set(int location, E object)
    int           size()
    <T> T[]       toArray(T[] contents)
    Object[]     toArray()

![复制代码][copycode.gif]

**AbstractSequentialList简介**

在介绍LinkedList的源码之前，先介绍一下AbstractSequentialList。毕竟，LinkedList是AbstractSequentialList的子类。

AbstractSequentialList 实现了get(int index)、set(int index, E element)、add(int index, E element) 和 remove(int index)这些函数。**这些接口都是随机访问List的**，LinkedList是双向链表；既然它继承于AbstractSequentialList，就相当于已经实现了“get(int index)这些接口”。

此外，我们若需要通过AbstractSequentialList自己实现一个列表，只需要扩展此类，并提供 listIterator() 和 size() 方法的实现即可。若要实现不可修改的列表，则需要实现列表迭代器的 hasNext、next、hasPrevious、previous 和 index 方法即可。

### **第2部分 LinkedList数据结构** ###

**LinkedList的继承关系**

![复制代码][copycode.gif]

java.lang.Object
       ↳     java.util.AbstractCollection<E>
             ↳     java.util.AbstractList<E>
                   ↳     java.util.AbstractSequentialList<E>
                         ↳     java.util.LinkedList<E>
    
    public class LinkedList<E>
        extends AbstractSequentialList<E>
        implements List<E>, Deque<E>, Cloneable, java.io.Serializable {}

![复制代码][copycode.gif]

**LinkedList与Collection关系如下图：**

[![272345393446232.jpg][]][272345393446232.jpg]

LinkedList的本质是双向链表。  
(01) LinkedList继承于AbstractSequentialList，并且实现了Dequeue接口。   
(02) LinkedList包含两个重要的成员：header 和 size。  
　　header是双向链表的表头，它是双向链表节点所对应的类Entry的实例。Entry中包含成员变量： previous, next, element。其中，previous是该节点的上一个节点，next是该节点的下一个节点，element是该节点所包含的值。   
　　size是双向链表中节点的个数。

### 第3部分 LinkedList源码解析(基于JDK1.6.0\_45) ###

为了更了解LinkedList的原理，**下面对LinkedList源码代码作出分析**。

在阅读源码之前，我们先对LinkedList的整体实现进行大致说明：  
    LinkedList实际上是通过双向链表去实现的。既然是双向链表，那么它的**顺序访问会非常高效，而随机访问效率比较低**。  
    既然LinkedList是通过双向链表的，但是它也实现了List接口\{ *也就是说，它实现了get(int location)、remove(int location)等“根据**索引值**来获取、删除节点的函数”*\}。LinkedList是如何实现List的这些接口的，如何将“**双向链表和索引值联系起来的**”？  
    实际原理非常简单，它就是通过一个**计数索引值**来实现的。例如，当我们调用get(int location)时，首先会比较“location”和“双向链表长度的1/2”；若前者大，则从链表头开始往后查找，直到location位置；否则，从链表末尾开始先前查找，直到location位置。  
   这就是“双线链表和索引值联系起来”的方法。

好了，接下来开始阅读源码(只要理解双向链表，那么LinkedList的源码很容易理解的)。

![ExpandedBlockStart.gif][]

![复制代码][copycode.gif]

1 package java.util;
      2 
      3 public class LinkedList<E>
      4     extends AbstractSequentialList<E>
      5     implements List<E>, Deque<E>, Cloneable, java.io.Serializable
      6 {
      7     // 链表的表头，表头不包含任何数据。Entry是个链表类数据结构。
      8     private transient Entry<E> header = new Entry<E>(null, null, null);
      9 
     10     // LinkedList中元素个数
     11     private transient int size = 0;
     12 
     13     // 默认构造函数：创建一个空的链表
     14     public LinkedList() {
     15         header.next = header.previous = header;
     16     }
     17 
     18     // 包含“集合”的构造函数:创建一个包含“集合”的LinkedList
     19     public LinkedList(Collection<? extends E> c) {
     20         this();
     21         addAll(c);
     22     }
     23 
     24     // 获取LinkedList的第一个元素
     25     public E getFirst() {
     26         if (size==0)
     27             throw new NoSuchElementException();
     28 
     29         // 链表的表头header中不包含数据。
     30         // 这里返回header所指下一个节点所包含的数据。
     31         return header.next.element;
     32     }
     33 
     34     // 获取LinkedList的最后一个元素
     35     public E getLast()  {
     36         if (size==0)
     37             throw new NoSuchElementException();
     38 
     39         // 由于LinkedList是双向链表；而表头header不包含数据。
     40         // 因而，这里返回表头header的前一个节点所包含的数据。
     41         return header.previous.element;
     42     }
     43 
     44     // 删除LinkedList的第一个元素
     45     public E removeFirst() {
     46         return remove(header.next);
     47     }
     48 
     49     // 删除LinkedList的最后一个元素
     50     public E removeLast() {
     51         return remove(header.previous);
     52     }
     53 
     54     // 将元素添加到LinkedList的起始位置
     55     public void addFirst(E e) {
     56         addBefore(e, header.next);
     57     }
     58 
     59     // 将元素添加到LinkedList的结束位置
     60     public void addLast(E e) {
     61         addBefore(e, header);
     62     }
     63 
     64     // 判断LinkedList是否包含元素(o)
     65     public boolean contains(Object o) {
     66         return indexOf(o) != -1;
     67     }
     68 
     69     // 返回LinkedList的大小
     70     public int size() {
     71         return size;
     72     }
     73 
     74     // 将元素(E)添加到LinkedList中
     75     public boolean add(E e) {
     76         // 将节点(节点数据是e)添加到表头(header)之前。
     77         // 即，将节点添加到双向链表的末端。
     78         addBefore(e, header);
     79         return true;
     80     }
     81 
     82     // 从LinkedList中删除元素(o)
     83     // 从链表开始查找，如存在元素(o)则删除该元素并返回true；
     84     // 否则，返回false。
     85     public boolean remove(Object o) {
     86         if (o==null) {
     87             // 若o为null的删除情况
     88             for (Entry<E> e = header.next; e != header; e = e.next) {
     89                 if (e.element==null) {
     90                     remove(e);
     91                     return true;
     92                 }
     93             }
     94         } else {
     95             // 若o不为null的删除情况
     96             for (Entry<E> e = header.next; e != header; e = e.next) {
     97                 if (o.equals(e.element)) {
     98                     remove(e);
     99                     return true;
    100                 }
    101             }
    102         }
    103         return false;
    104     }
    105 
    106     // 将“集合(c)”添加到LinkedList中。
    107     // 实际上，是从双向链表的末尾开始，将“集合(c)”添加到双向链表中。
    108     public boolean addAll(Collection<? extends E> c) {
    109         return addAll(size, c);
    110     }
    111 
    112     // 从双向链表的index开始，将“集合(c)”添加到双向链表中。
    113     public boolean addAll(int index, Collection<? extends E> c) {
    114         if (index < 0 || index > size)
    115             throw new IndexOutOfBoundsException("Index: "+index+
    116                                                 ", Size: "+size);
    117         Object[] a = c.toArray();
    118         // 获取集合的长度
    119         int numNew = a.length;
    120         if (numNew==0)
    121             return false;
    122         modCount++;
    123 
    124         // 设置“当前要插入节点的后一个节点”
    125         Entry<E> successor = (index==size ? header : entry(index));
    126         // 设置“当前要插入节点的前一个节点”
    127         Entry<E> predecessor = successor.previous;
    128         // 将集合(c)全部插入双向链表中
    129         for (int i=0; i<numNew; i++) {
    130             Entry<E> e = new Entry<E>((E)a[i], successor, predecessor);
    131             predecessor.next = e;
    132             predecessor = e;
    133         }
    134         successor.previous = predecessor;
    135 
    136         // 调整LinkedList的实际大小
    137         size += numNew;
    138         return true;
    139     }
    140 
    141     // 清空双向链表
    142     public void clear() {
    143         Entry<E> e = header.next;
    144         // 从表头开始，逐个向后遍历；对遍历到的节点执行一下操作：
    145         // (01) 设置前一个节点为null 
    146         // (02) 设置当前节点的内容为null 
    147         // (03) 设置后一个节点为“新的当前节点”
    148         while (e != header) {
    149             Entry<E> next = e.next;
    150             e.next = e.previous = null;
    151             e.element = null;
    152             e = next;
    153         }
    154         header.next = header.previous = header;
    155         // 设置大小为0
    156         size = 0;
    157         modCount++;
    158     }
    159 
    160     // 返回LinkedList指定位置的元素
    161     public E get(int index) {
    162         return entry(index).element;
    163     }
    164 
    165     // 设置index位置对应的节点的值为element
    166     public E set(int index, E element) {
    167         Entry<E> e = entry(index);
    168         E oldVal = e.element;
    169         e.element = element;
    170         return oldVal;
    171     }
    172  
    173     // 在index前添加节点，且节点的值为element
    174     public void add(int index, E element) {
    175         addBefore(element, (index==size ? header : entry(index)));
    176     }
    177 
    178     // 删除index位置的节点
    179     public E remove(int index) {
    180         return remove(entry(index));
    181     }
    182 
    183     // 获取双向链表中指定位置的节点
    184     private Entry<E> entry(int index) {
    185         if (index < 0 || index >= size)
    186             throw new IndexOutOfBoundsException("Index: "+index+
    187                                                 ", Size: "+size);
    188         Entry<E> e = header;
    189         // 获取index处的节点。
    190         // 若index < 双向链表长度的1/2,则从前先后查找;
    191         // 否则，从后向前查找。
    192         if (index < (size >> 1)) {
    193             for (int i = 0; i <= index; i++)
    194                 e = e.next;
    195         } else {
    196             for (int i = size; i > index; i--)
    197                 e = e.previous;
    198         }
    199         return e;
    200     }
    201 
    202     // 从前向后查找，返回“值为对象(o)的节点对应的索引”
    203     // 不存在就返回-1
    204     public int indexOf(Object o) {
    205         int index = 0;
    206         if (o==null) {
    207             for (Entry e = header.next; e != header; e = e.next) {
    208                 if (e.element==null)
    209                     return index;
    210                 index++;
    211             }
    212         } else {
    213             for (Entry e = header.next; e != header; e = e.next) {
    214                 if (o.equals(e.element))
    215                     return index;
    216                 index++;
    217             }
    218         }
    219         return -1;
    220     }
    221 
    222     // 从后向前查找，返回“值为对象(o)的节点对应的索引”
    223     // 不存在就返回-1
    224     public int lastIndexOf(Object o) {
    225         int index = size;
    226         if (o==null) {
    227             for (Entry e = header.previous; e != header; e = e.previous) {
    228                 index--;
    229                 if (e.element==null)
    230                     return index;
    231             }
    232         } else {
    233             for (Entry e = header.previous; e != header; e = e.previous) {
    234                 index--;
    235                 if (o.equals(e.element))
    236                     return index;
    237             }
    238         }
    239         return -1;
    240     }
    241 
    242     // 返回第一个节点
    243     // 若LinkedList的大小为0,则返回null
    244     public E peek() {
    245         if (size==0)
    246             return null;
    247         return getFirst();
    248     }
    249 
    250     // 返回第一个节点
    251     // 若LinkedList的大小为0,则抛出异常
    252     public E element() {
    253         return getFirst();
    254     }
    255 
    256     // 删除并返回第一个节点
    257     // 若LinkedList的大小为0,则返回null
    258     public E poll() {
    259         if (size==0)
    260             return null;
    261         return removeFirst();
    262     }
    263 
    264     // 将e添加双向链表末尾
    265     public boolean offer(E e) {
    266         return add(e);
    267     }
    268 
    269     // 将e添加双向链表开头
    270     public boolean offerFirst(E e) {
    271         addFirst(e);
    272         return true;
    273     }
    274 
    275     // 将e添加双向链表末尾
    276     public boolean offerLast(E e) {
    277         addLast(e);
    278         return true;
    279     }
    280 
    281     // 返回第一个节点
    282     // 若LinkedList的大小为0,则返回null
    283     public E peekFirst() {
    284         if (size==0)
    285             return null;
    286         return getFirst();
    287     }
    288 
    289     // 返回最后一个节点
    290     // 若LinkedList的大小为0,则返回null
    291     public E peekLast() {
    292         if (size==0)
    293             return null;
    294         return getLast();
    295     }
    296 
    297     // 删除并返回第一个节点
    298     // 若LinkedList的大小为0,则返回null
    299     public E pollFirst() {
    300         if (size==0)
    301             return null;
    302         return removeFirst();
    303     }
    304 
    305     // 删除并返回最后一个节点
    306     // 若LinkedList的大小为0,则返回null
    307     public E pollLast() {
    308         if (size==0)
    309             return null;
    310         return removeLast();
    311     }
    312 
    313     // 将e插入到双向链表开头
    314     public void push(E e) {
    315         addFirst(e);
    316     }
    317 
    318     // 删除并返回第一个节点
    319     public E pop() {
    320         return removeFirst();
    321     }
    322 
    323     // 从LinkedList开始向后查找，删除第一个值为元素(o)的节点
    324     // 从链表开始查找，如存在节点的值为元素(o)的节点，则删除该节点
    325     public boolean removeFirstOccurrence(Object o) {
    326         return remove(o);
    327     }
    328 
    329     // 从LinkedList末尾向前查找，删除第一个值为元素(o)的节点
    330     // 从链表开始查找，如存在节点的值为元素(o)的节点，则删除该节点
    331     public boolean removeLastOccurrence(Object o) {
    332         if (o==null) {
    333             for (Entry<E> e = header.previous; e != header; e = e.previous) {
    334                 if (e.element==null) {
    335                     remove(e);
    336                     return true;
    337                 }
    338             }
    339         } else {
    340             for (Entry<E> e = header.previous; e != header; e = e.previous) {
    341                 if (o.equals(e.element)) {
    342                     remove(e);
    343                     return true;
    344                 }
    345             }
    346         }
    347         return false;
    348     }
    349 
    350     // 返回“index到末尾的全部节点”对应的ListIterator对象(List迭代器)
    351     public ListIterator<E> listIterator(int index) {
    352         return new ListItr(index);
    353     }
    354 
    355     // List迭代器
    356     private class ListItr implements ListIterator<E> {
    357         // 上一次返回的节点
    358         private Entry<E> lastReturned = header;
    359         // 下一个节点
    360         private Entry<E> next;
    361         // 下一个节点对应的索引值
    362         private int nextIndex;
    363         // 期望的改变计数。用来实现fail-fast机制。
    364         private int expectedModCount = modCount;
    365 
    366         // 构造函数。
    367         // 从index位置开始进行迭代
    368         ListItr(int index) {
    369             // index的有效性处理
    370             if (index < 0 || index > size)
    371                 throw new IndexOutOfBoundsException("Index: "+index+ ", Size: "+size);
    372             // 若 “index 小于 ‘双向链表长度的一半’”，则从第一个元素开始往后查找；
    373             // 否则，从最后一个元素往前查找。
    374             if (index < (size >> 1)) {
    375                 next = header.next;
    376                 for (nextIndex=0; nextIndex<index; nextIndex++)
    377                     next = next.next;
    378             } else {
    379                 next = header;
    380                 for (nextIndex=size; nextIndex>index; nextIndex--)
    381                     next = next.previous;
    382             }
    383         }
    384 
    385         // 是否存在下一个元素
    386         public boolean hasNext() {
    387             // 通过元素索引是否等于“双向链表大小”来判断是否达到最后。
    388             return nextIndex != size;
    389         }
    390 
    391         // 获取下一个元素
    392         public E next() {
    393             checkForComodification();
    394             if (nextIndex == size)
    395                 throw new NoSuchElementException();
    396 
    397             lastReturned = next;
    398             // next指向链表的下一个元素
    399             next = next.next;
    400             nextIndex++;
    401             return lastReturned.element;
    402         }
    403 
    404         // 是否存在上一个元素
    405         public boolean hasPrevious() {
    406             // 通过元素索引是否等于0，来判断是否达到开头。
    407             return nextIndex != 0;
    408         }
    409 
    410         // 获取上一个元素
    411         public E previous() {
    412             if (nextIndex == 0)
    413             throw new NoSuchElementException();
    414 
    415             // next指向链表的上一个元素
    416             lastReturned = next = next.previous;
    417             nextIndex--;
    418             checkForComodification();
    419             return lastReturned.element;
    420         }
    421 
    422         // 获取下一个元素的索引
    423         public int nextIndex() {
    424             return nextIndex;
    425         }
    426 
    427         // 获取上一个元素的索引
    428         public int previousIndex() {
    429             return nextIndex-1;
    430         }
    431 
    432         // 删除当前元素。
    433         // 删除双向链表中的当前节点
    434         public void remove() {
    435             checkForComodification();
    436             Entry<E> lastNext = lastReturned.next;
    437             try {
    438                 LinkedList.this.remove(lastReturned);
    439             } catch (NoSuchElementException e) {
    440                 throw new IllegalStateException();
    441             }
    442             if (next==lastReturned)
    443                 next = lastNext;
    444             else
    445                 nextIndex--;
    446             lastReturned = header;
    447             expectedModCount++;
    448         }
    449 
    450         // 设置当前节点为e
    451         public void set(E e) {
    452             if (lastReturned == header)
    453                 throw new IllegalStateException();
    454             checkForComodification();
    455             lastReturned.element = e;
    456         }
    457 
    458         // 将e添加到当前节点的前面
    459         public void add(E e) {
    460             checkForComodification();
    461             lastReturned = header;
    462             addBefore(e, next);
    463             nextIndex++;
    464             expectedModCount++;
    465         }
    466 
    467         // 判断 “modCount和expectedModCount是否相等”，依次来实现fail-fast机制。
    468         final void checkForComodification() {
    469             if (modCount != expectedModCount)
    470             throw new ConcurrentModificationException();
    471         }
    472     }
    473 
    474     // 双向链表的节点所对应的数据结构。
    475     // 包含3部分：上一节点，下一节点，当前节点值。
    476     private static class Entry<E> {
    477         // 当前节点所包含的值
    478         E element;
    479         // 下一个节点
    480         Entry<E> next;
    481         // 上一个节点
    482         Entry<E> previous;
    483 
    484         /**
    485          * 链表节点的构造函数。
    486          * 参数说明：
    487          *   element  —— 节点所包含的数据
    488          *   next      —— 下一个节点
    489          *   previous —— 上一个节点
    490          */
    491         Entry(E element, Entry<E> next, Entry<E> previous) {
    492             this.element = element;
    493             this.next = next;
    494             this.previous = previous;
    495         }
    496     }
    497 
    498     // 将节点(节点数据是e)添加到entry节点之前。
    499     private Entry<E> addBefore(E e, Entry<E> entry) {
    500         // 新建节点newEntry，将newEntry插入到节点e之前；并且设置newEntry的数据是e
    501         Entry<E> newEntry = new Entry<E>(e, entry, entry.previous);
    502         newEntry.previous.next = newEntry;
    503         newEntry.next.previous = newEntry;
    504         // 修改LinkedList大小
    505         size++;
    506         // 修改LinkedList的修改统计数：用来实现fail-fast机制。
    507         modCount++;
    508         return newEntry;
    509     }
    510 
    511     // 将节点从链表中删除
    512     private E remove(Entry<E> e) {
    513         if (e == header)
    514             throw new NoSuchElementException();
    515 
    516         E result = e.element;
    517         e.previous.next = e.next;
    518         e.next.previous = e.previous;
    519         e.next = e.previous = null;
    520         e.element = null;
    521         size--;
    522         modCount++;
    523         return result;
    524     }
    525 
    526     // 反向迭代器
    527     public Iterator<E> descendingIterator() {
    528         return new DescendingIterator();
    529     }
    530 
    531     // 反向迭代器实现类。
    532     private class DescendingIterator implements Iterator {
    533         final ListItr itr = new ListItr(size());
    534         // 反向迭代器是否下一个元素。
    535         // 实际上是判断双向链表的当前节点是否达到开头
    536         public boolean hasNext() {
    537             return itr.hasPrevious();
    538         }
    539         // 反向迭代器获取下一个元素。
    540         // 实际上是获取双向链表的前一个节点
    541         public E next() {
    542             return itr.previous();
    543         }
    544         // 删除当前节点
    545         public void remove() {
    546             itr.remove();
    547         }
    548     }
    549 
    550 
    551     // 返回LinkedList的Object[]数组
    552     public Object[] toArray() {
    553     // 新建Object[]数组
    554     Object[] result = new Object[size];
    555         int i = 0;
    556         // 将链表中所有节点的数据都添加到Object[]数组中
    557         for (Entry<E> e = header.next; e != header; e = e.next)
    558             result[i++] = e.element;
    559     return result;
    560     }
    561 
    562     // 返回LinkedList的模板数组。所谓模板数组，即可以将T设为任意的数据类型
    563     public <T> T[] toArray(T[] a) {
    564         // 若数组a的大小 < LinkedList的元素个数(意味着数组a不能容纳LinkedList中全部元素)
    565         // 则新建一个T[]数组，T[]的大小为LinkedList大小，并将该T[]赋值给a。
    566         if (a.length < size)
    567             a = (T[])java.lang.reflect.Array.newInstance(
    568                                 a.getClass().getComponentType(), size);
    569         // 将链表中所有节点的数据都添加到数组a中
    570         int i = 0;
    571         Object[] result = a;
    572         for (Entry<E> e = header.next; e != header; e = e.next)
    573             result[i++] = e.element;
    574 
    575         if (a.length > size)
    576             a[size] = null;
    577 
    578         return a;
    579     }
    580 
    581 
    582     // 克隆函数。返回LinkedList的克隆对象。
    583     public Object clone() {
    584         LinkedList<E> clone = null;
    585         // 克隆一个LinkedList克隆对象
    586         try {
    587             clone = (LinkedList<E>) super.clone();
    588         } catch (CloneNotSupportedException e) {
    589             throw new InternalError();
    590         }
    591 
    592         // 新建LinkedList表头节点
    593         clone.header = new Entry<E>(null, null, null);
    594         clone.header.next = clone.header.previous = clone.header;
    595         clone.size = 0;
    596         clone.modCount = 0;
    597 
    598         // 将链表中所有节点的数据都添加到克隆对象中
    599         for (Entry<E> e = header.next; e != header; e = e.next)
    600             clone.add(e.element);
    601 
    602         return clone;
    603     }
    604 
    605     // java.io.Serializable的写入函数
    606     // 将LinkedList的“容量，所有的元素值”都写入到输出流中
    607     private void writeObject(java.io.ObjectOutputStream s)
    608         throws java.io.IOException {
    609         // Write out any hidden serialization magic
    610         s.defaultWriteObject();
    611 
    612         // 写入“容量”
    613         s.writeInt(size);
    614 
    615         // 将链表中所有节点的数据都写入到输出流中
    616         for (Entry e = header.next; e != header; e = e.next)
    617             s.writeObject(e.element);
    618     }
    619 
    620     // java.io.Serializable的读取函数：根据写入方式反向读出
    621     // 先将LinkedList的“容量”读出，然后将“所有的元素值”读出
    622     private void readObject(java.io.ObjectInputStream s)
    623         throws java.io.IOException, ClassNotFoundException {
    624         // Read in any hidden serialization magic
    625         s.defaultReadObject();
    626 
    627         // 从输入流中读取“容量”
    628         int size = s.readInt();
    629 
    630         // 新建链表表头节点
    631         header = new Entry<E>(null, null, null);
    632         header.next = header.previous = header;
    633 
    634         // 从输入流中将“所有的元素值”并逐个添加到链表中
    635         for (int i=0; i<size; i++)
    636             addBefore((E)s.readObject(), header);
    637     }
    638 
    639 }

![复制代码][copycode.gif]

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

总结起来如下表格：

第一个元素（头部） 最后一个元素（尾部）
            抛出异常        特殊值            抛出异常        特殊值
    插入    addFirst(e)    offerFirst(e)    addLast(e)        offerLast(e)
    移除    removeFirst()  pollFirst()      removeLast()    pollLast()
    检查    getFirst()     peekFirst()      getLast()        peekLast()

(06) LinkedList可以作为**FIFO**(先进先出)的队列，作为FIFO的队列时，下表的方法等价：

![复制代码][copycode.gif]

队列方法 等效方法
    add(e)        addLast(e)
    offer(e)      offerLast(e)
    remove()      removeFirst()
    poll()        pollFirst()
    element()     getFirst()
    peek()        peekFirst()

![复制代码][copycode.gif]

(07) LinkedList可以作为**LIFO**(后进先出)的栈，作为LIFO的栈时，下表的方法等价：

栈方法 等效方法
    push(e)      addFirst(e)
    pop()        removeFirst()
    peek()       peekFirst()

### 第4部分 LinkedList遍历方式 ###

**LinkedList遍历方式**

LinkedList支持多种遍历方式。建议不要采用随机访问的方式去遍历LinkedList，而采用逐个遍历的方式。  
(01) 第一种，通过**迭代器**遍历。即通过Iterator去遍历。

for(Iterator iter = list.iterator(); iter.hasNext();)
        iter.next();

(02) 通过**快速随机**访问遍历LinkedList

int size = list.size();
    for (int i=0; i<size; i++) {
        list.get(i);        
    }

(03) 通过**另外一种for循环**来遍历LinkedList

for (Integer integ:list) 
        ;

(04) 通过**pollFirst()**来遍历LinkedList

while(list.pollFirst() != null)
        ;

(05) 通过**pollLast()**来遍历LinkedList

while(list.pollLast() != null)
        ;

(06) 通过**removeFirst()**来遍历LinkedList

try {
        while(list.removeFirst() != null)
            ;
    } catch (NoSuchElementException e) {
    }

(07) 通过**removeLast()**来遍历LinkedList

try {
        while(list.removeLast() != null)
            ;
    } catch (NoSuchElementException e) {
    }

**测试这些遍历方式效率的代码如下**：

![ContractedBlock.gif][]

**执行结果**：

![复制代码][copycode.gif]

iteratorLinkedListThruIterator：8 ms
    iteratorLinkedListThruForeach：3724 ms
    iteratorThroughFor2：5 ms
    iteratorThroughPollFirst：8 ms
    iteratorThroughPollLast：6 ms
    iteratorThroughRemoveFirst：2 ms
    iteratorThroughRemoveLast：2 ms

![复制代码][copycode.gif]

由此可见，遍历LinkedList时，使用removeFist()或removeLast()效率最高。但用它们遍历时，会删除原始数据；若单纯只读取，而不删除，应该使用第3种遍历方式。  
**无论如何，千万不要通过随机访问去遍历LinkedList！**

### 第5部分 LinkedList示例 ###

下面通过一个示例来学习如何使用LinkedList的常用API

![ContractedBlock.gif][]

**运行结果**：

![复制代码][copycode.gif]

Test "addFirst(), removeFirst(), getFirst()"
    llist:[10, 1, 4, 2, 3]
    llist.removeFirst():10
    llist:[1, 4, 2, 3]
    llist.getFirst():1
    
    Test "offerFirst(), pollFirst(), peekFirst()"
    llist:[10, 1, 4, 2, 3]
    llist.pollFirst():10
    llist:[1, 4, 2, 3]
    llist.peekFirst():1
    
    Test "addLast(), removeLast(), getLast()"
    llist:[1, 4, 2, 3, 20]
    llist.removeLast():20
    llist:[1, 4, 2, 3]
    llist.getLast():3
    
    Test "offerLast(), pollLast(), peekLast()"
    llist:[1, 4, 2, 3, 20]
    llist.pollLast():20
    llist:[1, 4, 2, 3]
    llist.peekLast():3
    
    get(3):300
    str:1
    str:4
    str:300
    str:3
    size:4
    isEmpty():true
    
    
    useLinkedListAsLIFO
    stack:[4, 3, 2, 1]
    stack.pop():4
    stack.peek():3
    stack:[3, 2, 1]
    
    useLinkedListAsFIFO
    queue:[10, 20, 30, 40]
    queue.remove():10
    queue.element():20
    queue:[20, 30, 40]

![复制代码][copycode.gif]

--------------------

**更多内容**

01. [Java 集合系列目录][Java]

02. [Java 集合系列01之 总体框架][Java _01_]

03. [Java 集合系列03之 ArrayList详细介绍(源码解析)和使用示例][Java _03_ ArrayList]

04. [Java 集合系列08之 List总结(LinkedList, ArrayList等使用场景和性能分析)][Java _08_ List_LinkedList_ ArrayList]

05. [Java 集合系列18之 Iterator和Enumeration比较][Java _18_ Iterator_Enumeration]

[1_ LinkedList]: https://www.cnblogs.com/skywang12345/p/3308807.html#a1
[2_ LinkedList]: https://www.cnblogs.com/skywang12345/p/3308807.html#a2
[3_ LinkedList_JDK1.6.0_45]: https://www.cnblogs.com/skywang12345/p/3308807.html#a3
[4_ LinkedList]: https://www.cnblogs.com/skywang12345/p/3308807.html#a4
[5_ LinkedList]: https://www.cnblogs.com/skywang12345/p/3308807.html#a5
[http_www.cnblogs.com_skywang12345_p_3308807.html]: http://www.cnblogs.com/skywang12345/p/3308807.html
[copycode.gif]: /images/20220522/ce89b2e29ef34c068085df3cbd8209ec.png
[272345393446232.jpg]: /images/20220522/60696d7016f64ce8a3c44e2e5f75955f.png
[ExpandedBlockStart.gif]: /images/20220522/ebf3a6b7867b419c9cfd5ba0c6cff5f9.png
[ContractedBlock.gif]: /images/20220522/ff37e36d5a594dafac27b8f5c83ebc16.png
[Java]: http://www.cnblogs.com/skywang12345/p/3323085.html
[Java _01_]: http://www.cnblogs.com/skywang12345/p/3308498.html
[Java _03_ ArrayList]: http://www.cnblogs.com/skywang12345/p/3308556.html
[Java _08_ List_LinkedList_ ArrayList]: http://www.cnblogs.com/skywang12345/p/3308900.html
[Java _18_ Iterator_Enumeration]: http://www.cnblogs.com/skywang12345/p/3311275.html