转载

Java集合框架分析(三)LinkedList分析

本篇文章主要分析一下 Java 集合框架中的 List 部分，LinkedList，该源码分析基于JDK1.8，分析工具，AndroidStudio，文章分析不足之处，还请指正！

LinkedList简介

类结构

首先，我们来看下 LinkedList 的类继承结构：

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
复制代码

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

数据结构

接下来我们来看看LinkedList的数据结构是什么样的。我们在分析 LinkedHashMap 的时候也会发现它的底层包含一个双向循环链表，而 LinkedList 也是的，LinkedList 底层的数据结构是基于双向循环链表的，且头结点中不存放数据,如下：

图上便是 LinkedList 的底层结构图，基于双向循环链表结构设计的。它的每一个节点都包含数据信息，上一个节点位置信息和下一个节点位置信息。

源码分析

接下来我们分析 LinkedList 的源码，首先来看下它内部申明的属性。

//链表节点的数量
transient int size = 0;
//头结点
transient Node<E> first;
//下一个节点
transient Node<E> last;
复制代码

变量申明比较简单，接着我们分析构造函数。如果有不大理解的，我们可以先分析后面的代码，就能知道这些属性的意思了。

构造函数

public LinkedList() {
   }
   
   public LinkedList(Collection<? extends E> c) {
       this();
       addAll(c);
   }
复制代码

构造函数也比较简单，没啥可说的，我们接着分析。一开始介绍的时候我们说明了底层是双向循环链表，所以肯定有节点信息，所以我们来看下它的节点数据结构。

节点信息

private static class Node<E> {
       E item;
       Node<E> next;
       Node<E> prev;
       Node(Node<E> prev, E element, Node<E> next) {
           this.item = element;
           this.next = next;
           this.prev = prev;
       }
   }
复制代码

节点数据结构，很简单，一个是数据信息 item，一个是前一个位置节点 prev，另一个是后一个位置节点 next，非常简单。接下来我们继续查看添加元素 add 方法

add(E e)

public boolean add(E e) {
       linkLast(e);
       return true;
   }
复制代码

添加数据 add 方法比较简单，add 函数用于向 LinkedList 中添加一个元素，并且添加到链表尾部。我们来看看 linkLast 方法怎么添加数据的。

//尾部添加数据e
   void linkLast(E e) {
    //保存尾部节点
       final Node<E> l = last;
       //新生成结点的前驱为l,后继为null
       final Node<E> newNode = new Node<>(l, e, null);
       // 重新赋值尾结点
       last = newNode;
       // 尾节点为空，赋值头结点
       if (l == null)
           first = newNode;
       else
        // 尾结点的后继为新生成的结点
           l.next = newNode;
       //节点数量增加1
       size++;
       modCount++;
   }
复制代码

上面这段代码是什么意思呢？我们来通过 demo 来简单说明一下。

List<String> mLinkedList = new LinkedList();
          mLinkedList.add("A");
          mLinkedList.add("B");
复制代码

首先我们先申明一个 LinkedList 类型的变量 mLinkedList，然后依次添加进两个数据 “A” 和 “B”，这个时候，它的内部结构是怎么操作的呢？

我们首先调用 LinkedList 的无参构造函数，进行初始化，这个时候里面的节点都是 null，因为没有数据，其次，我们通过 add 添加进一条数据 “A”，这个时候结合上面的源代码 add 方法，来解读一下，首先会调用 linkLast 方法，其次判断它的 last 节点是否为null，由于是刚初始化的，所以 last=null，这样就会调用 first = newNode;这个方法，也就是在开头节点处插入一条数据，其次再调用 add(“B”)，再次插入一条数据，我们循环上面那段代码，发现这个时候 last！=null 了，所以调用 last.next=newNode 代码，也就是在第一个节点的后面插入一条数据。

我们接着分析 add 其他的重载方法。

