【源码解析】Java8-LinkList

LinkedList源码分析

  1. 从创建开始说：

    1
    List linkList = new LinkedList();
    1
    2
    /** * Constructs an empty list. */
    public LinkedList() {}

    构建函数里面啥都没操作，然后看一下LinkedList的成员变量：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    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;
     }

    有Node类型的fist和last，first一直指向第一个Node的引用，last一直是最后一个Node的引用，size是这个list的大小，点开Node，看一下是什么东西

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    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即此节点值，还有一个指向前面和后面的Node，下面看一下add怎么操作的吧

  2. 新增一个元素

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    linkList.add("a");

    public boolean add(E e) {
        linkLast(e);
        return true;
    }

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

    可以看到调用的linkLast方法：

    1. 先把最后一个元素（即当前元素）赋值给l，此时l为当前元素的引用，为空说明为第一个元素
    2. new一个新的Node，l作为新增元素的pre，新值为新元素value，next为空
    3. last指向新的元素
    4. 如果是第一个元素，first指向新元素，若不是第一个元素则，用当前元素的next指向新的元素