Java集合之LinkedList类源码剖析

LinkedList类源码剖析

一、LinkedList类的简介

LinkedList类是List和Deque接口的双向链表实现，实现所有可选列表操作，并允许所有元素(包括null)。所有操作的执行都与双向链表的预期相同。对列表进行索引的操作将从开头或结尾遍历列表，以更接近指定索引的为准。LinkedList是一个基于双向链表实现的集合类，经常被拿来和ArrayList做比较，除了支持快速随机访问和自动扩容机制外(LinkedList底层采用双向链表，不需要预分配存储空间)，LinkedList与ArrayList的功能特性基本一致，仅仅多了一些双端队列的操作。

不过，我们在项目中一般是不会使用到LinkedList的，需要用到LinkedList的场景几乎都可以使用ArrayList来代替，并且性能通常会更好！另外，不要下意识地认为LinkedList作为链表就最适合元素增删的场景，LinkedList仅仅在头尾插入或者删除元素的时候时间复杂度近似O(1)，其他情况增删元素的平均时间复杂度都是O(n)。

LinkedList插入和删除元素的时间复杂度？

  • 头部插入/删除：只需要修改头结点的指针即可完成插入/删除操作，因此时间复杂度为O(1)。

  • 尾部插入/删除：只需要修改尾结点的指针即可完成插入/删除操作，因此时间复杂度为O(1)。

  • 指定位置插入/删除：需要先移动到指定位置，再修改指定节点的指针完成插入/删除，因此需要移动平均n/2个元素，时间复杂度为O(n)。

LinkedList为什么不能实现RandomAccess接口？

RandomAccess是一个标记接口，用来表明实现该接口的类支持随机访问（即可以通过索引快速访问元素）。由于LinkedList底层数据结构是链表，内存地址不连续，只能通过指针来定位，不支持随机快速访问，所以不能实现RandomAccess接口。

LinkedList 类图

1
2
3
4
5
6
public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
    ...
}

LinkedList继承了AbstractSequentialList，而AbstractSequentialList又继承于AbstractList。阅读过ArrayList的源码我们就知道，ArrayList同样继承了AbstractList，所以LinkedList会有大部分方法和ArrayList相似。

LinkedList实现了以下接口：

  • List:表明它是一个列表，支持添加、删除、查找等操作，并且可以通过下标进行访问。
  • Deque:继承自Queue接口，具有双端队列的特性，支持从两端插入和删除元素，方便实现栈和队列等数据结构。
  • Cloneable:表明它具有拷贝能力，可以进行深拷贝或浅拷贝操作。
  • Serializable:表明它可以进行序列化操作，也就是可以将对象转换为字节流进行持久化存储或网络传输，非常方便。

LinkedList中的元素是通过Node定义的：

1
2
3
4
5
6
7
8
9
10
11
12
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;
    }
}

二、LinkedList类的字段

1
2
3
4
5
6
// 元素数量
transient int size = 0;
// 首节点
transient Node<E> first;
// 尾节点
transient Node<E> last;

LinkedList类的字段非常简介明朗，其中size记录了存储的元素个数，first和last记录了底层双向链表的首尾节点。

三、LinkedList类的构造函数

LinkedList中有一个无参构造函数和一个有参构造函数。其中有参构造函数通过addAll函数将集合中的元素都一一添加到链表末尾。

1
2
3
4
5
6
7
8
9
// 创建一个空的链表对象
public LinkedList() {
}

// 接收一个集合类型作为参数，会创建一个与传入集合相同元素的链表对象
public LinkedList(Collection<? extends E> c) {
    this();
    addAll(c);
}

四、LinkedList类的插入操作

LinkedList除了实现了List接口相关方法，还实现了Deque接口的很多方法，所以我们有很多种方式插入元素。我们这里以List接口中相关的插入方法为例进行源码讲解，对应的是add()方法。

add()方法有两个版本：

  • add(E e):用于在LinkedList的尾部插入元素，即将新元素作为链表的最后一个元素，时间复杂度为O(1)。
  • add(int index, E element):用于在指定位置插入元素。这种插入方式需要先移动到指定位置，再修改指定节点的指针完成插入/删除，因此需要移动平均n/2个元素，时间复杂度为O(n)。

此外，作为双向链表，LinkedList还支持两端的元素插入操作，即addFirst和addLast。

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
// 在链表尾部插入元素
public boolean add(E e) {
    linkLast(e);
    return true;
}