//在指定的位置上面插入一条数据
public void add(int index, E element) {
       checkPositionIndex(index);
       if (index == size)
           linkLast(element);
       else
           linkBefore(element, node(index));
   }
复制代码

这个方法也不是很复杂，我们依次分析，首先判断一下，需要插入的 index 是否越界。在插入之前我们需要先找到待插入位置的 node，通过 node(index) 方法获得，我们看下

//判断index是在链表的中部之前还是后面，如果在 1/2 前的话，从头开始遍历，如果在 1/2 后的话，从后往前遍历

Node<E> node(int index) {
	//从前往后遍历获取index出的node
       if (index < (size >> 1)) {
           Node<E> x = first;
           for (int i = 0; i < index; i++)
               x = x.next;
           return x;
       } else {
        //从后往前遍历获取index出的node
           Node<E> x = last;
           for (int i = size - 1; i > index; i--)
               x = x.prev;
           return x;
       }
   }
复制代码

上面很简单，为了提高搜索效率，先判断是在 1/2 处的前面还是后面，然后依次循环获得 index处的 node，我们接着分析

private void checkPositionIndex(int index) {
       if (!isPositionIndex(index))
           throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
   }
//不在[0，size]范围内越界
private boolean isPositionIndex(int index) {
       return index >= 0 && index <= size;
   }
复制代码

其次根据 index 判断是在链表中的哪个地方插入数据，是尾部还是在前面位置，如果是在尾部的话，我们已经分析过了，我们来看下在前面插入数据的情况。

void linkBefore(E e, Node<E> succ) {
       //保存目标index处的前置节点
       final Node<E> pred = succ.prev;
       final Node<E> newNode = new Node<>(pred, e, succ);
       succ.prev = newNode;
       //如果是在开头处插入的话
       if (pred == null)
           first = newNode;
       else
           pred.next = newNode;
       size++;
       modCount++;
}
复制代码

我们逐一分析，首先我们获取到了 index 处的节点 C，然后保存 C 的前置节点为 pred (也就是 B 节点)，然后我们用待插入的节点构建一个新的节点 (newNode)（新节点的前置节点是 pred，后继节点是 C），然后我们将 index 处的节点 C 的前置节点设置为待插入的节点，然后判断这个 index 处的 node 是否是第一个节点，不是的话就将原先 index 处的 node 的前置节点的后继节点设置为待插入的节点。这里面主要涉及到链表的插入操作，如果对于这不熟悉的话，可以先去复习一下链表的相关操作。

分析完了 add 方法，我们再来分析一下 addAll 方法。

public boolean addAll(Collection<? extends E> c) {
       return addAll(size, c);
   }
复制代码

很简单，在链表尾部插入一个集合，我们看一下 addAll 的重载方法，还是蛮长的，我们逐行看一下：

public boolean addAll(int index, Collection<? extends E> c) {
       //是否越界判断
       checkPositionIndex(index);
       Object[] a = c.toArray();
       int numNew = a.length;
       if (numNew == 0)
           return false;
	
	//保存前置和后继节点
       Node<E> pred, succ;
       //判断是在尾部插入还是在中间或者头部插入
       if (index == size) {
           succ = null;
           pred = last;
       } else {
           succ = node(index);
           pred = succ.prev;
       }
	
	
       for (Object o : a) {
           @SuppressWarnings("unchecked") E e = (E) o;
           Node<E> newNode = new Node<>(pred, e, null);
           if (pred == null)
               first = newNode;
           else
               pred.next = newNode;
		//将新添加进来的节点保存到结尾
           pred = newNode;
       }
	
	
       if (succ == null) {
           last = pred;
       } else {
        //中间保存后面的链表数据
           pred.next = succ;
           succ.prev = pred;
       }
       size += numNew;
       modCount++;
       return true;
   }
复制代码

以上便是 add 的方法内容，思想其实也简单的，类似单个插入，主要就是判断在链表尾部还是中间或者头部插入，然后再依次插入即可。

