• 引入
• LinkedList概述
• 链表的数据结构
• 自定义LinkedList
• LinkedList源码分析
  • LinkedList的特性
  • 继承结构以及层次关系
  • 类的属性
  • 构造方法
  • 内部类（Node）
  • 核心方法
  • LinkedList的迭代器
• 总结

引入

问题：在集合的任何位置（头部，中间，尾部）添加，获取，删除狗狗对象。

插入，删除操作频繁时，可使用 LinkedList 来提高效率

LinkedList 提供对头部和尾部元素进行添加和删除操作的方法。

LinkedList 的特殊方法

集合框架有何好处？

Java 集合框架中包含哪些接口和类？

ArrayList 和 LinkedList 有何异同？

LinkedList概述

我们都知道它的底层是由链表实现的，所以我们要明白什么是链表？

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

LinkedList 是一种可以在任何位置进行高效地插入和移除操作的有序序列，它是基于双向链表实现的。

LinkedList 是一个继承于 AbstractSequentialList 的双向链表。它也可以被当作堆栈、队列或双端队列进行操作。

LinkedList 实现 List 接口，能对它进行队列操作。

LinkedList 实现 Deque 接口，即能将 LinkedList 当作双端队列使用。

LinkedList 实现了 Cloneable 接口，即覆盖了函数 clone()，能克隆。

LinkedList 实现 java.io.Serializable 接口，这意味着 LinkedList 支持序列化，能通过序列化去传输。

LinkedList 是非同步的。

推荐文章：LinkList 详解 (opens new window)

链表的数据结构

单向链表：

element：用来存放元素

next：用来指向下一个节点元素

通过每个结点的指针指向下一个结点从而链接起来的结构，最后一个节点的 next 指向 null。

单向循环链表：

element、next 跟前面一样，在单向链表的最后一个节点的 next 会指向头节点，而不是指向 null，这样存成一个环

双向链表：

element：存放元素

pre：用来指向前一个元素

next：指向后一个元素

双向链表是包含两个指针的，pre 指向前一个节点，next 指向后一个节点，但是第一个节点 head 的 pre 指向 null，最后一个节点的 tail 指向 null。

双向循环链表：

element、pre、next 跟前面的一样

第一个节点的 pre 指向最后一个节点，最后一个节点的 next 指向第一个节点，也形成一个「环」。

LinkedList 的数据结构

如上图所示，LinkedList 底层使用的双向链表结构，有一个头结点和一个尾结点，双向链表意味着我们可以从头开始正向遍历，或者是从尾开始逆向遍历，并且可以针对头部和尾部进行相应的操作。

自定义LinkedList

模拟源码自定义一个 LinkedList，这样读源码理解更佳。

class Node {
    // 前一个元素地址
    Node pre;
    // 当前存入的元素地址
    Object obj;
    // 后一个元素地址
    Node next;
    //.... set get toString 方法，这里因为篇幅不写，其实需要写
}
public class MyLinkedList {
    // 首 Node 对象
    Node first;
    // 尾Node对象
    Node last;
    // 节点长度
    int size;
    // 无参构造器
    public MyLinkedList(){ }
    
    public void add(Object o){
        if(first == null){
            // 当前 Node 对象
            Node node = new Node();
            node.setPre(null);
            node.setObj(o);
            node.setNext(null);
            // 初始 first 和 last 为空，所以 first 和 last 都指向最开始的首 Node 对象
            first = node;
            last = node;
        }else {
            Node node = new Node();
            // 此时有了第二个或者更多的 Node 节点，所以第二个节点的 first 指向第一个节点的 last，第一个 Node 节点的 last 指向第二个 Node 节点
            node.setPre(last);
            node.setObj(o);
            node.setNext(null);
            last.setNext(node);
            last = node; // 指向第二个节点 
            
        }
        // 添加一次，长度 + 1
        size++;
    }
    public Object get(int index){
        Node node = first;
        for (int i = 0; i < index; i++) {
            node = node.getNext();
        }
        return node.getObj(); // 不要返回 Node 对象，会报错，应该返回的是当前存入的元素
    }
    
    public int size(){
        return size;
    }
}

class Test{
    public static void main(String[] args) {
        MyLinkedList list = new MyLinkedList();
        list.add("aa");
        list.add("bb");
        list.add("cc");
        System.out.println(list.get(2)); // cc
         System.out.println(list.size()); // 3
    }
}

LinkedList源码分析

接下来又到了大家喜欢的读源码环节**😄**。

LinkedList的特性

在我们平常中，我们只知道一些常识性的特点：

