内存无需连续的空间保证;
元素查找只能是顺序的遍历超查找;
针对增删操作具有更好的性能;

继承关系类图:

mark

成员属性:

    //存储的元素数量
    transient int size = 0;

    /**
     * Pointer to first node.
     * 头节点 Node
     */
    transient Node<E> first;

    /**
     * Pointer to last node.
     * 尾节点 Node
     */
    transient Node<E> last;

    /**
     * Constructs an empty list.
     * 无参构造器
     */
    public LinkedList() {
    }

    /**
     * 传入集合的有参构造器
     */
    public LinkedList(Collection<? extends E> c) {
        this();
        addAll(c);
    }

    //Node为LinkedList的内部类
    private static class Node<E> {
        //当前Node存储的元素
        E item;
        //当前Node的下一个节点
        Node<E> next;
        //当前Node的上一个节点
        Node<E> prev;
        //构造器
        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }

get 操作

    public E get(int index) {
        //1.检查index是否越界
        checkElementIndex(index);
        //2.node(index).item遍历查找值
        //4.返回查找到的元素
        return node(index).item;
    }

    //1.1
    private void checkElementIndex(int index) {
        //如果越界抛出IndexOutOfBoundsException异常
        if (!isElementIndex(index))
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }
    //1.2 检查idex是否为size 或大于size 是否越界
    private boolean isElementIndex(int index) {
        return index >= 0 && index < size;
    }

    //3.根据index 进行二分查找
    Node<E> node(int index) {

        if (index < (size >> 1)) {
            //如果index小于 size的一半 则从头部开始遍历查找
            Node<E> x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {
            //如果index大于 size的一半 则从尾部开始向前遍历查找
            Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }

    //查找第一个元素 直接first.item
    public E getFirst() {
        final Node<E> f = first;
        if (f == null)
            throw new NoSuchElementException();
        return f.item;
    }

    //查找最后一个元素 直接last.item
    public E getLast() {
        final Node<E> l = last;
        if (l == null)
            throw new NoSuchElementException();
        return l.item;
    }

add 添加操作:

    //add(E e)流程
    public boolean add(E e) {
        //1.添加新的元素
        linkLast(e);
        //2.返回成功
        return true;
    }

    void linkLast(E e) {
        //1.1 声明l 用于保存last节点
        final Node<E> l = last;
        //1.2 new Node<>(l, e, null) 生成新的node节点
        final Node<E> newNode = new Node<>(l, e, null);
        //新的节点赋值给last
        last = newNode;
        if (l == null)
            //如果l为null 说明还没有存储数据没有头节点
            //将新节点赋值给头节点first
            first = newNode;
        else
            //如果l不为null,则说明存在数据,则设置l的next指向newNode 完成尾部添加的操作.
            l.next = newNode;
        //增加存储元素的数量
        size++;
        //更新modCount
        modCount++;
    }

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

    //add(int index, E element)方式
    public void add(int index, E element) {
        //检查下标是否越界 越界则抛出异常
        checkPositionIndex(index);
        //如果idex等于size则直接在尾部添加
        if (index == size)
            linkLast(element);
        else
            //在对应节点位置添加 关联上一个节点和下一个节点
            linkBefore(element, node(index));
    }

    void linkBefore(E e, Node<E> succ) {
        //要在其后面保存新元素的节点
        final Node<E> pred = succ.prev;
        //声明一个新的Node节点 存储新元素 并指定pred(上一个节点)为index位置节点的pred next为index位         //置的节点
        final Node<E> newNode = new Node<>(pred, e, succ);
        //指定已存在元素的的上一个节点为新加入的元素节点 形成关联
        succ.prev = newNode;
        if (pred == null)
            //如果已存在元素的前一个节点为null,说明这个元素为第一个, 则设置Libkedlist的first的节点为             //新添加的元素的节点
            first = newNode;
        else
            //如果不为null 则将index位置元素的下一个节点指向保存新元素的节点
            pred.next = newNode;
        //更新存储元素数量
        size++;
        //更新 modCount
        modCount++;
    }

remove 操作:

    public E remove(int index) {
        //检测下标是否越界 越界抛出异常
        checkElementIndex(index);
        //进行删除 前后重新关联操作
        return unlink(node(index));
    }

    E unlink(Node<E> x) {
        // assert x != null;
        //声明 element 保存要删除的元素
        final E element = x.item;
        //要删除元素节点的next 下一个节点
        final Node<E> next = x.next;
        //要删除元素节点的prev 上一个节点
        final Node<E> prev = x.prev;

        if (prev == null) {
            //如果要删除元素的上一个节点为null 曾说明为第一个? 则将要删除元素的的next 下一个节点设置为             //整个集合的第一个元素
            first = next;
        } else {
            //不是第一个元素 则将要删除元素的上一个节点得nnext指向他的下一个节点
            prev.next = next;
            //清空要删除元素的prev
            x.prev = null;
        }

        if (next == null) {
            //如果要删除元素的next(下一个节点)为null 则说明是最后一个元素 曾吧他的上一个元素设置为整个            //集合的最后一个节点
            last = prev;
        } else {
            //如果要删除的元素不是最后一个节点,则把他的下一个节点的prev(上一个节点)设置为他的上一个节点
            next.prev = prev;
            //清空要删除元素的next
            x.next = null;
        }
        //设置要删除节点存储的元素为null
        x.item = null;
        //减少存储的元素数量
        size--;
        //更新modCount
        modCount++;
        //返回要删除节点所保存的元素
        return element;
    }