// 在链表指定位置插入元素
public void add(int index, E element) {
    // 下标越界检查，必须满足0<=index<=size
    checkPositionIndex(index);

    // 判断 index 是不是链表尾部位置
    if (index == size)
        // 如果是就直接调用 linkLast 方法将元素节点插入链表尾部即可
        linkLast(element);
    else
        // 如果不是则调用 linkBefore 方法将其插入指定元素之前
        linkBefore(element, node(index));
}

// 把指定元素插入链表的头部
public void addFirst(E e) {
    linkFirst(e);
}

// 把指定元素插入链表的尾部
public void addLast(E e) {
    linkLast(e);
}

// 将元素节点插入到链表头部
private void linkFirst(E e) {
    // 将第一个元素赋值（引用传递）给节点 f
    final Node<E> f = first;
    // 创建节点，并指定节点前驱为空，后继引用为链表头节点 first
    final Node<E> newNode = new Node<>(null, e, f);
    // 将 first 节点指向新节点
    first = newNode;
    // 判断头节点是否为空
    // 如果 f 是 null 意味着这是第一次添加元素
    if (f == null)
        // 如果是第一次添加，将last赋值为新节点，此时链表只有一个元素
        last = newNode;
    else
        // 如果不是第一次添加，将新节点赋值给f（添加前的第一个元素）的prev
        f.prev = newNode;
    size++;
    modCount++;
}

// 将元素节点插入到链表尾部
void linkLast(E e) {
    // 将最后一个元素赋值（引用传递）给节点l
    final Node<E> l = last;
    // 创建节点，并指定节点前驱为链表尾节点 last，后继引用为空
    final Node<E> newNode = new Node<>(l, e, null);
    // 将 last 引用指向新节点
    last = newNode;
    // 判断尾节点是否为空
    // 如果 l 是 null 意味着这是第一次添加元素
    if (l == null)
        // 如果是第一次添加，将first赋值为新节点，此时链表只有一个元素
        first = newNode;
    else
        // 如果不是第一次添加，将新节点赋值给l（添加前的最后一个元素）的next
        l.next = newNode;
    size++;
    modCount++;
}

// 在指定元素之前插入元素
void linkBefore(E e, Node<E> succ) {
    // assert succ != null;断言 succ不为 null
    // 定义一个节点元素保存 succ 的 prev 引用，也就是它的前一节点信息
    final Node<E> pred = succ.prev;
    // 初始化节点，并指明前驱和后继节点
    final Node<E> newNode = new Node<>(pred, e, succ);
    // 将 succ 节点前驱引用 prev 指向新节点
    succ.prev = newNode;
    // 判断前驱节点是否为空，为空表示 succ 是头节点
    if (pred == null)
        first = newNode;
    else
        // succ 节点前驱的后继引用指向新节点
        pred.next = newNode;
    size++;
    modCount++;
}

如果大家细心，前面讨论LinkedList类的构造函数时提到了一个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
public boolean addAll(Collection<? extends E> c) {
    // 在链表末尾附加集合列表，指定索引参数为size
    return addAll(size, c);
}

public boolean addAll(int index, Collection<? extends E> c) {
    // 下标越界检查
    checkPositionIndex(index);
    // 目标集合的对象列表
    Object[] a = c.toArray();
    // 添加元素的个数
    int numNew = a.length;
    // 列表为空列表
    if (numNew == 0)
        return false;
    Node<E> pred, succ;
    if (index == size) 
    {
        // 末尾插入，后继节点为null，前驱节点为last
        succ = null;
        pred = last;
    } else {
        // 正常插入，后继节点为指定位置的节点，前驱节点为前一个节点
        succ = node(index);
        pred = succ.prev;
    }
    for (Object o : a) {
        @SuppressWarnings("unchecked") E e = (E) o;
        // 创建一个新节点，前驱节点是pred，后继节点是null，下次循环会补充后继节点
        Node<E> newNode = new Node<>(pred, e, null);
        // 头部插入
        if (pred == null)
            // 修改fist的新指向
            first = newNode;
        else
            // 前驱节点的后继指向新创建的节点
            pred.next = newNode;
        // 前驱节点后移一位
        pred = newNode;
    }
    // 末尾插入
    if (succ == null) {
        // 修改last的新指向
        last = pred;
    } else {
        // 此时pred是最后一个插入的节点
        // 完成最后一个插入节点与后继节点的关系对接
        pred.next = succ;
        succ.prev = pred;
    }
    size += numNew;
    modCount++;
    return true;
}

五、LinkedList类的获取操作

