Java之LinkedList源码解析

下文笔者讲述Linkedlist源码解析,如下所示

LinkedList类图

从LinkedList的类图中
   我们可以看出LinkedList实现Iterable、Queue
     、Collection、List接口

LinkedList自身还有一大特点：
  就是底层数据采用链接进行存储,而且是一个双向列表

Node类

private static class Node<E> {
    //主要用于在当前Node节点上的存储的数据对象
    E item;
    //类型也是Node，表示当前节点指向的下一个节点
    Node<E> next;
    //类型也是Node，表示当前节点指向的上一个节点
    Node<E> prev;

    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

LinkedList双向链表--记录first属性和last属性
size属性用于记录双向链表的当前长度

 
public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
    //记录当前双向链表的长度
    transient int size = 0;

    /**
     * Pointer to first node.
     * Invariant: (first == null && last == null) ||
     *            (first.prev == null && first.item != null)
     */
    
    //记录当前双向链表的头节点
    transient Node<E> first;

    /**
     * Pointer to last node.
     * Invariant: (first == null && last == null) ||
     *            (last.next == null && last.item != null)
     */
    
    //记录当前双向链表的尾节点
    transient Node<E> last;

    /**
     * Constructs an empty list.
     */
    public LinkedList() {
    }

first == null && last == null:
    当双向链表没有任何数据对象的时候
      first属性和last属性都为null

first == last:
    当双向链表只有一个对象的时候
       first属性和last属性一定指向同一个节点

first != null && last != null:
    当双向链表至少有一个数据对象的时候
       first属性和last属性都不可能为null

LinkedList集合内部场景是不可能出现
   (first != null && last == null)或
   (first == null && last != null)
   因为first属性和last属性要么都为null，要么都不为null

JDK8中，开始对外提供三个添加节点的方法
linkFirst(E)方法，linkLast(E)方法和linkBefore(E,Node)

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++;
}


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++;
}

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++;
}

//但是对外只提供
//add(E)、addLast(E)、addFirst(E)方法

例:对外提供三个方法的源码

 
public boolean add(E e) {
    linkLast(e);
    return true;
}
 
public void addLast(E e) {
    linkLast(e);
}
 
public void addFirst(E e) {
    linkFirst(e);
}
 

linkFirst源码

/**
 * Links e as first element.
 */
private void linkFirst(E e) {
    //使用一个临时的变量记录操作前first属性的信息
    final Node<E> f = first;
    //创建一个数据信息为e的新节点，该节点前置节点引用为null，后置节点引用指向原先的头节点
    final Node<E> newNode = new Node<>(null, e, f);
    //因为要在双向链表头部添加新的节点，将first属性中的信息重新设置
    first = newNode;
    //条件成立，说明双向链表没有任何节点
    if (f == null)
        //将last节点也指向新的节点，这样first和last节点属性同时指向同一个节点
        last = newNode;
    else
        //不成立，说明双向链表至少有一个节点，只需要把原来的头节点的前置节点引用指向新的头节点
        f.prev = newNode;
    //双向链表长度 + 1
    size++;
    //linkedList集合的操作次数 + 1
    modCount++;
}

linkLast(E)方法的功能:
可以在当前双向链表的尾节点之后添加一个新的节点，并且调整last属性的指向位置

void linkLast(E e) {
    //使用一个临时变量来记录操作前的last属性信息
    final Node<E> l = last;
    //创建一个新的节点，item属性值为e，新节点的前置对象指向原来的尾节点，后置节点为null
    final Node<E> newNode = new Node<>(l, e, null);
    //因为要在双向链表的尾节点添加新的节点，将last属性中的信息重新设置
    last = newNode;
    //条件成立，说明双向链表没有任何节点
    if (l == null)
        //将first节点指向新的节点，first和last都同时指向同一个节点
        first = newNode;
    else
        //不成立，双向链表至少有一个节点，将原来的尾节点的后置节点指向新的尾节点
        l.next = newNode;
    //双向链表长度 + 1 
    size++;
    //linkedList集合的操作次数 + 1
    modCount++;
}

linkBefore(E,Node)方法的功能:

在指定的节点前的索引位置上插入一个新的节点

  注意事项:
     LinkedList集合的操作逻辑可以保证这里的succ入参一定不为null
     并且一定已经存储于当前LinkedList集合中的某个位置

linkBefore源码

void linkBefore(E e, Node<E> succ) {
    // assert succ != null;
    //创建一个变量，记录当前succ的前置节点引用(可能为null)
    final Node<E> pred = succ.prev;
    //创建一个新的节点，该节点的前置节点引用指向succ节点的前置节点，该节点的后置节点引用指向succ节点
    final Node<E> newNode = new Node<>(pred, e, succ);
    //将succ节点的前置节点重新设置为刚刚创建的新的节点
    succ.prev = newNode;
    //条件成立，说明当前succ节点原本就是双向链表的头节点，可以看作当前的操作其实就是在链表的头部添加一个新的节点
    if (pred == null)
        //这个时候将first属性的指向新创建的节点
        first = newNode;
    else
        //不成立，将succ的前置节点的后置节点设置为当前新创建的节点
        pred.next = newNode;
    //双向链表长度 + 1
    size++;
    //linkedList集合的操作次数 + 1
    modCount++;
}

LinkedList集合中元素移除方法

unlinkFirst(Node)方法
unlinkLast(Node)方法
unlink(Node)方法
====================================================
LinkedList集合对外提供
     removeFirst()、removeLast()、remove(Object)

remove方法源码

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

removeFirst源码

public E removeFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return unlinkFirst(f);
}

