java集合-链表LinkedList

1、简介

LinkedList 底层使用的是 双向链表的数据结构

2、类图（JDK 1.8）

下图是LinkedList实现的接口和继承的类关系图：

public class LinkedList
    extends AbstractSequentialList
    implements List, Deque, Cloneable, java.io.Serializable

1、实现了四个接口
1.1 java.util.List 接口，提供数组的添加、删除、修改、迭代遍历等操作。
1.2 java.io.Serializable 接口，表示 LinkedList 支持序列化的功能。
1.3 java.lang.Cloneable 接口，表示 LinkedList 支持克隆。
1.4 java.util.Deque接口，是一种双向线性集合，可以再两端对集合进行插入或者删除操作，所以既可以当队列(FIFO)，也可以当栈(LIFO)，Deque继承java.util.Queue。
2、继承了一个类
2.1 java.util.AbstractSequentialList抽象类，它继承了AbstractList抽象类,并且有
public abstract ListIterator listIterator(int index);抽象方法，返回一个由LinkedList实现的ListIterator迭代器，用来支持AbstractList抽象类的get(int index),set(int index, E element),add(int index, E element)remove(int index) 等一些支持随机访问的方法。

3、常用方法

添加元素 add(E e)

    //链表添加元素
    public boolean add(E e) {
        linkLast(e);//往链表尾部添加元素
        return true;
    }
    void linkLast(E e) {
        final Node l = last;//临时变量l=last，后面会直接修改last节点 指向 新加入的节点
        final Node newNode = new Node<>(l, e, null);//新元素，创建成一个节点
        last = newNode;//最后节点，指向新加入的节点
        if (l == null)//判断last是否为空，为空代表是第一次新增节点
            first = newNode;//首节点指向新加入的节点
        else//last不为空表示当前链表有值，让l节点的参数 next指向新加入的节点
            l.next = newNode;
        size++;//链表大小+1
        modCount++;//链表修改次数+1
    }

    private static class Node {
        E item;//节点-值
        Node next;//下一个节点
        Node prev;//上一个节点

        Node(Node prev, E element, Node next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }

链表指定位置添加元素 add(int index, E element)

    public void add(int index, E element) {
        checkPositionIndex(index);//判断index是否>=0，并且index<=size,否则抛出IndexOutOfBoundsException异常

        if (index == size)//判断index等于size直接添加到链表尾部
            linkLast(element);//同add(E e)方法
        else
            linkBefore(element, node(index));//node()方法先根据index标在链表取得对应到Node节点，并把新元素，添加到Node节点之前
    }

    //根据下标获得节点
    Node node(int index) {
        // assert isElementIndex(index);

        //size >> 1 等同 size除以2
        //判断index 下标是在链表的前半部分，是则从链表头部开始遍历，否则从链表尾部向前遍历
        //加了一个判断,最多只需要遍历一半链表即可，复杂度从O(n)降到了O(1)
        if (index < (size >> 1)) {
            Node x = first;//从链表头部向后遍历
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {
            Node x = last;//从链表尾部向前遍历
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }

根据下标删除节点 remove(int index)

   //根据下标删除节点
    public E remove(int index) {
        checkElementIndex(index);//判断下标是否越界
        return unlink(node(index));
    }
	
    //链表-删除节点
    E unlink(Node x) {
        // assert x != null;
        final E element = x.item;//删除节点的元素
        final Node next = x.next;//删除节点的下一个节点
        final Node prev = x.prev;//删除节点的上一个节点

        if (prev == null) {//prev等于null，说明是第一个节点
            first = next;
        } else {
            prev.next = next;//删除节点的上一个节点，next参数指向 删除节点的下一个节点
            x.prev = null;//删除节点的上一个节点，设置为null取消关联
        }

        if (next == null) {//next等于null，说明是尾部节点
            last = prev;
        } else {
            next.prev = prev;//删除节点的下一个节点,参数prev指向 删除节点的上一个节点
            x.next = null;//删除节点的下一个节点，设置为null取消关联
        }

        x.item = null;//节点元素设置为null，方便gc回收
        size--;//链表大小-1
        modCount++;//链表修改次数+1
        return element;//返回删除的元素值
    }

根据元素删除节点 remove(Object o)

    //删除链表中第一个匹配o的元素
    public boolean remove(Object o) {
        if (o == null) {//先判断o是否为空
            for (Node x = first; x != null; x = x.next) {
                if (x.item == null) {//判断元素是否为null
                    unlink(x);//链表删除元素
                    return true;
                }
            }
        } else {
            for (Node x = first; x != null; x = x.next) {
                if (o.equals(x.item)) {//判断元素是否相等
                    unlink(x);//链表删除元素
                    return true;
                }
            }
        }
        return false;
    }

根据下标获得元素 get(int index)

    //根据下标获得节点
    public E get(int index) {
        checkElementIndex(index);//判断index是大于0，并且小于等于size，否则抛出异常
        return node(index).item;//node()方法获取下标对应的Node，并返回Node的item
    }

时间复杂度

添加元素 add(E e)

最好时间复杂度是 O(1) ，最坏时间复杂度是 O(n) ，平均时间复杂度是 O(n) 。
最好时间复杂度发生在头部、或尾部添加的情况。

链表指定位置添加元素 add(int index, E element)

最好时间复杂度是 O(1) ，最坏时间复杂度是 O(n) ，平均时间复杂度是 O(n) 。
最好时间复杂度发生在头部、或尾部添加的情况。

根据下标删除节点 remove(int index)

最好时间复杂度是 O(1) ，最坏时间复杂度是 O(n) ，平均时间复杂度是 O(n) 。
最好时间复杂度发生在头部、或尾部移除的情况。

根据元素删除节点 remove(Object o)

最好时间复杂度是 O(1) ，最坏时间复杂度是 O(n) ，平均时间复杂度是 O(n) 。
最好时间复杂度发生在头部移除的情况。

根据下标获得元素 get(int index)

最好时间复杂度是 O(1)，平均时间复杂度是 O(n) ，查找指定元素的平均时间复杂度是 O(n) 。
最好时间复杂度发生在下标为0或者等于size的位置，因为LinkedList会根据index是否超过了 size除以2 来作为依据看是从链表头部往后面遍历，还是链表尾部向前遍历，所以基本上只需要遍历一半的链表就能找到对应下标的元素了。

小结

1、LinkedList做插入、删除的时候，慢在寻址，快在只需要改变前后Node的引用地址即可
2、适用于频繁的元素修改的场景，对于查询场景比较多的适合请适用这种数据结构