LinkedList获取元素相关的方法一共有3个：

  1. getFirst()：获取链表的第一个元素。
  2. getLast()：获取链表的最后一个元素。
  3. get(int index)：获取链表指定位置的元素。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 获取链表的第一个元素
public E getFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return f.item;
}

// 获取链表的最后一个元素
public E getLast() {
    final Node<E> l = last;
    if (l == null)
        throw new NoSuchElementException();
    return l.item;
}

// 获取链表指定位置的元素
public E get(int index) {
  // 下标越界检查，如果越界就抛异常
  checkElementIndex(index);
  // 返回链表中对应下标的元素
  return node(index).item;
}

这里的核心在于node(int index)这个方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 返回指定下标的非空节点
Node<E> node(int index) {
    // 断言下标未越界
    // assert isElementIndex(index);
    // 如果index小于size的二分之一  从前开始查找（向后查找）  反之向前查找
    if (index < (size >> 1)) {
        Node<E> x = first;
        // 遍历，循环向后查找，直至 i == index
        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;
    }
}

get(int index)或remove(int index)等方法内部都调用了该方法来获取对应的节点。

从这个方法的源码可以看出，该方法通过比较索引值与链表size的一半大小来确定从链表头还是尾开始遍历。如果索引值小于size的一半，就从链表头开始遍历，反之从链表尾开始遍历。这样可以在较短的时间内找到目标节点，充分利用了双向链表的特性来提高效率。

六、LinkedList类的删除操作

LinkedList删除元素相关的方法一共有5个：

  1. removeFirst()：删除并返回链表的第一个元素。
  2. removeLast()：删除并返回链表的最后一个元素。
  3. remove(E e)：删除链表中首次出现的指定元素，如果不存在该元素则返回false。
  4. remove(int index)：删除指定索引处的元素，并返回该元素的值。
  5. void clear()：移除此链表中的所有元素。
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
// 删除并返回链表的第一个元素
public E removeFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return unlinkFirst(f);
}

// 删除并返回链表的最后一个元素
public E removeLast() {
    final Node<E> l = last;
    if (l == null)
        throw new NoSuchElementException();
    return unlinkLast(l);
}

// 删除链表中首次出现的指定元素，如果不存在该元素则返回 fals
public boolean remove(Object o) {
    // 如果指定元素为 null，根据 == 运算符比较遍历链表
    if (o == null) {
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null) {
                unlink(x);
                return true;
            }
        }
    } else {
        // 如果指定元素不为 null，根据 equals 方法比较遍历链表
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item)) {
                unlink(x);
                return true;
            }
        }
    }
    return false;
}

// 删除链表指定位置的元素
public E remove(int index) {
    // 下标越界检查，如果越界就抛异常
    checkElementIndex(index);
    return unlink(node(index));
}

这里的核心在于unlink(Node<E> x)这个方法：

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
E unlink(Node<E> x) {
    // 断言 x 不为 null
    // 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 { // 如果前一个节点不为空
        // 将前一个节点的 next 指针指向当前节点的下一个节点
        prev.next = next;
        // 将当前节点的 prev 指针置为 null，，方便 GC 回收
        x.prev = null;
    }

    // 如果下一个节点为空，则说明当前节点是尾节点
    if (next == null) {
        // 直接让链表尾指向当前节点的前一个节点
        last = prev;
    } else { // 如果下一个节点不为空
        // 将下一个节点的 prev 指针指向当前节点的前一个节点
        next.prev = prev;
        // 将当前节点的 next 指针置为 null，方便 GC 回收
        x.next = null;
    }

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

unlink()方法的逻辑如下：

  1. 首先获取待删除节点x的前驱和后继节点；
  2. 判断待删除节点是否为头节点或尾节点：
    • 如果x是头节点，则将first指向x的后继节点next
    • 如果x是尾节点，则将last指向x的前驱节点 prev
    • 如果x不是头节点也不是尾节点，执行下一步操作
  3. 将待删除节点x的前驱的后继指向待删除节点的后继next，断开x和x.prev之间的链接；
  4. 将待删除节点x的后继的前驱指向待删除节点的前驱prev，断开x和x.next之间的链接；
  5. 将待删除节点x的元素置空，修改链表长度。

unlink 方法逻辑