• 是通过链表实现的
• 如果在频繁的插入，或者删除数据时，就用 LinkedList 性能会更好

那我们通过 API 去查看它的一些特性

Doubly-linked list implementation of the List and Deque interfaces. Implements all optional list operations, and permits all elements (including null).

这告诉我们，LinkedList 是一个双向链表，并且实现了 List 和 Deque 接口中所有的列表操作，并且能存储任何元素，包括 null，这里我们可以知道 linkedList 除了可以当链表使用，还可以当作队列使用，并能进行相应的操作。

All of the operations perform as could be expected for a doubly-linked list. Operations that index into the list will traverse the list from the beginning or the end, whichever is closer to the specified index.

这个告诉我们，LinkedList 在执行任何操作的时候，都必须先遍历此列表来靠近通过 index 查找我们所需要的的值。通俗点讲，这就告诉了我们这个是顺序存取，每次操作必须先按开始到结束的顺序遍历，随机存取，就是 ArrayList，能够通过 index。随便访问其中的任意位置的数据，这就是随机列表的意思。

API 中接下来讲的一大堆，就是说明 LinkedList 是一个非线程安全的（异步），其中在操作 Interator 时，如果改变列表结构（add，delete 等），会发生 fail-fast。

通过 API 再次总结一下 LinkedList 的特性

1. 异步，也就是非线程安全

2. 双向链表。由于实现了 List 和 Deque 接口，能够当作队列来使用

   链表：查询效率不高，但是插入和删除这种操作性能好

3. 是顺序存取结构（注意和随机存取结构两个概念搞清楚）

继承结构以及层次关系

IDEA 里 CTRL + H 快捷查看

我们可以看到，LinkedList 在最底层，说明他的功能最为强大，并且细心的还会发现，ArrayList 有四层，这里多了一层 AbstractSequentialList 的抽象类，为什么呢？

通过 API 我们会发现：

• 减少实现顺序存取（例如 LinkedList）这种类的工作，通俗的讲就是方便，抽象出类似 LinkedList 这种类的一些共同的方法
• 既然有了上面这句话，那么以后如果自己想实现顺序存取这种特性的类（就是链表形式），那么就继承这个 AbstractSequentialList 抽象类，如果想像数组那样的随机存取的类，那么就去实现 AbstracList 抽象类
• 这样的分层，就很符合我们抽象的概念，越在高处的类，就越抽象，往在底层的类，就越有自己独特的个性。自己要慢慢领会这种思想
• LinkedList 的类继承结构很有意思，我们着重要看是 Deque 接口，Deque 接口表示是一个双端队列，那么也意味着 LinkedList 是双端队列的一种实现，所以，基于双端队列的操作在 LinkedList 中全部有效。

public abstract class AbstractSequentialList<E>
extends AbstractList<E>

第一段

这里第一段就解释了这个类的作用，这个类为实现 List 接口提供了一些重要的方法，尽最大努力去减少实现这个「顺序存取」的特性的数据存储（例如链表）的什么随机存取数据（例如数组）的类应该优先使用 AbstractList 从上面就可以大概知道，AbstractSwquentialList 这个类是为了减少 LinkedList 这种顺序存取的类的代码复杂度而抽象的一个类。

第二段

这一段大概讲的就是这个 AbstractSequentialList 这个类和 AbstractList 这个类是完全相反的。比如 get、add 这个方法的实现。

第三段

这里就是讲一些我们自己要继承该类，该做些什么事情，一些规范。

接口实现分析

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

1. List 接口：列表，add、set 等一些对列表进行操作的方法

2. Deque 接口：有队列的各种特性

3. Cloneable 接口：能够复制，使用那个 copy 方法

4. Serializable 接口：能够序列化

5. 应该注意到没有 RandomAccess：那么就推荐使用 iterator，在其中就有一个 forEach，增强的 for 循环，其中原理也就是 iterator，我们在使用的时候，使用 forEach 或者 iterator 都可以

iterator：

public static void method() {
    List<String> l = new ArrayList<>();

    l.add("hello");
    l.add(0, "123");
    l.add("789");
    l.set(0, "456");
    l.remove(0);

    ListIterator<String> lit = l.listIterator();
    while (lit.hasNext()) {
        String next = lit.next();
        // l.add("111");
        lit.add("111");
        System.out.println(next);

    }
    System.out.println(l);
}

类的属性

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
    // 实际元素个数
    transient int size = 0;
    // 头结点
    transient Node<E> first;
    // 尾结点
    transient Node<E> last;
}

