一.LinkedList数据结构

1.1 数据结构

LinkedList 底层数据结构是一个双向链表，整体结构如下图所示：

注意事项：

• 链表每个节点叫做 Node，Node 有 prev 属性，代表前一个节点的位置，next 属性，代表后一个节点的位 置
• first 是双向链表的头节点，它的前一个节点是 null。
• last 是双向链表的尾节点，它的后一个节点是 null；
• 当链表中没有数据时，first 和 last 是同一个节点，前后指向都是 null；
• 因为是个双向链表，是没有大小限制的。

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

二.源码分析

2.1 LinkedList类注释解析

• 使用“双向链表”来实现List与Deque接口。 实现了所有List接口中的方法，并且允许存放所有元素，包括Null。
• 所有的操作都可通过双向链表完成。通过从开头或者结尾遍历集合，去接近要操作的那个元素。
• 是非线程安全的，多线程情况下，推荐使用线程安全类：Collections#synchronizedList
• 增强 for 循环，或者使用迭代器迭代过程中，如果数组大小被改变，会快速失败，抛出异常。

2.2 新增

源码解析：

​ 新增节点时，我们可以选择追加到链表头部，还是追加到链表尾部，add 方法默认是从尾部开始追加，addFirst 方

法是从头部开始追加：

添加：

 /**
     * 将元素添加到链表尾部，等于addFirst 
     */
    public boolean add(E e) {
        linkLast(e);
        return true;
    }

从尾部增加：

    /**
     *  从尾部开始追加节点
     */
    void linkLast(E e) {
        // 把尾节点数据暂存
        final Node<E> l = last;
        // 新建新的节点，初始化入参含义： 
        // l 是新节点的前一个节点，当前值是尾节点值 
        // e 表示当前新增节点，当前新增节点后一个节点是 null
        final Node<E> newNode = new Node<>(l, e, null);
        // 将新建节点追加到尾部
        last = newNode;
        //如果链表为空 l 是尾节点，尾节点为空，链表即空，头部和尾部是同一个节点，都是新建的节点
        if (l == null)
            first = newNode;
        else
        //否则把前尾节点的下一个节点，指向当前尾节点。
            l.next = newNode;
        //大小和版本更改
        size++;
        modCount++;
    }

从头部增加：

    /**
     *从头部开始追加节点
     */
    private void linkFirst(E e) {
         // 把头节点数据暂存
        final Node<E> f = first;
        // 新建新的节点，初始化入参含义： 
        // l 是新节点的前一个节点，当前值是尾节点值 
        // f 表示当前新增节点，当前新增节点后一个节点是 null
        final Node<E> newNode = new Node<>(null, e, f);
         // 将新建节点追加到头部
        first = newNode;
        //如果链表为空 f 是头节点，头节点为空，链表即空，头部和尾部是同一个节点，都是新建的节点
        if (f == null)
            last = newNode;
        else
        //上一个头节点的前一个节点指向当前节点
            f.prev = newNode;
        size++;
        modCount++;
    }

注意事项：

• 头部追加节点和尾部追加节点，只是前者是移动头节点的 prev 指向，后者是移动尾节点的 next 指向，两者区别不大。

2.3 删除实现

源码解析：

LinkedList节点删除的方式和追加类似，我们可以选择从头部删除，也可以选择从尾部删除，删除操作会把节点的值，前后指

向节点都置为 null。

从头部删除：

  /**
     * 从头部开始删除节点
     */
    private E unlinkFirst(Node<E> f) {
        //拿出头节点的值，作为方法的返回值
        final E element = f.item;
        // 拿出头节点的下一个节点
        final Node<E> next = f.next;
        //帮助 GC 回收头节点
        f.item = null;
        f.next = null; 
        //头节点的下一个节点成为头节点
        first = next;
        //如果 next 为空，表明链表为空
        if (next == null)
            last = null;
        else
        //链表不为空，头节点的前一个节点指向 null
            next.prev = null;
        //修改链表大小和版本
        size--;
        modCount++;
        return element;
    }

从尾部删除：

/**
 * 和从头部删除基本一致
 */
private E unlinkLast(Node<E> l) {
    // assert l == last && l != null;
    final E element = l.item;
    final Node<E> prev = l.prev;
    l.item = null;
    l.prev = null; // help GC
    last = prev;
    if (prev == null)
        first = null;
    else
        prev.next = null;
    size--;
    modCount++;
    return element;
}

注意事项：

• 前后指向节点都置为 null，是为了帮助 GC 进行回收；
• 从源码中我们可以了解到，链表结构的节点新增、删除仅仅把前后节点的指向修改了， 所以LinkedList新增和删除度很快。

2.4 实现查询

查询：

/**
 * 根据链表索引位置查询节点
 */
Node<E> node(int index) {
    //  如果 index 处于队列的前半部分，从头开始找，size >> 1 是 size 除以 2 的意思。
    if (index < (size >> 1)) {
        Node<E> x = first;
   // 直到 for 循环到 index 的前一个 node 停止
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
      // 如果 index 处于队列的后半部分，从尾开始找
        Node<E> x = last;
      // 直到 for 循环到 index 的后一个 node 停止
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

注意事项：

​ LinkedList 并没有采用从头循环到尾的做法，而是采取了二分法，首先看 index 是在链表的前半部分，还是后半部分。如果是前半部分，就从头开始寻找，反之亦然。通过这种方式，使循环的次数 至少降低了一半，提高了查找的性能。

三.时间复杂度

get() 获取第几个元素，依次遍历，复杂度O(n)
add(E) 添加到末尾，复杂度O(1)
add(index, E) 添加第几个元素后，需要先查找到第几个元素，直接指针指向操作，复杂度O(n) （这个比较容易想错）
remove（）删除元素，直接指针指向操作，复杂度O(1)

四.线程安全

4.1 线程安全问题

只有当 LinkedList作为共享变量时，才会有线程安全问题，当 LinkedList是方法内的局部变量时，是没有线程安全的问题的。

LinkedList有线程安全问题的原因，是因为 LinkedList自身的 size、modConut 在进行各种操作时，都没有加锁，而且这些变量的类型并非是可见（volatile）的，所以如果多个线程对这些变量进行操作时，可能会有值被覆盖的情况。

类注释中推荐使用 Collections#synchronizedList 来保证线程安全，SynchronizedList 是通过在每个方法上面加上锁来实现，虽然实现了线程安全，但是性能大大降低，具体实现源码：

public boolean add(E e) {
    synchronized (mutex) {return c.add(e);}
}

我们也可以使用ConcurrentLinkedQueue来保证线程安全,

五.总结

LinkedList的底层是链表结构 ,适用于适合于经常新增和删除的场景,
欢迎关注公众号：前程有光，领取一线大厂Java面试题总结+各知识点学习思维导+一份300页pdf文档的Java核心知识点总结！ 这些资料的内容都是面试时面试官必问的知识点，篇章包括了很多知识点，其中包括了有基础知识、Java集合、JVM、多线程并发、spring原理、微服务、Netty 与RPC 、Kafka、日记、设计模式、Java算法、数据库、Zookeeper、分布式缓存、数据结构等等。