LinkedList源码分析

前言

大学中学习数据结构的时候，线性表是最开始学的，之前的ArrayList是线性表，而ArrayList就是线性链表了。由于ArrayList的每次插入和移除可能会让很多数据的位置发生变化,频繁的扩容和System.arrayCopy也会带来性能上的开销。于是就有了LinkedList。它的继承树如下所示:

image.png

1. 实现了Deque代表它可以具备双端队列的特性
2. 实现List代表它是一种线性结构的
3. Serializable和Clinedable都是标记的接口，代表具备其接口所对应的克隆和序列化的功能。

LinkedList的一些特性

1. LinkedList 集合底层实现的数据结构为双向链表
2. LinkedList 集合中元素可以为null
3. LinkedList 允许存放重复的数据
4. LinkedList 是非线程安全的

LinkedList中的成员

 private static class Node<E> {
        E item;   //存放当前节点的元素
        Node<E> next; //下一个节点指向哪个  可以为Null
        Node<E> prev; //前一个节点指向哪个  可以为Null
        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }

正是因为每个节点都有上面三个属性，所以我们可以说LinkedList是双向链表，它的主要成员变量有三个

    //元素个数
     transient int size = 0;
    /**
     * 链表的头
     */
    transient Node<E> first;
    /**
     * 链表的尾
     */
    transient Node<E> last;

LinkedList中的构造方法

    /**
     * 相当于first=last=null
     */
     public LinkedList() {
    }
    /**
     * 传入一个单列集合构造链表
     */
     public LinkedList(Collection<? extends E> c) {
         //调用无参构造方法
        this();
        addAll(c);
    }
    public boolean addAll(Collection<? extends E> c) {
        return addAll(size, c);
    }
//将指定元素插入到指定索引节点
public boolean addAll(int index, Collection<? extends E> c) {
        //检查是否>=0或<=size
        checkPositionIndex(index);
        //转换成Object数组
        Object[] a = c.toArray();
        int numNew = a.length;
        if (numNew == 0) //如果传进来的为空了就不用继续了
            return false;
        //当前节点的上一个节点为pred,当前节点为succ
        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)  //如果前面的为null，此时链表为Null,新节点就是首节点
                first = newNode;
            else  //否则就添加到这个位置
                pred.next = newNode;
            pred = newNode; 
        }
        //如果当前元素为Null,则last就是当前位置的上一个节点
        if (succ == null) {
            last = pred;
        } else {
            //否则就正常添加->将pred的next索引指向当前节点，当前节点的上一个指向pred
            pred.next = succ;
            succ.prev = pred;
        }
        //更新链表长度并返回true
        size += numNew;
        modCount++;
        return true;
    }

第二个构造器总结起来就是下面的步骤:

1. 检查索引值合法性。小于0或者大于size都不行
2. 保存index位置的节点和Index-1位置的节点，这样就形成了一个关联
3. 将单列集合转化成数组，循环将数组中的元素封装为节点添加到链表中
4. 更新链表的长度

LinkedList的主要方法

    //传入的元素将作为首节点
    private void linkFirst(E e) {
        //f为之前的节点
        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++;
    }
//移除首节点
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;
    }
    //移除尾节点
   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;
    }
    //移除指定的节点
    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;
        //前驱节点null表示移除的是首节点
        if (prev == null) {
            first = next;
        } else {
        //否则就直接让前驱节点的next指向要移除的next
            prev.next = next;
            x.prev = null;//help GC
        }
        //如果要移除的下一个是null表示移除的是尾节点
        if (next == null) {
            //最后一个变成当前的前一个
            last = prev;
        } else {
            //否则就是移除中间的,断链和接链
            next.prev = prev;
            x.next = null; //help GC
        }

        x.item = null;
        size--;
        modCount++;
        return element;
    }
    
    //获取首节点 尾节点就不说了,很容易理解
    //移除首节点,调用的是刚刚的private方法
     public E removeFirst() {
        final Node<E> f = first;
        if (f == null)
            throw new NoSuchElementException();
        return unlinkFirst(f);
    }
    //移除尾节点,调用的是刚刚的private方法
    public E removeLast() {
        final Node<E> l = last;
        if (l == null)
            throw new NoSuchElementException();
        return unlinkLast(l);
    }
public E removeLast() {
        final Node<E> l = last;
        if (l == null)
            throw new NoSuchElementException();
        return unlinkLast(l);
    }
    //其余的方法都是实现了Deque的一些特性,具体可见Deque源码分析