除了unlink方法外，还有unlinkFirst和unlinkLast两个方法，相对比较简单，这三个方法组成了双向链表中最底层的删除操作：

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
private E unlinkFirst(Node<E> f) {
    // assert f == first && f != null;
    // 头节点的元素值
    final E element = f.item;
    // 头节点的后继节点
    final Node<E> next = f.next;
    f.item = null; // help GC
    f.next = null; // help GC
    // 头节点后移
    first = next;
    // 维护尾节点的正确位置
    if (next == null)
        last = null;
    else
        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; // help GC
    l.prev = null; // help GC
    // 尾节点前移
    last = prev;
    // 维护头节点的正确位置
    if (prev == null)
        first = null;
    else
        prev.next = null;
    size--;
    modCount++;
    return element;
}

七、LinkedList类的遍历操作

推荐使用for-each循环来遍历LinkedList中的元素，for-each循环最终会转换成迭代器形式。LinkedList的遍历的核心就是它的迭代器的实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 双向迭代器
private class ListItr implements ListIterator<E> {
    // 表示上一次调用 next() 或 previous() 方法时经过的节点；
    private Node<E> lastReturned;
    // 表示下一个要遍历的节点；
    private Node<E> next;
    // 表示下一个要遍历的节点的下标；
    private int nextIndex;
    // 表示当前遍历期望的修改计数值，用于和 LinkedList 的 modCount 比较，判断链表是否被其他线程修改过。
    private int expectedModCount = modCount;
    // 构造方法，指定了起始遍历位置
    ListItr(int index) {
        // assert isPositionIndex(index);
        next = (index == size) ? null : node(index);
        nextIndex = index;
    }
}

下面我们对迭代器ListItr中的核心方法进行详细介绍。

我们先来看下从头到尾方向的迭代：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 判断还有没有下一个节点
public boolean hasNext() {
    // 判断下一个节点的下标是否小于链表的大小，如果是则表示还有下一个元素可以遍历
    return nextIndex < size;
}
// 获取下一个节点
public E next() {
    // 检查在迭代过程中链表是否被修改过
    checkForComodification();
    // 判断是否还有下一个节点可以遍历，如果没有则抛出 NoSuchElementException 异常
    if (!hasNext())
        throw new NoSuchElementException();
    // 将 lastReturned 指向当前节点
    lastReturned = next;
    // 将 next 指向下一个节点
    next = next.next;
    nextIndex++;
    return lastReturned.item;
}

再来看一下从尾到头方向的迭代：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 判断是否还有前一个节点
public boolean hasPrevious() {
    return nextIndex > 0;
}

// 获取前一个节点
public E previous() {
    // 检查是否在迭代过程中链表被修改
    checkForComodification();
    // 如果没有前一个节点，则抛出异常
    if (!hasPrevious())
        throw new NoSuchElementException();
    // 将 lastReturned 和 next 指针指向上一个节点
    lastReturned = next = (next == null) ? last : next.prev;
    nextIndex--;
    return lastReturned.item;
}

迭代器对应的移除元素的方法如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 从列表中删除上次被返回的元素
public void remove() {
    // 检查是否在迭代过程中链表被修改
    checkForComodification();
    // 如果上次返回的节点为空，则抛出异常
    if (lastReturned == null)
        throw new IllegalStateException();

    // 获取当前节点的下一个节点
    Node<E> lastNext = lastReturned.next;
    // 从链表中删除上次返回的节点
    unlink(lastReturned);
    // next == lastReturned意味着之前采用向前遍历，next后移一位（因为next表示当前节点），nextIndex不变
    if (next == lastReturned)
        next = lastNext;
    // next != lastReturned意味着之前采用向后遍历，next不动，nextIndex减一(因为前面删除了一个节点)
    else
        nextIndex--;
    // 将上次返回的节点引用置为 null，方便 GC 回收
    lastReturned = null;
    // 列表迭代器中保存的expectedModCount递增
    expectedModCount++;
}

八、LinkedList类的队列操作对比

首先查看LinkedList的继承关系可知，LinkedList实现了双端队列接口Deque，而双端队列接口Deque又继承了队列接口Queue，因此LinkedList既可以作为一个普通队列使用，也可以作为双端队列使用。

Queue 是单端队列，只能从一端插入元素，另一端删除元素，实现上一般遵循 先进先出（FIFO） 规则。

Queue 扩展了 Collection 的接口，根据 因为容量问题而导致操作失败后处理方式的不同 可以分为两类方法: 一种在操作失败后会抛出异常，另一种则会返回特殊值。

Queue 接口 抛出异常 返回特殊值
插入队尾 add(E e) offer(E e)
删除队首 remove() poll()
查询队首元素 element() peek()

