LinkedList源码剖析(三)

转载:http://vote.blog.csdn.net/Article/Details?articleid=35568011

LinkedList简介

LinkedList是基于双向循环链表(从源码中可以很容易看出)实现的,除了可以当做链表来操作外,它还可以当做栈、队列和双端队列来使用。

LinkedList同样是非线程安全的,只在单线程下适合使用。

LinkedList实现了Serializable接口,因此它支持序列化,能够通过序列化传输,实现了Cloneable接口,能被克隆。

LinkedList源码剖析

LinkedList的源码如下(加入了比较详细的注释):

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

几点总结

关于LinkedList的源码,给出几点比较重要的总结:

1、从源码中很明显可以看出,LinkedList的实现是基于双向循环链表的,且头结点中不存放数据,如下图;

2、注意两个不同的构造方法。无参构造方法直接建立一个仅包含head节点的空链表,包含Collection的构造方法,先调用无参构造方法建立一个空链表,而后将Collection中的数据加入到链表的尾部后面。

3、在查找和删除某元素时,源码中都划分为该元素为null和不为null两种情况来处理,LinkedList中允许元素为null。

4、LinkedList是基于链表实现的,因此不存在容量不足的问题,所以这里没有扩容的方法。

5、注意源码中的Entry<E> entry(int index)方法。该方法返回双向链表中指定位置处的节点,而链表中是没有下标索引的,要指定位置出的元素,就要遍历该链表,从源码的实现中,我们看到这里有一个加速动作。源码中先将index与长度size的一半比较,如果index<size/2,就只从位置0往后遍历到位置index处,而如果index>size/2,就只从位置size往前遍历到位置index处。这样可以减少一部分不必要的遍历,从而提高一定的效率(实际上效率还是很低)。

6、注意链表类对应的数据结构Entry。如下;

  1. // 双向链表的节点所对应的数据结构。  
  2. // 包含3部分:上一节点,下一节点,当前节点值。  
  3. private static class Entry<E> {
  4.     // 当前节点所包含的值  
  5.     E element;
  6.     // 下一个节点  
  7.     Entry<E> next;
  8.     // 上一个节点  
  9.     Entry<E> previous;
  10.     /**  
  11.      * 链表节点的构造函数。  
  12.      * 参数说明:  
  13.      *   element  —— 节点所包含的数据  
  14.      *   next      —— 下一个节点  
  15.      *   previous —— 上一个节点  
  16.      */
  17.     Entry(E element, Entry<E> next, Entry<E> previous) {
  18.         this.element = element;
  19.         this.next = next;
  20.         this.previous = previous;
  21.     }
  22. }

7、LinkedList是基于链表实现的,因此插入删除效率高,查找效率低(虽然有一个加速动作)。
8、要注意源码中还实现了栈和队列的操作方法,因此也可以作为栈、队列和双端队列来使用。

发表评论

电子邮件地址不会被公开。 必填项已用*标注