Java中LinkedList详解和使用示例_动力节点Java学院整理

第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  

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

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

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

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 new NoSuchElementException();
   // 链表的表头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 new IndexOutOfBoundsException