LinkedList

几句话证明你看过LinkedList的源码
LinkedList同时实现了List接口和Deque接口，可以当做一个链表容器，也当做一个队列(Queue)，还可以当做一个栈(Stack)。
推荐栈和队列（即对两端进行操作）使用AarryDeque，根据索引位置增删使用LinkedList
链表（查询慢，增删快，线程不安全，允许元素重复和null，增删都是在中间效率会较低（源码遍历有从前或从后遍历，所以最慢的遍历是中间）)

关于循环删除元素，普通for循环，不会报错，会导致下标紊乱，产生数据错误或数组越界
增强for循环，由于删除修改了modCount，导致fail-fast，所以会报错ConcurrentModificationException
迭代器删除(iterator.remove()，而不是list.remove())，会更新modCount与expectedModCount，所以支持迭代删除。

1.双向链表

成员变量包含
first头节点 last尾节点 size长度
内部类

private static class Node<E> {
        //上一节点
        Node<E> prev;
        //下一节点
        Node<E> next;
        //当前节点值
        E item;

        public Node(Node<E> prev, Node<E> next, E item) {
            this.prev = prev;
            this.next = next;
            this.item = item;
        }
    }

2.头尾节点修饰符为transient

transient关键字了解
简单概括：实现Serilizable接口，将不需要序列化的属性前添加关键字transient，序列化对象的时候，这个属性就不会序列化到指定的目的地中

3.获取node元素效率提升小细节

/**
     * 获取指定角标元素
     */
    Node<E> node(int index) {
        // assert isElementIndex(index);

        //根据角标与长度一半对比，选择从头遍历还是从尾遍历到指定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;
        }
    }

4.add方法
插入新节点，处理前驱后继，完成链接

/**
     * 插入元素-指定节点
     * @param index
     * @param element
     */
    public void add(int index, E element) {
        checkPositionIndex(index);

        if (index == size)
            linkLast(element);
        else
            linkBefore(element, node(index));
    }

    /**
     * 插入元素-默认尾节点
     * @param e
     * @return
     */
    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++;
    }

    /**
     * Inserts element e before non-null Node succ.
     */
    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++;
    }

5.remove方法

处理前驱后继，隔p链接

/**
     * 删除指定元素
     * @param o
     * @return
     */
    public boolean remove(Object o) {
        if (o == null) {
            for (Node<E> x = first; x != null; x = x.next) {
                if (x.item == null) {
                    unlink(x);
                    return true;
                }
            }
        } else {
            for (Node<E> x = first; x != null; x = x.next) {
                if (o.equals(x.item)) {
                    unlink(x);
                    return true;
                }
            }
        }
        return false;
    }

    /**
     * 删除指定角标元素
     * @param index
     * @return
     */
    public E remove(int index) {
        checkElementIndex(index);
        return unlink(node(index));
    }

    /**
     * Unlinks non-null node 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;

        //头节点
        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;
    }

6.fast-fail机制

linkedlist可正反双向迭代

/**
     * ListItrItr-ListIterator是Iterator(迭代器)的实现类
     */
    private class ListItr implements ListIterator<E> {
        //上一次返回的节点
        private Node<E> lastReturned;
        //下一个节点
        private Node<E> next;
        //下一个节点角标
        private int nextIndex;
        //期望的改变计数。用来实现fail-fast机制。
        private int expectedModCount = modCount;

        //从index位置开始进行迭代
        ListItr(int index) {
            // assert isPositionIndex(index);
            //半数以下 从前往后，半数以上 从前往后
            next = (index == size) ? null : node(index);
            nextIndex = index;
        }

        //是否存在下一个元素
        public boolean hasNext() {
            //通过元素角标是否等于“双向链表大小”判断
            return nextIndex < size;
        }

        //获取下一个元素
        public E next() {
            //期望的改变计数与modCount比较
            checkForComodification();
            if (!hasNext())
                throw new NoSuchElementException();

            lastReturned = next;
            next = next.next;
            nextIndex++;
            return lastReturned.item;
        }

        //是否存在上一个元素
        public boolean hasPrevious() {
            return nextIndex > 0;
        }

        //获取上一个元素
        public E previous() {
            //期望的改变计数与modCount比较
            checkForComodification();
            if (!hasPrevious())
                throw new NoSuchElementException();

            lastReturned = next = (next == null) ? last : next.prev;
            nextIndex--;
            return lastReturned.item;
        }

        public int nextIndex() {
            return nextIndex;
        }

        public int previousIndex() {
            return nextIndex - 1;
        }

        // 删除当前元素
        // 删除双向链表中的当前节点
        public void remove() {
            //期望的改变计数与modCount比较
            checkForComodification();
            if (lastReturned == null)
                throw new IllegalStateException();

            Node<E> lastNext = lastReturned.next;
            unlink(lastReturned);
            if (next == lastReturned)
                next = lastNext;
            else
                nextIndex--;
            lastReturned = null;
            expectedModCount++;
        }

        //设置当前节点为e
        public void set(E e) {
            if (lastReturned == null)
                throw new IllegalStateException();
            //期望的改变计数与modCount比较
            checkForComodification();
            lastReturned.item = e;
        }

        //将e添加到当前节点
        public void add(E e) {
            //期望的改变计数与modCount比较
            checkForComodification();
            lastReturned = null;
            if (next == null)
                linkLast(e);
            else
                linkBefore(e, next);
            nextIndex++;
            expectedModCount++;
        }

        // 判断 “modCount和expectedModCount是否相等”，依次来实现fail-fast机制。
        final void checkForComodification() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }
    }