LinkedList 的属性非常简单，一个头结点、一个尾结点、一个表示链表中实际元素个数的变量。注意，头结点、尾结点都有 transient 关键字修饰，这也意味着在序列化时该域是不会序列化的。

构造方法

两个构造方法（两个构造方法都是规范规定需要写的）

空参构造函数

public LinkedList() {
    
}

有参构造函数

// 将集合 c 中的各个元素构建成 LinkedList 链表
public LinkedList(Collection<? extends E> c) {
    // 调用无参构造函数
    this();
    // 添加集合中所有的元素
    addAll(c);
}

说明：会调用无参构造函数，并且会把集合中所有的元素添加到 LinkedList 中。

内部类（Node）

// 根据前面介绍双向链表就知道这个代表什么了，linkedList 的奥秘就在这里。
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 就是实际的结点，用于存放实际元素的地方。

核心方法

add()方法

public boolean add(E e) {
    // 添加到末尾
    linkLast(e);
    return true;
}

说明：add 函数用于向 LinkedList 中添加一个元素，并且添加到链表尾部。具体添加到尾部的逻辑是由 LinkLast 函数完成的。

LinkLast(E e)

/**
 * Links e as last element.
 */
void linkLast(E e) {
    final Node<E> l = last; // 临时节点 l（L 的小写）保存 last，也就是 l 指向了最后一个节点
    final Node<E> newNode = new Node<>(l, e, null); // 将 e 封装为节点，并且 e.prev 指向了最后一个节点
    last = newNode; // newNode 成为了最后一个节点，所以 last 指向了它
    if (l == null) // 判断是不是一开始链表中就什么都没有，如果没有，则 newNode 就成为了第一个节点，first 和 last 都要指向它
        first = newNode;
    else  // 正常的在最后一个节点后追加，那么原先的最后一个节点的 next 就要指向现在真正的最后一个节点，原先的最后一个节点就变成了倒数第二个节点
        l.next = newNode;
    size++; ; // 添加一个节点，size 自增
    modCount++;
}

说明：对于添加一个元素至链表中会调用 add 方法 -> linkLast 方法。

举例一

List<Integer> lists = new LinkedList<Integer>();
lists.add(5);
lists.add(6);

首先调用无参构造函数，之后添加元素 5，之后再添加元素 6。具体的示意图如下：

上图的表明了在执行每一条语句后，链表对应的状态。

addAll()方法

addAll 有两个重载函数，addAll(Collection) 型和 addAll(int, Collection) 型，我们平时习惯调用的 addAll(Collection) 型会转化为 addAll(int, Collection) 型。

public boolean addAll(Collection<? extends E> c) {
// 继续往下看
return addAll(size, c);
}

addAll(size，c)：这个方法，能包含三种情况下的添加，我们这里分析的只是构造方法，空链表的情况，看的时候只需要按照不同的情况分析下去就行了。

