01 原理

LinkedList底层采纳双向链表实现。与ArrayList不同，链表不须要扩容，除此之外还会有以下特点。

02 特点

  1. 非间断的内存，因而不反对随机拜访，只能通过节点持有的指针，顺次向后（向前）查找就安顿，查找的复杂度高。

2. 插入操作性能好。只须要插入地位的前后节点的援用指向该节点即可。

  3.  删除性能好，与插入相似，将删除节点前后节点的援用相互指向即可。

03 源码

最初从源码里具体分析一下，LinkedList中的增加(add)，查找（get），删除(remove)，插入（add）。

增加(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); // 创立e的节点，其中prev指针指向尾部节点，next为空        last = newNode; // 将尾节点批改为增加的节点        if (l == null)            first = newNode; // 没有尾节点，则该节点也是头节点        else            l.next = newNode; // 旧的尾节点 next指针指向新增加的节点        size++; // 数据大小 + 1        modCount++;    }

查找（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;        }    }

插入（add）：

public void add(int index, E element) {        checkPositionIndex(index);        if (index == size)            linkLast(element);  // 增加节点到链表开端，与增加逻辑统一        else            linkBefore(element, node(index)); // 查找下标指向的节点，插入新节点    }void linkBefore(E e, Node<E> succ) { // e:插入节点，succ:插入地位上的节点        // assert succ != null;        final Node<E> pred = succ.prev;        final Node<E> newNode = new Node<>(pred, e, succ); // 创立插入e的节点，其中prev指针指向succ的前继节                                                                                     //  点，next指向succ节点        succ.prev = newNode;        if (pred == null)            first = newNode;        else            pred.next = newNode; // succ前继节点的next指针指向插入的节点        size++;        modCount++;    }

删除(remove)：

public E remove(int index) {        checkElementIndex(index);        return unlink(node(index)); // 删除    }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; // 删除节点的前继节点        if (prev == null) { // 插入地位为头节点            first = next;        } else {            prev.next = next; // 前继节点的next指针指向后继节点            x.prev = null; // 删除节点的pre指针置为null        }        if (next == null) { // 插入地位为尾部            last = prev;        } else {            next.prev = prev; // 后继节点的prev指针指向前继节点            x.next = null; // 删除节点的next指针置为null        }        x.item = null; // 删除节点的指置为null,让GC能够回收        size--;        modCount++;        return element;    }