get(int index)

插入数据分析完之后，我们就开始分析获取数据 get。

public E get(int index) {
       checkElementIndex(index);
       return node(index).item;
   }
复制代码

get 方法也是只有简单的两行，我们依次分析，首先分析第一行，就是判断索引的位置是否越界，

private void checkPositionIndex(int index) {
       if (!isPositionIndex(index))
           throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
   }
private boolean isPositionIndex(int index) {
       return index >= 0 && index <= size;
   }
复制代码

很简单，看代码就知道了，不用分析了，接着分析第二行，第二行上面也已经分析过了，所以这里就不用再多叙述了。get 方法总体而言很简单。我们接着分析。

remove(int index)

我们接着来分析一下删除数据的代码。

public E remove(int index) {
       checkElementIndex(index);
       return unlink(node(index));
   }
复制代码

代码也很简单，首先是检查索引是否越界，其次我们分析第二行，我们发现 node(index) 的意思就是获取链表中指定位置上面的 node，所以我们看看 unlink 方法内容。

E unlink(Node<E> x) {
 
      final E element = x.item;
      final Node<E> next = x.next;
      final Node<E> prev = x.prev;
//没有前置节点，删除第一个节点
      if (prev == null) {
          first = next;
      } else {
       //要删除节点的前置节点的后继节点设置为要删除节点的后继节点
          prev.next = next;
          x.prev = null;
      }
//尾节点删除
      if (next == null) {
          last = prev;
      } else {
    //要删除节点的的后继节点设置为要删除节点的前置节点
          next.prev = prev;
          x.next = null;
      }
//gc
      x.item = null;
      size--;
      modCount++;
      return element;
  }
复制代码

上面主要是进行双向链表的删除操作。我们接着分析它的重载方法，

//删除指定元素，默认从first节点开始，删除第一次出现的那个元素
public boolean remove(Object o) {
       if (o == null) {
           for (Node<E> x = first; x != null; x = x.next) {
               if (x.item == null) {
                   unlink(x);
                   return true;
               }
           }
       } else {
           for (Node<E> x = first; x != null; x = x.next) {
               if (o.equals(x.item)) {
                   unlink(x);
                   return true;
               }
           }
       }
       return false;
   }
复制代码

相应代码已经分析过了，我们就不再说了。我们分析一下 set 方法

public E set(int index, E element) {
      checkElementIndex(index);
      Node<E> x = node(index);
      E oldVal = x.item;
      x.item = element;
      return oldVal;
  }
复制代码

首先是判断是否越界，然后获取需要替换的位置上面的 node，然后 update 一下，返回旧的数据。

我们来分析一下清空链表的方法 clear

clear

public void clear() {
       //遍历链表，依次设置为null
       for (Node<E> x = first; x != null; ) {
           Node<E> next = x.next;
           x.item = null;
           x.next = null;
           x.prev = null;
           x = next;
       }
       first = last = null;
       size = 0;
       modCount++;
   }
复制代码

基本上，LinkedList 的方法分析完了，还有一些简单的方法，我们一并列出来，做个简单的注释。

在首节点处添加一个数据

//在首节点处添加一个数据
   private void linkFirst(E e) {
       final Node<E> f = first;
       final Node<E> newNode = new Node<>(null, e, f);
       first = newNode;
       if (f == null)
           last = newNode;
       else
           f.prev = newNode;
       size++;
       modCount++;
   }
   
public void addFirst(E e) {
       linkFirst(e);
   }
复制代码

在尾节点插入一个节点

//在尾节点插入一个节点
void linkLast(E e) {
       final Node<E> l = last;
       final Node<E> newNode = new Node<>(l, e, null);
       last = newNode;
       if (l == null)
           first = newNode;
       else
           l.next = newNode;
       size++;
       modCount++;
   }
   
 public void addLast(E e) {
       linkLast(e);
   }
复制代码

移除第一个节点