removeLast源码

public E removeLast() {
    final Node<E> l = last;
    if (l == null)
        throw new NoSuchElementException();
    return unlinkLast(l);
}

unlinkFirst(Node)方法功能

unlinkFirst(Node)方法的功能:
   用于移除LinkedList集合中双向链表的头节点
   并重新设置它的后置节点为新的头节点
     该方法入参f就是当前双向链表的头节点
      该参数一定不为null

unlinkFirst源码

private E unlinkFirst(Node<E> f) {
    // assert f == first && f != null;
    //定义一个element变量，记录当前双向链表头节点的数据对象，以便方法最后将其返回
    final E element = f.item;
    //创建一个next变量，记录当前双向链表头节点的后置节点引用，可能为null
    final Node<E> next = f.next;
    //设置当前双向链表头节点的数据对象为null，后置节点引用设置为null
    f.item = null;
    f.next = null; // help GC  (帮助进行GC（java的垃圾回收机制）)
    //设置双向链表新的头节点为当前头节点的后置节点
    first = next;
    //条件处理，说明完成头节点的移除操作，当前双向链表已经没有任何节点
    if (next == null)
        //将last属性设置为null
        last = null;
    else
        //不成立，设置新的头节点前置节点设置为null，因为新的头节点的前置节点指向是原先的头节点
        next.prev = null;
    //双向链表长度 - 1
    size--;
    //LinkedList集合操作次数 + 1 
    modCount++;
    return element;
}

unlinkLast(Node)方法的功能

unlinkLast(Node)方法的功能:
    可移除LinkedList集合中双向链表的尾节点
     且重新设置它的前置节点为新的尾节点
     该方法入参l就是当前双向链表的尾节点
       该参数不能为null

unlinkLast源码

private E unlinkLast(Node<E> l) {
    // assert l == last && l != null;
    //定义一个element变量记录当前双向链表尾节点中的数据对象，以便在最后将其返回
    final E element = l.item;
    //创建一个prev变量，记录当前双向链表尾节点中的前置节点，该变量可能为null
    final Node<E> prev = l.prev;
    //设置当前双向链表尾节点中的数据为null，前置对象引用为null
    l.item = null;
    l.prev = null; // help GC  帮助进行GC（垃圾回收）
    //设置双向链表新的尾节点为当前尾节点的前置节点
    last = prev;
    //条件处理，说明移除完尾节点之后双向链表已经没有任何节点了
    if (prev == null)
        //设置头节点为null
        first = null;
    else
        //不成立，设置新的尾节点后置节点设置为null，因为新的尾节点的后置节点指向是原先的尾节点
        prev.next = null;
    //双向链表长度 - 1
    size--;
    //LinkedList集合操作次数 + 1
    modCount++;
    return element;
}

unlink(Node)方法功能

unlink(Node)方法的功能:
   从双向链表中移除指定的节点
    其入参x所指向的节点一定位于双向链表中

unlink(Node)方法源码

E unlink(Node<E> x) {
    // assert x != null;
    //定义一个element变量，记录当前节点中的数据对象，以便方法最后返回
    final E element = x.item;
    //创建一个next节点，记录当前节点中的后置节点引用，可能为null
    final Node<E> next = x.next;
    //创建一个prev节点，记录当前节点中的前置节点引用，可能为null
    final Node<E> prev = x.prev;

    //如果条件成立，说明被移除的x节点是双向链表的头节点
    if (prev == null) {
        //将x的后置节点设置为新的头节点
        first = next;
    } else {
        //将x的前置节点中的后置节点设置为移除的x节点的后置节点
        prev.next = next;
        //将移除的x节点的前置节点设置为null
        x.prev = null;
    }

    //如果条件成立，说明被移除的x节点是双向链表的尾节点
    if (next == null) {
        //将移除的x的节点的前置节点设置为新的尾节点
        last = prev;
    } else {
        //将x的后置节点中的前置节点设置为移除x节点的前置节点
        next.prev = prev;
        //将移除的x节点的后置节点设置为null
        x.next = null;
    }

    //将移除的x节点中的数据对象设置为null
    x.item = null;
    //双向链表长度 - 1
    size--;
    //LinkedList集合操作次数 + 1
    modCount++;
    return element;
}

LinkedList获取数据的方法

由于LinkedList中采用链表的结构存储数据
   所以我们获取数据时，不能使用索引的方式获取数据
但是LinkedList对外提供一个node(int)方法

但是此方法的底层逻辑：
   是采用遍历LinkedList检索数据，所以其查询效率相对于ArrayList低效
 

node源码

 Node<E> node(int index) {
    // assert isElementIndex(index);

    //如果条件成立，说明当前指定的index号索引位在当前双向链表的前半段
    if (index < (size >> 1)) {
        //从当前双向链表的头节点开始向后依次查询
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        //不成立，说明当前指定的index号索引位在双向链表的后半段，从当前双向链表的尾节点开始向后依次查询
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

indexOf(object)

此方法的核心原理:
    也是采用遍历的方法依次查找LinkedList中的元素
	当匹配到符合条件的元素时,则返回index位置
	当匹配失败时，则返回-1

indexOf源码

 
public int indexOf(Object o) {
    int index = 0;
    //如果入参o为null
    if (o == null) {
        //从头节点开始向后遍历，直到找到某个item属性值为null的节点
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null)
                return index;
            index++;
        }
    } else {
        //不为null，从头节点开始向后遍历，直到找到某个item属性值向的内存地址和传入参数o指向的内存地址相同的节点
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item))
                return index;
            index++;
        }
    }
    return -1;
}