//真正核心的地方就是这里了，记得我们传过来的是size，c
public boolean addAll(int index, Collection<? extends E> c) {
    //检查index这个是否为合理。这个很简单，自己点进去看下就明白了。
    checkPositionIndex(index);
	//将集合c转换为Object数组 a
    Object[] a = c.toArray();
    //数组a的长度numNew，也就是由多少个元素
    int numNew = a.length;
    if (numNew == 0)
        //集合c是个空的，直接返回false，什么也不做。
        return false;
	//集合c是非空的，定义两个节点(内部类)，每个节点都有三个属性，item、next、prev。注意：不要管这两个什么含义，就是用来做临时存储节点的。这个Node看下面一步的源码分析，Node就是linkedList的最核心的实现，可以直接先跳下一个去看Node的分析
    Node<E> pred, succ;
    //构造方法中传过来的就是index==size
    if (index == size) {
        //linkedList中三个属性：size、first、last。 size：链表中的元素个数。first：头节点 last：尾节点，就两种情况能进来这里
        //情况一、：构造方法创建的一个空的链表，那么size=0，last、和first都为null。linkedList中是空的。什么节点都没有。succ=null、pred=last=null
        
        //情况二、：链表中有节点，size就不是为0，first和last都分别指向第一个节点，和最后一个节点，在最后一个节点之后追加元素，就得记录一下最后一个节点是什么，所以把last保存到pred临时节点中。

        succ = null;
        pred = last;
    } else {
        //情况三、index！=size，说明不是前面两种情况，而是在链表中间插入元素，那么就得知道index上的节点是谁，保存到succ临时节点中，然后将succ的前一个节点保存到pred中，这样保存了这两个节点，就能够准确的插入节点了
        //举个简单的例子，有2个位置，1、2、如果想插数据到第二个位置，双向链表中，就需要知道第一个位置是谁，原位置也就是第二个位置上是谁，然后才能将自己插到第二个位置上。如果这里还不明白，先看一下文章开头对于各种链表的删除，add操作是怎么实现的。
        succ = node(index);
        pred = succ.prev;
    }
	//前面的准备工作做完了，将遍历数组a中的元素，封装为一个个节点。
    for (Object o : a) {
        @SuppressWarnings("unchecked") E e = (E) o;
        //pred就是之前所构建好的，可能为null、也可能不为null，为null的话就是属于情况一、不为null则可能是情况二、或者情况三

        Node<E> newNode = new Node<>(pred, e, null);
        //如果pred==null，说明是情况一，构造方法，是刚创建的一个空链表，此时的newNode就当作第一个节点，所以把newNode给first头节点
        if (pred == null)
            first = newNode;
        else
            //如果pred！=null，说明可能是情况2或者情况3，如果是情况2，pred就是last，那么在最后一个节点之后追加到newNode，如果是情况3，在中间插入，pred为原index节点之前的一个节点，将它的next指向插入的节点，也是对的
            pred.next = newNode;
        //然后将pred换成newNode，注意，这个不在else之中，请看清楚了。
        pred = newNode;
    }

    if (succ == null) {
        /*如果succ==null，说明是情况一或者情况二，
		情况一、构造方法，也就是刚创建的一个空链表，pred已经是newNode了，last=newNode，所以linkedList的first、last都指向第一个节点。
		情况二、在最后节后之后追加节点，那么原先的last就应该指向现在的最后一个节点
了，就是newNode。*/
        last = pred;
    } else {
        //如果succ！=null，说明可能是情况三、在中间插入节点，举例说明这几个参数的意义，有1、2两个节点，现在想在第二个位置插入节点newNode，根据前面的代码，pred=newNode，succ=2，并且1.next=newNode，已经构建好了，pred.next=succ，相当于在newNode.next =2； succ.prev = pred，相当于 2.prev = newNode， 这样一来，这种指向关系就完成了。first和last不用变，因为头节点和尾节点没变
        pred.next = succ;
        succ.prev = pred;
    }
	//增加了几个元素，就把 size = size +numNew 就可以了
    size += numNew;
    modCount++;
    return true;
}

说明：参数中的 index 表示在索引下标为 index 的结点（实际上是第 index + 1 个结点）的前面插入。

在 addAll 函数中，addAll 函数中还会调用到 node 函数，get 函数也会调用到 node 函数，此函数是根据索引下标找到该结点并返回，具体代码如下：

Node<E> node(int index) {
    // assert isElementIndex(index);
	// 判断插入的位置在链表前半段或者是后半段
    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; // 返回该结点
    }
}

说明：在根据索引查找结点时，会有一个小优化，结点在前半段则从头开始遍历，在后半段则从尾开始遍历，这样就保证了只需要遍历最多一半结点就可以找到指定索引的结点。

举例说明调用 addAll 函数后的链表状态：

List<Integer> lists = new LinkedList<Integer>();
lists.add(5);
lists.addAll(0, Arrays.asList(2, 3, 4, 5));

上述代码内部的链表结构如下：

addAll()中的一个问题：

在 addAll 函数中，传入一个集合参数和插入位置，然后将集合转化为数组，然后再遍历数组，挨个添加数组的元素，但是问题来了，为什么要先转化为数组再进行遍历，而不是直接遍历集合呢？

从效果上两者是完全等价的，都可以达到遍历的效果。关于为什么要转化为数组的问题，我的思考如下：

1. 如果直接遍历集合的话，那么在遍历过程中需要插入元素，在堆上分配内存空间，修改指针域，这个过程中就会一直占用着这个集合，考虑正确同步的话，其他线程只能一直等待
2. 如果转化为数组，只需要遍历集合，而遍历集合过程中不需要额外的操作，所以占用的时间相对是较短的，这样就利于其他线程尽快的使用这个集合。说白了，就是有利于提高多线程访问该集合的效率，尽可能短时间的阻塞

remove(Object o)

/**
 * Removes the first occurrence of the specified element from this list,
 * if it is present.  If this list does not contain the element, it is
 * unchanged.  More formally, removes the element with the lowest index
 * {@code i} such that
 * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>
 * (if such an element exists).  Returns {@code true} if this list
 * contained the specified element (or equivalently, if this list
 * changed as a result of the call).
 *
 * @param o element to be removed from this list, if present
 * @return {@code true} if this list contained the specified element
 */