我们根据源码先查看抛出异常的三个队列方法：add、remove、element

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
public boolean add(E e) {
    /**
     * Links e as last element.
     */
    linkLast(e);
    return true;
}

public E remove() {
    /**
     * Retrieves and removes the head (first element) of this list.
     *
     * @return the head of this list
     * @throws NoSuchElementException if this list is empty
     * @since 1.5
     */
    return removeFirst();
}

public E element() {
    /**
     * Returns the first element in this list.
     *
     * @return the first element in this list
     * @throws NoSuchElementException if this list is empty
     */
    return getFirst();
}

image-20231209161118933

队列的add方法不一定会抛出异常，这取决于具体队列的实现类，对于LinkedList来说不存在容量限制和元素值限制(允许null)，因此不会抛出任何异常。

然后，我们再查看返回特殊值的三个队列方法：offer、poll、peek

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
/**
 * Adds the specified element as the tail (last element) of this list.
 *
 * @param e the element to add
 * @return {@code true} (as specified by {@link Queue#offer})
 * @since 1.5
 */
public boolean offer(E e) {
    return add(e);
}

/**
 * Retrieves and removes the head (first element) of this list.
 *
 * @return the head of this list, or {@code null} if this list is empty
 * @since 1.5
 */
public E poll() {
    final Node<E> f = first;
    return (f == null) ? null : unlinkFirst(f);
}

/**
 * Retrieves, but does not remove, the head (first element) of this list.
 *
 * @return the head of this list, or {@code null} if this list is empty
 * @since 1.5
 */
public E peek() {
    final Node<E> f = first;
    return (f == null) ? null : f.item;
}

九、LinkedList类的双端队列操作

Deque 是双端队列，在队列的两端均可以插入或删除元素。

Deque 扩展了 Queue 的接口, 增加了在队首和队尾进行插入和删除的方法，同样根据失败后处理方式的不同分为两类：

Deque 接口 抛出异常 返回特殊值
插入队首 addFirst(E e) offerFirst(E e)
插入队尾 addLast(E e) offerLast(E e)
删除队首 removeFirst() pollFirst()
删除队尾 removeLast() pollLast()
查询队首元素 getFirst() peekFirst()
查询队尾元素 getLast() peekLast()

首先，我们还是先看看抛出异常的6个双端队列方法：

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
public void addFirst(E e) {
    linkFirst(e);
}

public void addLast(E e) {
    linkLast(e);
}

public E removeFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return unlinkFirst(f);
}

public E removeLast() {
    final Node<E> l = last;
    if (l == null)
        throw new NoSuchElementException();
    return unlinkLast(l);
}

public E getFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return f.item;
}

public E getLast() {
    final Node<E> l = last;
    if (l == null)
        throw new NoSuchElementException();
    return l.item;
}

然后，我们看看返回特殊值的6个双端队列方法：

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
public boolean offerFirst(E e) {
    addFirst(e);
    return true;
}

public boolean offerLast(E e) {
    addLast(e);
    return true;
}

public E pollFirst() {
    final Node<E> f = first;
    return (f == null) ? null : unlinkFirst(f);
}

public E pollLast() {
    final Node<E> l = last;
    return (l == null) ? null : unlinkLast(l);
}

public E peekFirst() {
    final Node<E> f = first;
    return (f == null) ? null : f.item;
}

public E peekLast() {
    final Node<E> l = last;
    return (l == null) ? null : l.item;
}

事实上，Deque 还提供有 push() 和 pop() 等其他方法，可用于模拟栈。

十、LinkedList类常用方法测试

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
// 创建 LinkedList 对象
LinkedList<String> list = new LinkedList<>();

// 添加元素到链表末尾
list.add("apple");
list.add("banana");
list.add("pear");
System.out.println("链表内容：" + list);

// 在指定位置插入元素
list.add(1, "orange");
System.out.println("链表内容：" + list);

// 获取指定位置的元素
String fruit = list.get(2);
System.out.println("索引为 2 的元素：" + fruit);

// 修改指定位置的元素
list.set(3, "grape");
System.out.println("链表内容：" + list);

// 删除指定位置的元素
list.remove(0);
System.out.println("链表内容：" + list);

// 删除第一个出现的指定元素
list.remove("banana");
System.out.println("链表内容：" + list);

// 获取链表的长度
int size = list.size();
System.out.println("链表长度：" + size);

// 清空链表
list.clear();
System.out.println("清空后的链表：" + list);

image-20230927200548697

参考文章：LinkedList源码分析