链表和LinkedList源码分析

本文需要你具备一些简单的Java知识，主要是在LinkedList这个集合框架有一定的使用经验，特别提醒，如果你看过这篇的前一篇关于ArrayList的源码分析会更好理解。如果你没有太多经验，可以查看该网站之前有关于集合框架的文章中LinkedList的内容，本文JDK版本为1.8

链表

什么是链表

链表用官方的回答就是：

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。

看不懂也没关系：

藏宝图

想象一下，我们去寻宝，是不是只能跟着藏宝图上的记号去挖宝藏，而且说不定挖出来的是另一张藏宝图，然后我们又跟着藏宝图再一次去寻找宝藏，这样反复以往最后终于挖到了宝藏。而这就是链表遍历其中每个节点的过程。总的来说，链表的每个节点在物理层面是不连续的，不像数组那样0号元素时候1号元素的后一个地址。链表的每个节点都是单独的个体，在每个节点中存放着指向下一个节点的地址。也就是说我们只有找到这个节点才知道下一个节点在哪里。

链表在内存中的储存方式

链表

链表在内存中存储就不像数组那样有规律了，而是随便存哪里都ok，因为在当前节点中总是有指向下一个节点的地址。

链表的优点和缺点

优点

  • 链表不需要提前定义数据长度，也就不太容易产生内存碎片。
  • 链表中新增、删除一个数据很快，因为不需要移动其他数据，只需要把指向下一个节点的地址换了就行。

缺点

  • 不支持随机访问，除了在首尾等一些特殊的节点以后，你可能需要遍历整个链表才知道数据在哪里。

LinkedList源码分析

LinkedList运行总览

LinkedList的源码没有ArrayList那么复杂，主要是对对应的节点进行操作，新增就是new一个对象，修改上下级的地址。删除就是把一个对象赋null，然后修改前后节点的地址。不过因为LinkedList实现了很多接口，但其实很多方法的原理都是相似的。

LinkedList类基本属性和构造器

LinkedList类继承AbstractSequentialList，实现了以下几个接口。

  • List 能像数组一样通过索引得到某个数据
  • Deque实现该接口以便实现一些队列的特性，先进先出。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
    
    //老生常谈的东西，这个容器的大小
    transient int size = 0;

    /**
     * Pointer to first node.
     * Invariant: (first == null && last == null) ||
     *            (first.prev == null && first.item != null)
     * 类中保存的首节点的类
     */
    transient Node<E> first;

    /**
     * Pointer to last node.
     * Invariant: (first == null && last == null) ||
     *            (last.next == null && last.item != null)
     * 类中保存的尾节点的类
     */
    transient Node<E> last;

    /**
     * Constructs an empty list.
     * 空的构造器
     */
    public LinkedList() {
    }

    /**
     * Constructs a list containing the elements of the specified
     * collection, in the order they are returned by the collection's
     * iterator.
     * 支持通过其他集合框架来创建一个链表
     *
     * @param  c the collection whose elements are to be placed into this list
     * @throws NullPointerException if the specified collection is null
     */
    public LinkedList(Collection<? extends E> c) {
        this();
        addAll(c);
    }

     /**
     * 私有内部类，描述了链表中节点的构造，存着数据和前后节点的地址，然后有一个全参构造器
     */
    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;
        }
    }

好像没有啥好讲的，基本信息就是这些。构造器也没有什么特别的，只是调用了本类的方法而已。

新增方法

add()方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
/**
 * Appends the specified element to the end of this list.
 * 将指定的元素附加到此列表的末尾。这个方法没什么好讲的，就是调用本类中的linkLast。
 * <p>This method is equivalent to {@link #addLast}.
 *
 * @param e element to be appended to this list
 * @return {@code true} (as specified by {@link Collection#add})
 */
public boolean add(E e) {
    linkLast(e);
    return true;
}

