LinkedList源码按摩，啊舒服

​首先看一下LinkedList的声明

public class LinkedList<E>    extends AbstractSequentialList<E>    implements List<E>, Deque<E>, Cloneable, java.io.Serializable{
   }

AbstractSequentialList 分析

官方文档的解释如下

  This class provides a skeletal implementation of the <tt>List</tt>  interface to minimize the effort required to implement this interface  backed by a "sequential access" data store (such as a linked list).  For  random access data (such as an array), <tt>AbstractList</tt> should be used  in preference to this class.<p>

意思大概就是对于随机访问的数据或者数组，应优先使用AbstractSequentialList，即

E get(int index) E set(int index, E element)void add(int index, E element)E remove(int index)boolean addAll(int index, Collection<? extends E> c)

上面的这几个接口都是随机访问的

 

实现List<E>可以有list的特性

实现Deque,可以使用双端队列访问元素的方法，是一个双向链表

实现Cloneable，可以实现克隆对象的全部元素

实现java.io.Serializable，可以实现序列化

 

常量

 

// 元素个数transient int size = 0;// 指向头指针transient Node<E> first;// 指向末尾指针transient Node<E> last;

 

构造方法

    // 无参构造方法，生成空的链表    public LinkedList() {
       }    // 构建一个包含指定元素集合的列表，顺序有Collection的iterator返回    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;        }    }

 

头节点插入

   /**    * 头节点插入元素e    * 先拿到当前头结点定义为f，定一个新的节点newNode，pre指向null，元素为e，next指向f    * 在修改新的头节点为newNode    * 判断拿到的头节点f是否为空，如果为空last为newNode，此时链表就一个元素newNode    * 如果不为空，f的pre节点指向newNode新创建的节点    * size ++     * modCount 涉及修改数据结构都要修改的值，即修改统计数，用来实现fail-fast机制    */        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++;    }

末尾节点添加元素

    /**    * 末尾节点添加元素e    * 获取当前尾部节点last为l    * 定义新节点newNode，pre为l，元素为e，next为null    * 定义现在last尾部节点为newNode    * 如果刚才首次获取尾部节点l为null，头部节点改为newNode，此时链表就y一个元素    * 如果不为null，l的next节点就为我们的newNode    * 元素个数添加    * 修改次数添加，和上面类似    */    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++;    }

在非null元素succ之前插入元素

    /**    * 在非null元素succ之前插入元素e    * 拿到succ的pre节点pred    * 创建newNode节点保存我们要插入的数据，pre为刚才取得pred节点，元素为e，next为succ    * 修改succ的pre节点为创建的newNode节点    * 判断如果pred拿出的为null，即pred就是头节点，first为newNode    * 不为null，pred的next节点为新创建的newNode    * 修改元素个数size    * 修改次数添加    */    void linkBefore(E e, Node<E> succ) {
           // assert succ != null;        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++;    }

取消链接非空的第一个节点

  /**  * 取消第一个节点f的链接  * 取出f节点元素element  * 取出f的后置节点next  * 然后把f的元素值置为null，next置为null，置为nullgc更快回收  * 链表的头节点定义为刚才取出的后置节点next  * 判断next节点是否为空，如果为null，last也为null，链表为k空  * 不为null next的前置节点置为null  * 元素个数减少1  * 修改次数添加  */  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;    }

