从源码阅读认识LinkedList

我们从《从源码阅读认识ArrayList》中知道了ArrayList的底层实现以及它的特性（动态扩容），今天要来认识另一个List——ArrayList

LinkedList

    transient int size = 0;

    transient Node<E> first;

    transient Node<E> last;

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

LinkedList的内部定义了一个内部类Node，我们称之为节点。
first指列表的第一个节点
last指列表的最后一个节点
size即列表的长度

LinkedList节点模型

如图所示，LinkedList内部就是一个链表，每个节点都有前置节点和后置节点。

add()

//源码
    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++;
    }

add方法，新增一个节点，然后指针后移，比较简单就不详细讲。

ArrayList和LinkedList的插入：
ArrayList如果要在列表中的某个位置插入对象，需要将这个位置往
后的所有对象都往后挪一位，然后再将待加入对象放置入对应位置
LinkedList的插入只需要在待插入位置的前一个节点的后置节点指向
待插入节点，然后将插入位置的后一个节点的前置节点指向待插入
节点，最后设置待插入节点的前置和后置节点。

LinkedList的插入

get()

//源码
    public E get(int index) {
        checkElementIndex(index); //检查是否越界
        return node(index).item;
    }

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

        if (index < (size >> 1)) {
            Node<E> x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {
            Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }

LinkedList的get()方法是通过便利整个链表（只暴露了first和last两个节点当然要遍历了）。不过为了让性能更优，会判断从first还是从last节点开始遍历。

LinkedList的其他方法就不多介绍了，毕竟知道底层如何实现，许多方法也是可以推测出来，对源码有兴趣的可以自行去查看哦~