关于java LinkedList那些事

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

LinkedList继承自AbstractSequentialList，实现了List、 Deque、 Cloneable、Serializable 4个接口
用法的话基本与ArrayList用法一致，这边也不多讲啦，主要还是看看内部实现

不同于ArrayList的get方法可以轻松的看出内部是由数组实现的，所以这边就先讲结论了，LinkedList内部是由双向链表实现的^[1]，我们先来看一些基本的变量

    transient int size = 0;

    transient Node<E> first;

    transient Node<E> last;

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

• size不多讲，跟ArrayList一样，返回的是LinkedList的长度
• Node类（节点），里面一共有三个参数，
  1.item：该节点存放的元素
  2.prev：上一个节点对象
  3.next：下一个节点对象
• first就是LinkedList的第一个节点
• last则是最后一个节点

那么为什么特地弄出头尾节点来呢？

因为链表不同于数组，数组可以通过索引直接定位到所需要操作的元素，而链表不行，它只能通过.next一个一个的遍历元素直到查询到指定数据，这样一来查询的时间就呈线性增长了。所以在遍历链表的时候，采用了“二分法”，若需要对>size/2位置的元素进行CRUD，则从尾结点从后往前遍历，否则从头结点从前往后遍历

---

我们同样来看看LinkedList的add方法：

    LinkedList<String> linkedList = new LinkedList<>();
    linkedList.add("asd");


    public LinkedList() {
    }

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

     */
    public boolean add(E e) {
        linkLast(e);
        return true;
    }

    /**
     * Links e as last element.
     */
    void linkLast(E e) {
        这里我们知道last一开始是为null的
        final Node<E> l = last;

        这个是需要插入的节点，pre（上一个节点）为l（尾结点），
        next（下一个节点）为null，元素值为e
        final Node<E> newNode = new Node<>(l, e, null);

        将需要插入的值赋予尾结点
        last = newNode;

        如果旧的尾节点为null，说明链表为空，此时将需要插入
        的节点赋值给头结点
        if (l == null)
            first = newNode;
        else
             否则将需要插入的节点插到尾结点后面（last.next指向新节点
             ，上方在声明newNode的时候就将newNode.pre指向了last）
            l.next = newNode;
        size++;
        modCount++;
    }

public void add(int index, E element)

    public void add(int index, E element) {
        校验index是否有效，无效则直接抛出异常
        checkPositionIndex(index);
       
        如果插入的值刚好在尾结点，则直接插入
        if (index == size)
            linkLast(element);
        else
            否则进入该方法
            linkBefore(element, node(index));
    }

    /**
     * Returns the (non-null) Node at the specified element index.
     */
    Node<E> node(int index) {
        // assert isElementIndex(index);

        这里就是上面所说的，<size/2则从前往后遍历
        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;
        }
    }



    /**
     * Inserts element e before non-null Node succ.
     */
    1. 需要在succ节点前插入指定的元素
    void linkBefore(E e, Node<E> succ) {
        // assert succ != null;

        获取succ的上一个节点
        final Node<E> pred = succ.prev;
        2.生成新的节点，上一个节点为succ的上一个节点，下一个节点则为succ
        final Node<E> newNode = new Node<>(pred, e, succ);
        3.指定succ的上一个节点为新节点
        succ.prev = newNode;

        这里判断如果succ是first节点（头结点）则将新节点指定为头结点
        if (pred == null)
            first = newNode;
        else
            4.否则将新节点的上一个节点的next指向新节点
            pred.next = newNode;
        size++;
        modCount++;
    }

上面这一点其实就是对新节点的pre指向succ的pre节点，next指向succ节点，然后新节点的pre节点的next指向新节点。没错第一次接触的小伙伴一定非常绕，这里画幅图让大家更好理解（这里为了更好理解，我们就取index为1时插入，即在头结点后插入，分别对应上方的1234）

image.png

（这里有点跑题了，讲到链表去了= =）

public boolean addAll(int index, Collection<? extends E> c)

public boolean addAll(int index, Collection<? extends E> c) {
        校验index是否有效
        checkPositionIndex(index);

        Object[] a = c.toArray();
        int numNew = a.length;
        如果传进来的collection为空的，则直接返回
        if (numNew == 0)
            return false;

        succ节点：需要在succ节点前插入指定的元素（所需要插入节点的下一个节点）
        pred节点：succ的上一个节点(所需要插入节点的上一个节点）
        Node<E> pred, succ;

        if (index == size) {
            如果刚好在尾结点插入
            succ = null;
            pred = last;
        } else {
            否则遍历之前的链表，获取succ节点
            succ = node(index);
            pred = succ.prev;
        }

        for (Object o : a) {
           这边的操作无非就是重复上方add(int inedx,E e)的方法，这边就不多讲了
            @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;
        }
 
        如果是尾部插入，则将last重新赋值
        if (succ == null) {
            last = pred;
        } else {
            如果是中间/头部插入，该咋咋地
            pred.next = succ;
            succ.prev = pred;
        }

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

remove方法的话就不讲了吧，与add的原理差不多，大家可以自己去康康

我们可以发现，LinkedList插入删除是非常快的，因为只需要把上一个节点的next、下一个节点的pre指向新节点即可。与此同时还有一个问题，就是得找到所需要插入的位置才能进行增删操作，可数据量一大遍历的时间就呈线性增长了，带动着增删操作的成本也高了起来

我们以1000万条数据为例，对LinkedList与ArrayList进行对比

操作	ArrayList	LinkedList
for循环插入1000万个值	2676ms	6589ms
add头部	78ms	<1ms
add中间值	78ms	140ms
add末尾	78ms	<1ms
remove头部	15ms	<1ms
remove中间值	26ms	141ms
remove尾部	<1ms	<1ms
get头部	<1ms	<1ms
get中间值	<1ms	140ms
get尾部	<1ms	<1ms

*以上数据仅供参考，ArrayList add、remove之前都经过trimToSize()方法处理
我们可以看到，ArrayList查询是非常快的，但是增删就有些不尽人意了（除却remove尾部，因为此时是不需要扩容处理的）
LinkedList对头尾部的增删改查都是非常快的，而中间值则非常慢

总结

• 在数据量较小的情况比如10条、100条喜欢用啥用啥
• 数据量大一点，并且总是在尾部/头部新增数据，那是非常建议使用LInkedList的
• 数据量大而查询多则使用ArrayList
• 那我数据量又多，查询增删都有该怎么选择？还是ArrayList，毕竟ArrayList你可以在一开始就申明所需要的数组大小，这样后续的扩容耗时问题就可以少考虑一点

---

1. 数据结构本系列就不展开讨论了，但是这样其实是有点本末倒置了，因为不了解链表、树这些数据结构后续的集合也很难理解，但是没办法数据结构里面随便拎出一个就够讲大半天的，预计在2月份的时候会有数据结构系列的，届时与算法一起研究 ↩