如有转载请注明出处 https://www.jianshu.com/p/be54e00c5a22

绪论

LinkedList是线程不安全的，他底层数据结构是链表，链表的特点是增删比较快，查询比较慢。回顾一下之前通过ArrayList我们得出数组是查询快，增删慢。
由于数组是连续的一段空间，并且可以通过角标来获取数据，但是增删的时候需要对数组中的数据进行移动，这使得数组增删比较慢，但我们删除的时候数组中index之后的数据需要向左移动，像某一个位置插入数据的时候数组中index位置的数据需要往右移动。
那么链表是一段不连续的空间，他查询的时候需要从开头进行遍历到index位置。

增

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++;
    }
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) {
        // 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++;
    }

• 直接添加一个元素
  判断最后一个元素是否有值，如果没有值代表链表为空，把该元素添加在链表的头就可以了，如果有值则向链表的后面添加一个节点
• 在某一个位置添加一个元素

  1. 在链表的末尾添加
     如果在末尾加的话操作同上面
     2.在某一个index之前加
     先找到要添加位置的节点，并且拿到前面一个节点
     然后将要添加的节点放在原来在这个位置的节点之前
     如果拿到的前一个节点没有的话那就把添加的节点放在头部
     否则就就把拿到的前一个节点的next指向新添加的节点

     
     向某一个index位置添加节点.png

删

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;
            x.prev = null;
        }

        if (next == null) {
            last = prev;
        } else {
            next.prev = prev;
            x.next = null;
        }

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

• 获取到要删除的节点
• 判断要删除的节点前面有没有节点，有节点的话，把前面节点指向后一个节点，要删除节点的前面节点置为null，如果没有节点的话就把后一个节点当作链表的开头

• 判断要删除的节点后面有没有节点，有节点的话，后一个节点的pre指向要删节点的前一个节点，并且将要删节点的next置为null，如果没有节点的话就将末尾的节点设置为要删节点的前一个节点

  
  删除节点.png

查

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

get主要操作是在node方法中进行的。如果查找的index小于size/2，那么就从开头遍历到index。也就是这种情况会从头开始遍历
如果查找的index大于size/2，那么就从末尾开始遍历。节省了效率

总结

链表查询比较慢就是因为存储空间不是连续的，并每次都需要从头活着从尾部开始遍历
链表增加删除比较快，是由于只需要找到要增加或者删除的节点，修改他的next和pre的指向就好了。