/**
 * Inserts the specified element at the specified position in this list.
 * Shifts the element currently at that position (if any) and any
 * subsequent elements to the right (adds one to their indices).
 *
 *在此列表中的指定位置插入指定元素。 
 *将当前在该位置的元素（如果有）和任何后续元素向右移动（向它们的索引添加一个）。
 * @param index index at which the specified element is to be inserted index 要插入指定元素的索引
 * @param element element to be inserted 要插入的元素元素
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
public void add(int index, E element) {
    //校验index是否在范围内
    checkPositionIndex(index);

    //如果index==size，说明是在末尾插入，直接调用插入最后那个方法就行
    if (index == size)
        linkLast(element);
    else
        //否则就是在中间插入，首先通过node拿到节点，在这个节点前插入元素
        linkBefore(element, node(index));
}

/**
 * Returns the (non-null) Node at the specified element index.
 * 返回指定元素索引处的（非空）节点。
 */
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;
    }
}

/**
 * Inserts element e before non-null Node succ.
 * 在非空节点 succ 之前插入元素 e
 */
void linkBefore(E e, Node<E> succ) {
    // assert succ != null;
    final Node<E> pred = succ.prev;
    final Node<E> newNode = new Node<>(pred, e, succ);
    succ.prev = newNode;
    //如果前置节点地址为空，说明是要插入首节点
    if (pred == null)
        first = newNode;
    else
        pred.next = newNode;
    size++;
    modCount++;
}

/**
 * Links e as last element.链接 e 作为最后一个元素。
 */
void linkLast(E e) {
    final Node<E> l = last;
    //新建一个节点
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    //如果l是空，那么说明该链表是空的，就把新建的节点作为第一个节点
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    //增加容量
    size++;
    //增加程序计数器，这个值和快速遍历有关（在迭代器中调用过），这里不需要管。
    modCount++;
}

add()的方法很简单，主要围绕着linkBefore(E e, Node<E> succ)和linkLast(E e)两个方法，无非就是判断是应该在末尾增加节点呢？还是应该在某个节点之前增加节点。

下面看看addAll()的方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
      /**
    * Appends all of the elements in the specified collection to the end of
    * this list, in the order that they are returned by the specified
    * collection's iterator.  The behavior of this operation is undefined if
    * the specified collection is modified while the operation is in
    * progress.  (Note that this will occur if the specified collection is
    * this list, and it's nonempty.)
    *
    * @param c collection containing elements to be added to this list
    * @return {@code true} if this list changed as a result of the call
    * @throws NullPointerException if the specified collection is null
    */
   public boolean addAll(Collection<? extends E> c) {
       return addAll(size, c);
   }


/**
    * Inserts all of the elements in the specified collection into this
    * list, starting at the specified position.  Shifts the element
    * currently at that position (if any) and any subsequent elements to
    * the right (increases their indices).  The new elements will appear
    * in the list in the order that they are returned by the
    * specified collection's iterator.
    *
    *将指定集合中的所有元素插入此列表，从指定位置开始。
    *将当前在该位置的元素（如果有）和任何后续元素向右移动（增加它们的索引）。
    *新元素将按照指定集合的迭代器返回的顺序出现在列表中。
    *
    * @param index index at which to insert the first element
    *              from the specified collection 从指定集合插入第一个元素的索引
    * @param c collection containing elements to be added to this list 包含要添加到此列表的元素的集合
    * @return {@code true} if this list changed as a result of the call 如果此列表因调用而更改
    * @throws IndexOutOfBoundsException {@inheritDoc}
    * @throws NullPointerException if the specified collection is null
    */
   public boolean addAll(int index, Collection<? extends E> c) {
       //判断是否在链表范围内
       checkPositionIndex(index);

       //调用集合框架的接口把集合返回为数组
       Object[] a = c.toArray();
       int numNew = a.length;
       //如果这个集合为空就返回false
       if (numNew == 0)
           return false;

       //定义两个node类型的
       Node<E> pred, succ;
       //如果index==size，说明是在尾部插入一个数组，那么第一个元素的前置位置等于尾节点
       if (index == size) {
           succ = null;
           pred = last;
           //否则，就找到索引的那个节点，把该节点的节点设置为后置节点
       } else {
           succ = node(index);
           pred = succ.prev;
       }

       //遍历数据，插入数据
       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为当前被遍历的节点，以便后面遍历的节点能连上
           pred = newNode;
       }

       //如果插入位置在尾部，则重置尾部节点的位置
       if (succ == null) {
           last = pred;
           //就把之前的链表连接起来
       } else {
           pred.next = succ;
           succ.prev = pred;
       }

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

