[toc]

定义

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

LinkedList的底层数据结构是双向链表。
通过对LinkedList的定义可以看出LinkedList不支持随机访问因为没有实现RandomAccess接口，因此LinkedList的遍历优先选择迭代器遍历，实现了Deque接口说明LinkedList是一个双端队列，可以用来当做队列(先进先出)和栈(先进后出)。

继承了AbstractSequentialList，说明是顺序访问的而不是像ArrayList可以支持随机访问。
注:不管是ArrayList、LinkedList 在批量add的时候，都会先转化成数组去做。 因为数组可以用for循环直接花式遍历。比较方便 高效

内部类

在了解LinkedList之前先看一下LinkedList定义的Node内部类。

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

通过Node的定义可以确定LinkedList是一个双向链表，既然是双向链表就不存在像ArrayList那样的扩容了，他的删除添加元素也只需要修改链表节点的指针效率相对来说比较高，但是因为是链表形式，查找的时间复杂度是O(n)相对ArrayList的O(1)肯定是慢了一些。

属性

//记录链表的长度
transient int size = 0;
//链表的第一个节点
transient Node<E> first;
//链表的尾结点
transient Node<E> last;

其中first节点需要保证(first == null && last == null) ||(first.prev == null && first.item != null)表明了frist节点的要求：

• 要么链表是空的也就是first和last都是空的
• 如果first和last不为空，那么first上一个节点必须是null，而且first.item存在内容，表明first节点是链表的第一个节点。
  last节点也是类似(first == null && last == null) ||(last.next == null && last.item != null)
• 要么链表是空的也就是first和last都是空的
• 如果如果first和last不为空，那么last节点next必须为空，并且last.item存在内容，保证last节点是链表的最后的节点。

构造函数

LinkedList只有两个构造函数

无参的构造函数

创建一个空链表

public LinkedList() {
    }

使用另一个集合的Collection的构造方法

首先调用无参的构造方法，创建一个空的链表，然后批量添加元素，addAll方法下面会介绍。

public LinkedList(Collection<? extends E> c) {
        this();
        addAll(c);
    }
    

node方法,通过下标获取对应节点

先看一下node方法，因为下面会频繁使用这个方法，node()方法不允许外部调用。
会根据index与size/2 (size>>1==size/2)来确定是从头开始遍历寻找还是从尾遍历寻找。

    Node<E> node(int index) {
        // assert isElementIndex(index);
        //用来判断index是距离第一个节点进还是距离最后一个结点进
        if (index < (size >> 1)) {
            //如果index<size >> 1=size/2说明插入位置在中央位置的左侧也就是距离头结点更近，所以从头结点开始遍历
            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;
        }
    }

添加元素

在链表尾部进行添加

    public boolean add(E e) {
        linkLast(e);
        return true;
    }
    void linkLast(E e) {
        //获取尾结点
        final Node<E> l = last;
        //创建节点第一个参数l为上一个节点，e为Node的iterm，null为下一个节点，因为是添加到尾部所以下一个节点是null，上一个节点是之前的尾结点
        final Node<E> newNode = new Node<>(l, e, null);
        //将新创建的节点重新赋值到尾结点last
        last = newNode;
        if (l == null)
        //如果是第一次添加那么l必定为空，所以新的节点即是最后一个节点也是第一个节点
            first = newNode;
        else
        //如果l！=null说明不是第一次添加，那么需要将之前的最后一个节点也就是l的下一个与新的节点进行拼接
            l.next = newNode;
        size++;
        modCount++;
    }

指定下标下添加

因为LinkedList不能像ArrayList那样通过下标进行快速定位元素，所以需要循环找到对应index的位置

    public void add(int index, E element) {
        //判断是否越界
        checkPositionIndex(index);
        //如果index==size说明正好在链表尾部添加元素，直接调用linkLast即可
        if (index == size)
            linkLast(element);
        else
            //否则是在链表中间添加元素，需要先调用node()方法找到对应元素，然后进行拼接
            linkBefore(element, node(index));
    }
    Node<E> node(int index) {
        // assert isElementIndex(index);
        //用来判断index是距离第一个节点进还是距离最后一个结点进
        if (index < (size >> 1)) {
            //如果index<size >> 1=size/2说明插入位置在中央位置的左侧也就是距离头结点更近，所以从头结点开始遍历
            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;
        }
    }
    //找到符合index的位置的节点，将他进行链接，其中succ是链表中的元素，e是要添加的元素
    void linkBefore(E e, Node<E> succ) {
        // assert succ != null;
        //获取前驱结点
        final Node<E> pred = succ.prev;
        //创建新的节点，他的前驱是succ的前驱，他的下一个节点是succ
        final Node<E> newNode = new Node<>(pred, e, succ);
        succ.prev = newNode;
        //进行链表，如果pred是null说明succ之前是第一个节点，那么现在第一个节点也就是头结点将变为newNode
        if (pred == null)
            first = newNode;
        else
            //如果不是那么正常建立连接
            pred.next = newNode;
        size++;
        modCount++;
    }