7.队列，栈相关操作
https://www.cnblogs.com/skywang12345/p/3308807.html

8.自定义LinkedList练习

public class MyLinkedList<E> implements MyList<E> {

    Node<E> first;

    Node<E> last;

    private int size;

    @Override
    public int size() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public boolean contains(Object o) {
        return indexOf(o) == -1;
    }

    /**
     * 创建以最后节点为前驱的 新节点
     *
     * @param e
     * @return
     */
    @Override
    public boolean add(E e) {
        //“原尾节点”
        final Node<E> oldLast = last;

        //创建以尾节点为前驱的 “新尾节点”
        Node<E> newLast = new Node(last, null, e);

        //将“新尾节点”赋值给 “尾节点”
        last = newLast;

        //空链表
        if (oldLast == null) {
            //既是头节点也是尾节点
            first = newLast;
        } else {
            //将“原尾节点”的后置改为 “新尾节点”
            oldLast.next = newLast;
        }

        size++;
        return true;
    }

    @Override
    public boolean remove(Object o) {
        if (o == null) {
            for (Node<E> node = first; node != null; node = node.next) {
                if (node.item == null) {
                    unlink(node);
                    return true;
                }
            }
        } else {
            for (Node<E> node = first; node != null; node = node.next) {
                if (o.equals(node.item)) {
                    unlink(node);
                    return true;
                }
            }
        }

        return false;
    }

    private void unlink(Node<E> node) {
        //上一节点
        Node<E> prev = node.prev;
        //下一节点
        Node<E> next = node.next;

        //头节点
        if (prev == null) {
            first = next;
        } else {
            prev.next = next;
            //方便垃圾回收
            node.prev = null;

        }

        //尾节点
        if (next == null) {
            last = prev;
        } else {
            next.prev = prev;
            //方便垃圾回收
            node.next = null;
        }

        //方便垃圾回收
        node.item = null;
        size--;
    }

    @Override
    public E get(int index) {
        return node(index).item;
    }

    @Override
    public E set(int index, E element) {
        Node<E> node = node(index);
        E oldItem = node.item;
        node.item = element;
        return oldItem;
    }

    @Override
    public void add(int index, E e) {

        //获取节点
        Node<E> oldNode = node(index);
        //尾部插入节点
        if (index == size) {
            add(e);
            return;
        }

        final Node<E> prev = oldNode.prev;
        Node newNode = new Node(prev, oldNode, e);
        oldNode.prev = newNode;
        //头部插入节点
        if (prev == null) {
            first = newNode;
        } else {
            //中间插入节点
            prev.next = newNode;
        }

        size++;
    }

    private Node<E> node(int index) {
        //LinkedList思想
        //半数以下 从前往后
        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;
        }
    }

    @Override
    public E remove(int index) {
        final Node<E> delNode = node(index);

        final E item = delNode.item;
        unlink(delNode);

        return item;
    }

    @Override
    public int indexOf(Object o) {
        int index = 0;
        if (o == null) {
            for (Node<E> x = first; x != null; x = x.next) {
                if (x.item == null) {
                    return index;
                }
                index++;
            }
        } else {
            Node<E> x = first;
            while (x != null) {
                if (o.equals(x.item)) {
                    return index;
                }
                x = x.next;
                index++;
            }
        }

        return -1;
    }

    public static void main(String[] args) {

        MyList<String> list = new MyLinkedList<>();
        System.out.println(list.isEmpty());
        list.add("0");
        list.add("1");
        System.out.println(list);

        list.add(0, "new0");
        System.out.println(list);

        list.add(list.size(), "4");
        System.out.println(list.size());

        System.out.println(list.get(2));

        System.out.println(list.indexOf("new0"));

        list.set(0, "nn0");

        list.remove(0);
        System.out.println(list);

        list.remove(list.size() - 1);
        System.out.println(list);
    }

    private static class Node<E> {
        //上一节点
        Node<E> prev;
        //下一节点
        Node<E> next;
        //当前节点值
        E item;

        public Node(Node<E> prev, Node<E> next, E item) {
            this.prev = prev;
            this.next = next;
            this.item = item;
        }
    }
}

参考：
https://www.cnblogs.com/skywang12345/