主要addAll()还是看下面那个方法。这个方法总共做了5件事情：

  • 检查是否在范围内
  • 获得对象数组
  • 通过各种判断来确定插入点的前置节点和后置节点
  • 循环插入数据
  • 更新大小和程序计数器

添加元素到头或者尾

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
/**
 * Inserts the specified element at the beginning of this list.
 * 在此列表的开头插入指定的元素。
 * @param e the element to add
 */
public void addFirst(E e) {
    linkFirst(e);
}

/**
 * Links e as first element.
 * 链接 e 作为第一个元素。
 */
private void linkFirst(E e) {
    //获得首位节点
    final Node<E> f = first;
    //新建一个节点，该节点没有前置节点
    final Node<E> newNode = new Node<>(null, e, f);
    first = newNode;
    //如果首位节点为空，说明链表为空，则把尾节点也指向这个节点
    if (f == null)
        last = newNode;
    //把曾经的首位节点的前置节点链接到新建的节点
    else
        f.prev = newNode;
    size++;
    modCount++;
}

/**
 * Appends the specified element to the end of this list.
 *
 *将指定的元素附加到此列表的末尾。
 * <p>This method is equivalent to {@link #add}.
 *
 * @param e the element to add
 */
public void addLast(E e) {
    linkLast(e);
}

/**
 * Links e as last element.
 * 链接 e 作为最后一个元素。该方法也是类似的道理
 */
void linkLast(E e) {
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    size++;
    modCount++;
}

这里的添加方法逻辑还是很明显的也比较简单。

索引

主要分从头开始查找和从尾开始查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
/**
 * Returns the index of the first occurrence of the specified element
 * in this list, or -1 if this list does not contain the element.
 * More formally, returns the lowest index {@code i} such that
 * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>,
 * or -1 if there is no such index.
 *
 * 返回此列表中指定元素第一次出现的索引，如果此列表不包含该元素，则返回 -1。更正式地说，返回最低索引
 *{@code i} 使得 <tt>(o==null&nbsp ;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>，如果没有这样的索引，则为 -1。
 * @param o element to search for
 * @return the index of the first occurrence of the specified element in
 *         this list, or -1 if this list does not contain the element
 */
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;
}

/**
 * Returns the index of the last occurrence of the specified element
 * in this list, or -1 if this list does not contain the element.
 * More formally, returns the highest index {@code i} such that
 * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>,
 * or -1 if there is no such index.
 *
 * @param o element to search for
 * @return the index of the last occurrence of the specified element in
 *         this list, or -1 if this list does not contain the element
 */
public int lastIndexOf(Object o) {
    int index = size;
    if (o == null) {
        for (Node<E> x = last; x != null; x = x.prev) {
            index--;
            if (x.item == null)
                return index;
        }
    } else {
        for (Node<E> x = last; x != null; x = x.prev) {
            index--;
            if (o.equals(x.item))
                return index;
        }
    }
    return -1;
}

逻辑比较简单，就是遍历所有，查看是否有与之匹配的对象。

删除方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
/**
 * 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
 */
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;
}

/**
 * Removes the element at the specified position in this list.  Shifts any
 * subsequent elements to the left (subtracts one from their indices).
 * Returns the element that was removed from the list.
 *
 * 删除此列表中指定位置的元素。 将任何后续元素向左移动（从它们的索引中减去一个）。返回从列表中删除的元素。
 * @param index the index of the element to be removed
 * @return the element previously at the specified position
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
public E remove(int index) {
    checkElementIndex(index);
    return unlink(node(index));
}

/**
 * Unlinks non-null node x.
 * 取消链接非空节点 x。
 */
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;

    if (prev == null) {
        first = next;
    } else {
        prev.next = next;
        x.prev = null;
    }

    if (next == null) {
        last = prev;
    } else {
        next.prev = prev;
        x.next = null;
    }

    x.item = null;
    size--;
    modCount++;
    return element;
}

删除方法也好理解，就是取消这个节点的链接，然后把之前的前后节点链接到一起就行。

源码分析
集合框架

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！