取消链接的最后一个节点

   /**   * 取消链接的最后一个非k空节点l   * 取出l节点的元素element   * 取出l节点的前置节点prev   * l元素置为null，pre前置节点置为null   * 链表的last置为f节点的pre节点prev   * 判断如果pre节点为null，链表first头节点为null   * 不为null，prev的后置节点置为null断开元素的链接   * 元素个数减少1   * 修改次数添加   */   private E unlinkLast(Node<E> l) {
           // assert l == last && l != null;        final E element = l.item;        final Node<E> prev = l.prev;        l.item = null;        l.prev = null; // help GC        last = prev;        if (prev == null)            first = null;        else            prev.next = null;        size--;        modCount++;        return element;    }

取消链接非空节点

   /**   * 取消链接非空节点x   * 分别取到x节点的元素值element，前置节点prev，后置节点next   * 如果元素x的前置节点为null，链表的first 指向next节点，如果不为null，prev节点的next执行元素x的next节点   * 如果元素x的后置节点为null，链表的last节点为x的prev前置节点，不为null，元素x后置节点的pre指向x的前置节点   * x元素值置为null   * 元素减少1   * 修改次数添加   */   E unlink(Node<E> x) {
           // assert x != null;        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;        }​        x.item = null;        size--;        modCount++;        return element;    }

 

获取链表的第一个元素

    /**    * 拿到first指向的元素    * 判断是否为null，为null抛出NoSuchElementException()list为空异常    * 不为null，返回f.item的元素本身    */    public E getFirst() {
           final Node<E> f = first;        if (f == null)            throw new NoSuchElementException();        return f.item;    }

获取链表的最后一个元素

    /**    * 根据last拿到链表的最后一个元素值    * 判断last是否为null，如果为null，返回list为空的异常    * 不为null，返回l.item元素本身    */    public E getLast() {
           final Node<E> l = last;        if (l == null)            throw new NoSuchElementException();        return l.item;    }

删除链表中第一个元素并返回

    /**    * 拿到first第一个元素    * 如果为null，抛出list为empty的异常    * 不为null调用unlinkFirst(f)方法来取消元素的链接    */    public E removeFirst() {
           final Node<E> f = first;        if (f == null)            throw new NoSuchElementException();        return unlinkFirst(f);    }

删除链表中最后一个元素并返回

    /**    * 根据last获取链表的最后一个元素    * 如果为null，抛出list为empty的异常    * 不为null调用unlinkLast(l)方法，取消最后一个元素的链接    */    public E removeLast() {
           final Node<E> l = last;        if (l == null)            throw new NoSuchElementException();        return unlinkLast(l);    }

指定元素添加到链表头部

    /**    * 直接调用linkFirst(e)方法添加    */    public void addFirst(E e) {
           linkFirst(e);    }

指定元素添加到链表尾部

    /**    * 调用linkLast(e)方法尾部添加元素e    */    public void addLast(E e) {
           linkLast(e);    }​

判断链表中是否包含元素

    /**    * 判断链表是否包含元素o    * 调用indexOf(o)方法，indexOf方法见下面解析，返回元素的索引，找不到或者索引不存在返回-1    */    public boolean contains(Object o) {
           return indexOf(o) != -1;    }

indexOf(Object o)

    /**    * 返回元素o在此链表中 【首次】出现的位置    * 如果list不包含元素o，返回-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;    }

获取list元素个数

    public int size() {
           return size;    }

添加一个元素

    /**    * 添加一个元素e    * 调用linkLast(e)在队列的尾部添加元素    * 返回true    */    public boolean add(E e) {
           linkLast(e);        return true;    }

删除一个元素

   /**   * 如果元素o存在的话，移除首次出现的元素，即最小索引的元素，   * 如果元素o为null，移除首次出现的null元素   * 如果元素o不在list中，不做任何改变   * 如果元素o匹配上，调用unlink(o)方法来删除元素   */   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;    }

addAll 方法添加指定的集合元素

    public boolean addAll(Collection<? extends E> c) {
           // 从什么位置开始添加，此处从原list的末尾开始添加元素集合c        return addAll(size, c);    }    /**    * index： 开始添加元素的位置    * c： 要添加的元素集合     */    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;}​

清空list，删除所有的元素

    public void clear() {
           // Clearing all of the links between nodes is "unnecessary", but:        // - helps a generational GC if the discarded nodes inhabit        //   more than one generation        // - is sure to free memory even if there is a reachable Iterator        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++;    }

get(index)

    /**    * 返回指定位置的元素    * 检测index索引是否有效    * 返回index索引位置元素    */    public E get(int index) {
           checkElementIndex(index);        return node(index).item;    }

指定位置覆盖原先位置元素

    /**    * 检验index是否有效    * 获取index位置节点    * 替换node节点item    */    public E set(int index, E element) {
           checkElementIndex(index);        Node<E> x = node(index);        E oldVal = x.item;        x.item = element;        return oldVal;    }

指定位置后面添加元素（原索引位置元素以及之后的元素右移，索引位置放置新元素）

    /**    * 校验index索引是否有效    * 判断如果index等于list数组元素数量，就调用linkLast(element) 尾部添加元素    * 不等于就调用linkBefore(elemetn,node(index))在元素之前插入    */    public void add(int index, E element) {
           checkPositionIndex(index);​        if (index == size)            linkLast(element);        else            linkBefore(element, node(index));    }

移除元素

    /**    * 校验index索引是否有效    * 调用unlink(node)方法取消链接    */    public E remove(int index) {
           checkElementIndex(index);        return unlink(node(index);    }

 

好了，LinkedList源码按摩就到此结束了，如有错误欢迎指出，共同进步，以便下次提供更好的按摩服务