在尾部批量添加

    public boolean addAll(Collection<? extends E> c) {
        //调用的重载方法
        return addAll(size, c);
    }

指定下标下进行批量添加

public boolean addAll(int index, Collection<? extends E> c) {
        //判断越界
        checkPositionIndex(index);
        //先将添加的集合改为数组
        Object[] a = c.toArray();
        int numNew = a.length;
        //如果长度为0直接返回
        if (numNew == 0)
            return false;
        //pred记录前驱，succ记录需要添加到指定位置的原有元素，也就是现在新添加的链表最尾结点
        Node<E> pred, succ;
        if (index == size) {
            //如果index==size，说明是直接添加到尾部
            succ = null;
            pred = last;
        } else {
            //如果是中间位置，那么先找到对应的succ链表在index的原有元素
            succ = node(index);
            pred = succ.prev;
        }
        //开始遍历创建链表整条链表的第一个节点是succ.prev如果恰好在尾结点添加那么第一个节点便是last，创建好链表最后的尾部是succ
        for (Object o : a) {
            @SuppressWarnings("unchecked") E e = (E) o;
            Node<E> newNode = new Node<>(pred, e, null);
            if (pred == null)
                first = newNode;
            else
                pred.next = newNode;
            pred = newNode;
        }
        如果succ是null说明是在尾部进行添加的链表，那么最后一个节点就是pred
        if (succ == null) {
            last = pred;
        } else {
            //如果在中间那么因为是双指针，所以succ与pred建立双向的指针
            pred.next = succ;
            succ.prev = pred;
        }

        size += numNew;
        modCount++;
        return true;
    }

删除remove

根据指定下标进行删除

    public E remove(int index) {
        //越界判断
        checkElementIndex(index);
        //找到对应节点，取消链接
        return unlink(node(index));
    }
    //其实就是x.pre.next=x.next;
    x.next.pre=x.pre
    //如果恰好是第一个节点或者最后一个节点特殊处理一下
    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;
        //如果前置节点为null，说明当前节点原本是头结点
        if (prev == null) {
            first = next;
        } else {
            prev.next = next;
            x.prev = null; //将当前节点的前置变为null
        }
        
        if (next == null) {//如果后置为null说明当前节点本来是尾节点
            last = prev;
        } else {
            next.prev = prev;
            x.next = null; //将当前节点后置变为null
        }

        x.item = null; //将当前节点元素变为null，方便GC
        size--;
        modCount++;
        return element;//返回元素值
    }

删除指定元素

    //因为要考虑o为null的情况分两种情况遍历，从头结点开始遍历，遍历到第一个与目标元素相等的，然后调用unlink取消链接，也ArrayList一样也是只能删除一个，距离链表头部进的那个
    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;
    }

批量移除/保留 removeAll/retainAll

LinkedList没有直接实现这两个方法，而是直接使用父类中统一实现的，因为LinkedList不支持随机访问，所以这两个方法调用的是迭代器，这里不再展示

其余的removeXX()

其余的删除方法都是类型的比如删除头结点的removeFirst()、删除尾结点的removeLast(),其实也都是把对应的节点前驱后驱改掉，并且释放对应元素的节点。

get方法

本质上还是通过上面的所讲的node方法获取对应元素，根据index与size/2的关系来判定是从头遍历还是从尾遍历

public E get(int index) {
    checkElementIndex(index);//判断是否越界 [0,size)
    return node(index).item; //调用node()方法 取出 Node节点，
}

set()方法

先通过node()方法找到Node，然后替换值
修改不记录modCount值

public E set(int index, E element) {
    //检查越界[0,size)
    checkElementIndex(index); 
    Node<E> x = node(index);//取出对应的Node
    E oldVal = x.item;//保存旧值 供返回
    x.item = element;//用新值覆盖旧值
    return oldVal;//返回旧值
}

toArray()

顺带看一下toArray()毕竟是一个高频API,其实就是通过遍历链表放到对应数组中

//生成Object[]类型的
public Object[] toArray() {
        //new 一个新数组 然后遍历链表，将每个元素存在数组里，返回
        Object[] result = new Object[size];
        int i = 0;
        for (Node<E> x = first; x != null; x = x.next)
            result[i++] = x.item;
        return result;
    }
//生成指定类型的数组
public <T> T[] toArray(T[] a) {
        if (a.length < size)
            a = (T[])java.lang.reflect.Array.newInstance(
                                a.getClass().getComponentType(), size);
        int i = 0;
        Object[] result = a;
        for (Node<E> x = first; x != null; x = x.next)
            result[i++] = x.item;

        if (a.length > size)
            a[size] = null;

        return a;
    }

总结

LinkedList是双向链表

• 链表的批量增加，是靠for循环遍历原数组，依次插入到对应节点，对比ArrayList是通过System.arraycopy完成批量增加的，增加一定会修改modCount
• 通过index获取某个node，会根据index处于前半段还是后半段，进行一个折半，提升查询效率
• 删也一定会修改modCount，按下标删，也是先找到node，然后去掉链表，并且把对应节点释放掉
• 改也是先找到node节点，修改值，不会影响modCount