LinkedList 实现原理及源码解析(jdk8 底层⽤的是链表)

LinkList顾名思义，就是通过链表实现的集合，优点就是插入、删除速度快，但遍历速度不及ArrayList，本质原因还是数据结构的不同，至于ListList和ArrayList的优缺点网上很多，这里不再赘述。

前言

LinkList源码其实不难，主要关注三个重要的方法和Node内部类：

将新添加的元素e作为链表的最后一个元素并维护进去
linkLast(E e)
从链表中删除x节点的链接
unlink(Node<E> x)
根据传入的index值，返回对应的节点node
node(int index)
私有内部静态类Node
class Node

源码分析

    /**
     * 将新添加的元素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指向该节点
        {
            first = newNode;
        } else
            // 如果不是第一个添加进来的元素，则更新l的后置节点指向新添加的元素节点
        {
            l.next = newNode;
        }
        size++;
        modCount++;
    }

基本没什么特别的算法，就是链表操作而已

	/**
     * 从链表中删除x节点的链接
     */
    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;

        // x.prev为null,表示x节点为第一个元素
        if (prev == null) {
            // 更新first节点为x的后置节点
            first = next;
        } else {
            // 将x的前置节点于x的后置节点相连接
            prev.next = next;
            // 断开x的前置指针
            x.prev = null;
        }

        // x.next为null，说明x节点为最后一个元素
        if (next == null) {
            // 将最后一个节点更新为x的前置节点
            last = prev;
        } else {
            // 将x的后置节点与x的前置节点相连接
            next.prev = prev;
            // 断开x的后置指针
            x.next = null;
        }

        x.item = null;
        size--;
        modCount++;
        return element;
    }

删除一个节点会对前置节点、后置节点进行判断，然后将前后节点进行连接，要删除的节点进行置空即可
接下来看下node方法，相当于ArrayList中的get方法

    /**
     * Returns the (non-null) Node at the specified element index.
     *
     * 根据传入的index值，返回对应的节点node
     */
    Node<E> node(int index) {
        // assert isElementIndex(index);

        // 如果index小于总长度size的一半，则从头开始向后遍历寻找
        if (index < (size >> 1)) {
            // x等于首节点
            Node<E> x = first;
            for (int i = 0; i < index; i++) {
                // 从first节点开始查找，直到index下标node才返回node
                x = x.next;
            }
            return x;
        }

        // 从尾部开始向前遍历查找
        else {
            // x等于最后一个节点
            Node<E> x = last;
            // 向前查找，直到遍历到index下标的node后才返回
            for (int i = size - 1; i > index; i--) {
                // x的前一个节点
                x = x.prev;
            }
            return x;
        }
    }

这里会判断是属于链表的前半部分还是后半部分，如果是前半部分，则从头开始遍历直到遍历到index下标；如果是后半部分，则从后向前遍历，直到遍历到index下标
最后我们看下Node类的基本结构，也就是链表的元素结构

    /**
     * Node 元素结构
     * @param <E>
     */
    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;
        }
    }