// 首先通过看上面的注释，我们可以知道，如果我们要移除的值在链表中存在多个一样的值，那么我们会移除index 最小的那个，也就是最先找到的那个值，如果不存在这个值，那么什么也不做。
public boolean remove(Object o) {
    // 这里可以看到，linkedList 也能存储 null
    if (o == null) {
        // 循环遍历链表，直到找到 null 值，然后使用 unlink 移除该值。下面的这个 else 中也一样
        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;
}

unlink(Node<E> x)

// Unlinks non-null node x.
// 不能传一个 null 值过，注意，看之前要注意之前的 next、prev 这些都是谁。
E unlink(Node<E> x) {
    // assert x != null;
    // 拿到节点 x 的三个属性
    final E element = x.item;
    final Node<E> next = x.next;
    final Node<E> prev = x.prev;
	
    // 这里开始往下就进行移除该元素之后的操作，也就是把指向哪个节点搞定。
    if (prev == null) {
        // 说明移除的节点是头节点，则 first 头节点应该指向下一个节点
        first = next;
    } else {
        // 不是头节点，prev.next=next：有 1、2、3，将 1.next指向 3
        prev.next = next;
        // 然后解除 x 节点的前指向。
        x.prev = null;
    }

    if (next == null) {
        // 说明移除的节点是尾节点
        last = prev;
    } else {
        // 不是尾节点，有 1、2、3，将 3.prev 指向 1. 然后将 2.next=解除指向。
        next.prev = prev;
        x.next = null;
    }

    // x 的前后指向都为 null 了，也把 item 为 null，让 GC 回收它
    x.item = null;
    size--; // 移除一个节点，size自减
    modCount++;
    return element; // 由于一开始已经保存了 x 的值到 element，所以返回。
}

get(index)

get(index) 查询元素的方法

/**
    * Returns the element at the specified position in this list.
    *
    * @param index index of the element to return
    * @return the element at the specified position in this list
    * @throws IndexOutOfBoundsException {@inheritDoc}
*/
// 这里没有什么，重点还是在 node(index) 中
public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}

node(index)

/**
* Returns the (non-null) Node at the specified element index.
*/
// 这里查询使用的是先从中间分一半查找
Node<E> node(int index) {
    // assert isElementIndex(index);
    // "<<":*2 的几次方 「>>」:/2 的几次方，例如：size<<1：size*2 的 1 次方，
    // 这个 if 中就是查询前半部分
    if (index < (size >> 1)) {  // index < 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;
    }
}

indexOf(Object o)

// 这个很简单，就是通过实体元素来查找到该元素在链表中的位置。跟 remove 中的代码类似，只是返回类型不一样。
public int indexOf(Object o) {
    int index = 0;
    if (o == null) {
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null)
                return index;
            index++;
        }
    } else {
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item))
                return index;
            index++;
        }
    }
    return -1;
}

LinkedList的迭代器

在 LinkedList 中除了有一个 Node 的内部类外，应该还能看到另外两个内部类，那就是 ListItr，还有一个是 DescendingIterator。

ListItr 内部类

private class ListItr implements ListIterator<E> {
}

看一下他的继承结构，发现只继承了一个 ListIterator，到 ListIterator 中一看：

看到方法名之后，就发现不止有向后迭代的方法，还有向前迭代的方法，所以我们就知道了这个 ListItr 这个内部类干嘛用的了，就是能让 LinkedList 不光能像后迭代，也能向前迭代。

看一下 ListItr 中的方法，可以发现，在迭代的过程中，还能移除、修改、添加值得操作。

DescendingIterator 内部类

private class DescendingIterator implements Iterator<E> {
    // 看一下这个类，还是调用的 ListItr，作用是封装一下 Itr 中几个方法，让使用者以正常的思维去写代码，例如，在从后往前遍历的时候，也是跟从前往后遍历一样，使用 next 等操作，而不用使用特殊的 previous
    private final ListItr itr = new ListItr(size());
    public boolean hasNext() {
        return itr.hasPrevious();
    }
    public E next() {
        return itr.previous();
    }
    public void remove() {
        itr.remove();
    }
}

总结

1. LinkedList 本质上是一个双向链表，通过一个 Node 内部类实现的这种链表结构
2. 能存储 null 值
3. 跟 ArrayList 相比较，就真正的知道了，LinkedList 在删除和增加等操作上性能好，而 ArrayList 在查询的性能上好
4. 从源码中看，它不存在容量不足的情况
5. LinkedList 不光能够向前迭代，还能像后迭代，并且在迭代的过程中，可以修改值、添加值、还能移除值
6. LinkedList 不光能当链表，还能当队列使用，这个就是因为实现了 Deque 接口