转载请注明出处：

 

第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
      collection)

 

LinkedList的API 

LinkedList的APIboolean       add(E object)void          add(int location, E object)boolean       addAll(Collection
      collection)boolean       addAll(int location, Collection
      collection)void          addFirst(E object)void          addLast(E object)void          clear()Object        clone()boolean       contains(Object object)Iterator
     
         descendingIterator()E             element()E             get(int location)E             getFirst()E             getLast()int           indexOf(Object object)int           lastIndexOf(Object object)ListIterator
      
            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[]       toArray(T[] contents)Object[]     toArray()
       
      
     

 

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的继承关系

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

 

LinkedList与Collection关系如下图：

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的源码很容易理解的)。

1 package java.util;  2   3 public class LinkedList
      
         4     extends AbstractSequentialList
       
          5     implements List
        
         , Deque
         
          , Cloneable, java.io.Serializable  6 {  7     // 链表的表头，表头不包含任何数据。Entry是个链表类数据结构。  8     private transient Entry
          
            header = new Entry
           
            (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
             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 = 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 = 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
               c) {109 return addAll(size, c);110 }111 112 // 从双向链表的index开始，将“集合(c)”添加到双向链表中。113 public boolean addAll(int index, Collection
               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
              
                successor = (index==size ? header : entry(index));126 // 设置“当前要插入节点的前一个节点”127 Entry
               
                 predecessor = successor.previous;128 // 将集合(c)全部插入双向链表中129 for (int i=0; i
                
                  e = new Entry
                 
                  ((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 = header.next;144 // 从表头开始，逐个向后遍历；对遍历到的节点执行一下操作：145 // (01) 设置前一个节点为null 146 // (02) 设置当前节点的内容为null 147 // (03) 设置后一个节点为“新的当前节点”148 while (e != header) {149 Entry
                   
                     next = e.next;150 e.next = e.previous = null;151 e.element = null;152 e = next;153 }154 header.next = header.previous = header;155 // 设置大小为0156 size = 0;157 modCount++;158 }159 160 // 返回LinkedList指定位置的元素161 public E get(int index) {162 return entry(index).element;163 }164 165 // 设置index位置对应的节点的值为element166 public E set(int index, E element) {167 Entry
                    
                      e = entry(index);168 E oldVal = e.element;169 e.element = element;170 return oldVal;171 }172 173 // 在index前添加节点，且节点的值为element174 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
                     
                       entry(int index) {185 if (index < 0 || index >= size)186 throw new IndexOutOfBoundsException("Index: "+index+187 ", Size: "+size);188 Entry
                      
                        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 // 不存在就返回-1204 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 // 不存在就返回-1224 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,则返回null244 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,则返回null258 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,则返回null283 public E peekFirst() {284 if (size==0)285 return null;286 return getFirst();287 }288 289 // 返回最后一个节点290 // 若LinkedList的大小为0,则返回null291 public E peekLast() {292 if (size==0)293 return null;294 return getLast();295 }296 297 // 删除并返回第一个节点298 // 若LinkedList的大小为0,则返回null299 public E pollFirst() {300 if (size==0)301 return null;302 return removeFirst();303 }304 305 // 删除并返回最后一个节点306 // 若LinkedList的大小为0,则返回null307 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 = 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 = 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
                         
                           listIterator(int index) {352 return new ListItr(index);353 }354 355 // List迭代器356 private class ListItr implements ListIterator
                          
                            {357 // 上一次返回的节点358 private Entry
                           
                             lastReturned = header;359 // 下一个节点360 private Entry
                            
                              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--)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
                              
                                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 else445 nextIndex--;446 lastReturned = header;447 expectedModCount++;448 }449 450 // 设置当前节点为e451 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
                               
                                 {477 // 当前节点所包含的值478 E element;479 // 下一个节点480 Entry
                                
                                  next;481 // 上一个节点482 Entry
                                 
                                   previous;483 484 /**485 * 链表节点的构造函数。486 * 参数说明：487 * element —— 节点所包含的数据488 * next —— 下一个节点489 * previous —— 上一个节点490 */491 Entry(E element, Entry
                                  
                                    next, Entry
                                   
                                     previous) {492 this.element = element;493 this.next = next;494 this.previous = previous;495 }496 }497 498 // 将节点(节点数据是e)添加到entry节点之前。499 private Entry
                                    
                                      addBefore(E e, Entry
                                     
                                       entry) {500 // 新建节点newEntry，将newEntry插入到节点e之前；并且设置newEntry的数据是e501 Entry
                                      
                                        newEntry = new Entry
                                       
                                        (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) {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
                                         
                                           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 = header.next; e != header; e = e.next)558 result[i++] = e.element;559 return result;560 }561 562 // 返回LinkedList的模板数组。所谓模板数组，即可以将T设为任意的数据类型563 public 
                                           
                                             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 = 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
                                             
                                               clone = null;585 // 克隆一个LinkedList克隆对象586 try {587 clone = (LinkedList
                                              
                                               ) super.clone();588 } catch (CloneNotSupportedException e) {589 throw new InternalError();590 }591 592 // 新建LinkedList表头节点593 clone.header = new Entry
                                               
                                                (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 = 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 magic610 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 magic625 s.defaultReadObject();626 627 // 从输入流中读取“容量”628 int size = s.readInt();629 630 // 新建链表表头节点631 header = new Entry
                                                 
                                                  (null, null, null);632 header.next = header.previous = header;633 634 // 从输入流中将“所有的元素值”并逐个添加到链表中635 for (int i=0; i
                                                 
                                                
                                               
                                              
                                             
                                            
                                           
                                          
                                         
                                        
                                       
                                      
                                     
                                    
                                   
                                  
                                 
                                
                               
                              
                             
                            
                           
                          
                         
                        
                       
                      
                     
                    
                   
                  
                 
                
               
              
             
            
           
          
         
        
       
      

总结：

(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的队列时，下表的方法等价：

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

(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

(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) {}

 

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

1 import java.util.List;  2 import java.util.Iterator;  3 import java.util.LinkedList;  4 import java.util.NoSuchElementException;  5   6 /*  7  * @desc 测试LinkedList的几种遍历方式和效率  8  *  9  * @author skywang 10  */ 11 public class LinkedListThruTest { 12     public static void main(String[] args) { 13         // 通过Iterator遍历LinkedList 14         iteratorLinkedListThruIterator(getLinkedList()) ; 15          16         // 通过快速随机访问遍历LinkedList 17         iteratorLinkedListThruForeach(getLinkedList()) ; 18  19         // 通过for循环的变种来访问遍历LinkedList 20         iteratorThroughFor2(getLinkedList()) ; 21  22         // 通过PollFirst()遍历LinkedList 23         iteratorThroughPollFirst(getLinkedList()) ; 24  25         // 通过PollLast()遍历LinkedList 26         iteratorThroughPollLast(getLinkedList()) ; 27  28         // 通过removeFirst()遍历LinkedList 29         iteratorThroughRemoveFirst(getLinkedList()) ; 30  31         // 通过removeLast()遍历LinkedList 32         iteratorThroughRemoveLast(getLinkedList()) ; 33     } 34      35     private static LinkedList getLinkedList() { 36         LinkedList llist = new LinkedList(); 37         for (int i=0; i<100000; i++) 38             llist.addLast(i); 39  40         return llist; 41     } 42     /** 43      * 通过快迭代器遍历LinkedList 44      */ 45     private static void iteratorLinkedListThruIterator(LinkedList
      
        list) { 46         if (list == null) 47             return ; 48  49         // 记录开始时间 50         long start = System.currentTimeMillis(); 51          52         for(Iterator iter = list.iterator(); iter.hasNext();) 53             iter.next(); 54  55         // 记录结束时间 56         long end = System.currentTimeMillis(); 57         long interval = end - start; 58         System.out.println("iteratorLinkedListThruIterator：" + interval+" ms"); 59     } 60  61     /** 62      * 通过快速随机访问遍历LinkedList 63      */ 64     private static void iteratorLinkedListThruForeach(LinkedList
       
         list) { 65         if (list == null) 66             return ; 67  68         // 记录开始时间 69         long start = System.currentTimeMillis(); 70          71         int size = list.size(); 72         for (int i=0; i
        
          list) { 85         if (list == null) 86             return ; 87  88         // 记录开始时间 89         long start = System.currentTimeMillis(); 90          91         for (Integer integ:list)  92             ; 93  94         // 记录结束时间 95         long end = System.currentTimeMillis(); 96         long interval = end - start; 97         System.out.println("iteratorThroughFor2：" + interval+" ms"); 98     } 99 100     /**101      * 通过pollFirst()来遍历LinkedList102      */103     private static void iteratorThroughPollFirst(LinkedList
         
           list) {104         if (list == null)105             return ;106 107         // 记录开始时间108         long start = System.currentTimeMillis();109         while(list.pollFirst() != null)110             ;111 112         // 记录结束时间113         long end = System.currentTimeMillis();114         long interval = end - start;115         System.out.println("iteratorThroughPollFirst：" + interval+" ms");116     }117 118     /**119      * 通过pollLast()来遍历LinkedList120      */121     private static void iteratorThroughPollLast(LinkedList
          
            list) {122         if (list == null)123             return ;124 125         // 记录开始时间126         long start = System.currentTimeMillis();127         while(list.pollLast() != null)128             ;129 130         // 记录结束时间131         long end = System.currentTimeMillis();132         long interval = end - start;133         System.out.println("iteratorThroughPollLast：" + interval+" ms");134     }135 136     /**137      * 通过removeFirst()来遍历LinkedList138      */139     private static void iteratorThroughRemoveFirst(LinkedList
           
             list) {140 if (list == null)141 return ;142 143 // 记录开始时间144 long start = System.currentTimeMillis();145 try {146 while(list.removeFirst() != null)147 ;148 } catch (NoSuchElementException e) {149 }150 151 // 记录结束时间152 long end = System.currentTimeMillis();153 long interval = end - start;154 System.out.println("iteratorThroughRemoveFirst：" + interval+" ms");155 }156 157 /**158 * 通过removeLast()来遍历LinkedList159 */160 private static void iteratorThroughRemoveLast(LinkedList
            
              list) {161 if (list == null)162 return ;163 164 // 记录开始时间165 long start = System.currentTimeMillis();166 try {167 while(list.removeLast() != null)168 ;169 } catch (NoSuchElementException e) {170 }171 172 // 记录结束时间173 long end = System.currentTimeMillis();174 long interval = end - start;175 System.out.println("iteratorThroughRemoveLast：" + interval+" ms");176 }177 178 }
            
           
          
         
        
       
      

执行结果：

iteratorLinkedListThruIterator：8 msiteratorLinkedListThruForeach：3724 msiteratorThroughFor2：5 msiteratorThroughPollFirst：8 msiteratorThroughPollLast：6 msiteratorThroughRemoveFirst：2 msiteratorThroughRemoveLast：2 ms

由此可见，遍历LinkedList时，使用removeFist()或removeLast()效率最高。但用它们遍历时，会删除原始数据；若单纯只读取，而不删除，应该使用第3种遍历方式。

无论如何，千万不要通过随机访问去遍历LinkedList！

 

第5部分 LinkedList示例

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

 

运行结果：

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

注意: LinkedList是非线程安全的.