//移除第一个节点
private E unlinkFirst(Node<E> f) {
       // assert f == first && f != null;
       final E element = f.item;
       final Node<E> next = f.next;
       f.item = null;
       f.next = null; // help GC
       first = next;
       if (next == null)
           last = null;
       else
           next.prev = null;
       size--;
       modCount++;
       return element;
   }
public E removeFirst() {
       final Node<E> f = first;
       if (f == null)
           throw new NoSuchElementException();
       return unlinkFirst(f);
   }
复制代码

移除并返回最后一个节点

移除并返回最后一个节点
public E removeLast() {
       final Node<E> l = last;
       if (l == null)
           throw new NoSuchElementException();
       return unlinkLast(l);
   }
复制代码

返回第一个节点

//返回第一个节点
 public E getFirst() {
       final Node<E> f = first;
       if (f == null)
           throw new NoSuchElementException();
       return f.item;
   }
复制代码

返回最后一个节点

//返回最后一个节点
   public E getLast() {
       final Node<E> l = last;
       if (l == null)
           throw new NoSuchElementException();
       return l.item;
   }
复制代码

是否包含某个节点信息

//是否包含某个节点信息
public boolean contains(Object o) {
       return indexOf(o) != -1;
   }
复制代码

遍历链表，存在则返回索引不存在则返回-1

//遍历链表，存在则返回索引不存在则返回-1
public int indexOf(Object o) {
       int index = 0;
       if (o == null) {
           for (Node<E> x = first; x != null; x = x.next) {
               if (x.item == null)
                   return index;
               index++;
           }
       } else {
           for (Node<E> x = first; x != null; x = x.next) {
               if (o.equals(x.item))
                   return index;
               index++;
           }
       }
       return -1;
   }
复制代码

从后往前遍历，第一次出现则返回索引，不存在返回-1

//从后往前遍历，第一次出现则返回索引，不存在返回-1
public int lastIndexOf(Object o) {
       int index = size;
       if (o == null) {
           for (Node<E> x = last; x != null; x = x.prev) {
               index--;
               if (x.item == null)
                   return index;
           }
       } else {
           for (Node<E> x = last; x != null; x = x.prev) {
               index--;
               if (o.equals(x.item))
                   return index;
           }
       }
       return -1;
   }
复制代码

返回链表第一个节点，但是不删除节点

//返回链表第一个节点，但是不删除节点
 public E peek() {
       final Node<E> f = first;
       return (f == null) ? null : f.item;
   }
复制代码

返回并删除第一个节点

//返回并删除第一个节点
public E poll() {
       final Node<E> f = first;
       return (f == null) ? null : unlinkFirst(f);
   }
复制代码

//省略迭代部分的源码......

以上便是 LinkedList 的基本源码，我们基本都给出了注释，相关重要的功能都加以图解，接下来我们来总结一下关于 LinkedList 相关重要知识。

总结

从源码中可以看出，LinkedList 的实现是基于双向循环链表的。却别与 ArrayList 的数组，以及 HashMap 的线性表和散列表以及 LinkedHashMap 的线性表和散列表以及双向循环链表。我们在搜索链表中的数据时，都会进行判断是否为 null 的情况，所以 LinkedList 是允许元素为 null 的情况的。

LinkedList 是基于链表实现的，因此不存在容量不足的问题，所以这里没有扩容的方法。源码中还实现了栈和队列的操作方法，因此也可以作为栈、队列和双端队列来使用。 LinkedList 是一个继承于 AbstractSequentialList 的双向链表。它也可以被当作堆栈、队列或双端队列进行操作。实现 List 接口，能对它进行队列操作。实现 Deque 接口，即能将 LinkedList 当作双端队列使用。实现了 Cloneable 接口，即覆盖了函数 clone()，能克隆。实现 java.io.Serializable 接口，这意味着 LinkedList 支持序列化，能通过序列化去传输。同时LinkedList 是非同步的。