喵喵爱编程

这个屌丝很懒，什么也没留下！

热门标签

Java 集合框架：LinkedList 的介绍、使用、原理与源码解析_linkedlist java

作者：喵喵爱编程 | 2024-06-23 03:14:43

踩

linkedlist java

大家好，我是栗筝i，这篇文章是我的 “栗筝i 的 Java 技术栈” 专栏的第 014 篇文章，在 “栗筝i 的 Java 技术栈” 这个专栏中我会持续为大家更新 Java 技术相关全套技术栈内容。专栏的主要目标是已经有一定 Java 开发经验，并希望进一步完善自己对整个 Java 技术体系来充实自己的技术栈的同学。与此同时，本专栏的所有文章，也都会准备充足的代码示例和完善的知识点梳理，因此也十分适合零基础的小白和要准备工作面试的同学学习。当然，我也会在必要的时候进行相关技术深度的技术解读，相信即使是拥有多年 Java 开发经验的从业者和大佬们也会有所收获并找到乐趣。

–

Java 集合框架中包含了多种用于数据存储和操作的类，其中 LinkedList 是一个重要且常用的实现。LinkedList 作为一个双向链表，提供了高效的插入和删除操作，特别适用于频繁进行元素增删的场景。对于很多开发者而言，深入理解 LinkedList 的特性和工作原理是提高代码性能和优化数据处理逻辑的关键。本文将对 LinkedList 进行全面的介绍和解析，帮助读者掌握其使用方法、内部原理以及源码实现。

文章目录

1、LinkedList 概述

LinkedList 是 List 接口的一个实现，它是一个双向链表。与 ArrayList 相比，LinkedList 的元素在内存中不是连续存放的。每个元素（称为节点）都包含两部分数据：一部分是存储的数据，另一部分是指向前一个节点和后一个节点的链接（指针）。

LinkedList 的优点在于插入和删除元素时效率很高。因为链表的数据结构使得它只需要修改前后节点的指针即可，而不需要像 ArrayList 那样移动其他元素。因此，LinkedList 适合用在需要频繁执行添加和删除操作的场景。

然而，LinkedList 的随机访问效率不高，每次查找某个元素都需要从头开始遍历链表直到找到目标元素。这使得 LinkedList 在执行随机访问操作时速度较慢，不如 ArrayList。

在 Java 中，LinkedList 除了实现 List 接口外，还实现了 Deque 接口，这意味着它还可以被当作队列（Queue）、双端队列（Deque）使用，提供了更加丰富的方法，如 addFirst(), addLast(), removeFirst(), removeLast() 等。

LinkedList 也是非线程安全的。如果在多线程环境中使用，需要外部同步或者考虑使用 java.util.concurrent 包中的线程安全类，如 LinkedBlockingDeque 等。

总的来说，LinkedList 由于其结构的特点，适合于数据量不大但插入和删除操作频繁的场景，而不适合大量的随机访问操作。

2、LinkedList 的具体实现原理

2.1、LinkedList 底层的数据结构

LinkedList 是基于链表数据结构实现的，它包含一系列的节点（Node），每个节点包括三个部分：前一个节点的引用（previous），储存的元素（data），和下一个节点的引用（next）。这种数据结构支持高效的元素插入和删除操作。

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
    transient int size = 0;

    // 链表中元素的数量
    transient int size = 0;

    /**
     * 指向第一个节点的指针
     */
    transient Node<E> first;

    /**
     * 指向最后一个节点的指针
     */
    transient Node<E> last;

    /**
     * 构造一个空的链表
     */
    public LinkedList() {
    }

    /**
     * 构造一个包含指定集合元素的链表，这些元素按集合的迭代器返回的顺序排列。
     *
     * @param  c 要放入链表中的集合
     * @throws NullPointerException 如果指定的集合为 null
     */
    public LinkedList(Collection<? extends E> c) {
        this();
        // 将集合中的所有元素添加到链表中
        addAll(c);
    }
  
    // 省略其他方法和实现细节
  	...
  
  	/**
     * Node 是一个私有的静态内部类，用于表示 LinkedList 中的每个节点
     *
     * @param <E>
     */
    private static class Node<E> {
        // 节点存储的元素
        E item;
        // 指向下一个节点的引用
        Node<E> next;
        // 指向前一个节点的引用
        Node<E> prev;

        /**
         * 构造方法，创建一个新的节点
         *
         * @param prev    该节点的前一个节点
         * @param element 该节点存储的元素
         * @param next    该节点的后一个节点
         */
        Node(Node<E> prev, E element, Node<E> next) {
            // 设置节点存储的元素
            this.item = element;
            // 设置指向下一个节点的引用
            this.next = next;
            // 设置指向前一个节点的引用
            this.prev = prev;
        }
    }

    
    // 省略其他方法和实现细节
  	...
}
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

2.2、LinkedList 增删改查的实现

2.2.1、LinkedList 的插入

LinkedList 的插入的实现并不复杂，其插入式，主要会有两种场景，一种是在链表的末尾插入，另一种是在指定节点之前插入一个新节点，二者的实现都是通过创建一个新节点并更新其前驱和后继节点的引用，唯一的区别就是，linkBefore 是在指定节点之后插入该新节点，而 linkAfter 是在指定节点之后插入该新节点。

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
    // 省略其他方法和实现细节
  	...
  
    /**
     * 在链表末尾添加一个元素
     *
     * @param e 要添加的元素
     * @return 总是返回 true
     */
    @Override
    public boolean add(E e) {
      	// 在链表末尾链接一个新的节点
        linkLast(e);
        return true;
    }
  
    /**
     * 在链表末尾链接一个新的节点
     *
     * @param e 新节点存储的元素
     */
    void linkLast(E e) {
        // 保存当前链表的最后一个节点
        final Node<E> l = last;
        // 创建一个新的节点，前驱节点是当前最后一个节点，后继节点是 null
        final Node<E> newNode = new Node<>(l, e, null);
        // 将链表的最后一个节点更新为新节点
        last = newNode;
        if (l == null)
            // 如果链表之前是空的，即没有任何元素
            // 将新节点设置为链表的第一个节点
            first = newNode;
        else
            // 如果链表中已有元素
            // 将原最后一个节点的 next 指针指向新节点
            l.next = newNode;
      	// 链表大小增加 1
        size++;  
    }
  
    /**
     * 在指定索引处插入元素
     *
     * @param index 要插入元素的位置
     * @param element 要插入的元素
     */
    public void add(int index, E element) {
        checkPositionIndex(index);
        if (index == size)
            linkLast(element);
        else
            linkBefore(element, node(index));
    }
  
    /**
     * 在指定节点之前插入一个新节点
     *
     * @param e 新节点存储的元素
     * @param succ 指定的节点，新节点将插入在其之前
     */
    void linkBefore(E e, Node<E> succ) {
        // assert succ != null;  // 确保 succ 不为 null，确保在调用该方法前 succ 一定存在
        // 保存指定节点的前驱节点
        final Node<E> pred = succ.prev;
        // 创建一个新的节点，其前驱是 pred，后继是 succ
        final Node<E> newNode = new Node<>(pred, e, succ);
        // 将指定节点的前驱更新为新节点
        succ.prev = newNode;
        if (pred == null)
            // 如果 pred 为 null，说明 succ 是第一个节点
            // 将新节点设置为链表的第一个节点
            first = newNode;
        else
            // 如果 pred 不为 null，说明 succ 不是第一个节点
            // 将 pred 的后继节点更新为新节点
            pred.next = newNode;
        // 链表大小增加 1
        size++;
        // 修改计数器增加 1，用于快速失败机制
        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
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

此外，另一个十分值得注意的点是，add(int index, E element) 在调用指定节点之前插入一个新节点方法时，调用了 node(int index) 方法来返回指定索引处的节点。该方法可以看作是 LinkedList 的核心实现之一，除插入方法之外，LinkedList 在查询、删除、修改等方法除也需要调用当前方法：

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
    // 省略其他方法和实现细节
  	...
  
    /**
     * 返回指定索引处的节点。
     *
     * @param index 要获取节点的位置
     * @return 指定索引处的节点
     */
    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;
        }
    }

    // 省略其他方法和实现细节
  	...
}
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

2.2.2、LinkedList 的删除

LinkedList 的删除的实现同样十分简单，是使用 unlink 方法，即通过更新前驱和后继节点的引用，移除指定节点并返回其存储的元素实现的。

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
    // 省略其他方法和实现细节
  	...
  
    /**
     * 解除并移除指定节点。
     *
     * @param x 要移除的节点
     * @return 被移除节点存储的元素
     */
    E unlink(Node<E> x) {
        // assert x != null;  // 确保 x 不为 null

        // 保存节点中的元素
        final E element = x.item;
        // 保存节点的后继节点
        final Node<E> next = x.next;
        // 保存节点的前驱节点
        final Node<E> prev = x.prev;

        if (prev == null) {
            // 如果前驱节点为 null，说明 x 是第一个节点
            // 将链表的第一个节点更新为 x 的后继节点
            first = next;
        } else {
            // 如果前驱节点不为 null
            // 将前驱节点的后继更新为 x 的后继节点
            prev.next = next;
            // 将 x 的前驱设为 null，帮助垃圾回收
            x.prev = null;
        }

        if (next == null) {
            // 如果后继节点为 null，说明 x 是最后一个节点
            // 将链表的最后一个节点更新为 x 的前驱节点
            last = prev;
        } else {
            // 如果后继节点不为 null
            // 将后继节点的前驱更新为 x 的前驱节点
            next.prev = prev;
            // 将 x 的后继设为 null，帮助垃圾回收
            x.next = null;
        }

        // 将 x 中的元素设为 null，帮助垃圾回收
        x.item = null;
        // 链表大小减 1
        size--;
        // 修改计数器增加 1，用于快速失败机制
        modCount++;
        // 返回被移除节点中的元素
        return element;
    }
  
    /**
     * 移除指定索引处的元素。
     *
     * @param index 要移除元素的位置
     * @return 被移除的元素
     */
    public E remove(int index) {
        checkElementIndex(index);
        return unlink(node(index));
    }
  
    /**
     * 从链表中移除第一次出现的指定元素（如果存在）。
     * 如果列表不包含该元素，则不做改变。
     *
     * @param o 要移除的元素
     * @return 如果列表包含指定元素并移除成功则返回 true，否则返回 false
     */
    public boolean remove(Object o) {
        // 如果要移除的元素为 null
        if (o == null) { 
            for (Node<E> x = first; x != null; x = x.next) {
                // 从链表的第一个节点开始遍历
                if (x.item == null) {
                    // 如果当前节点的元素为 null
                    unlink(x);  
                    // 解除并移除当前节点
                    // 返回 true，表示移除成功
                    return true;  
                }
            }
        } else {  
            // 如果要移除的元素不为 null
            for (Node<E> x = first; x != null; x = x.next) {  
                // 从链表的第一个节点开始遍历
                // 如果当前节点的元素等于要移除的元素
                if (o.equals(x.item)) {
                    // 解除并移除当前节点
                    unlink(x);
                    // 返回 true，表示移除成功
                    return true;  
                }
            }
        }
        // 如果没有找到要移除的元素，返回 false
        return false;  
    }

    // 省略其他方法和实现细节
  	...
}
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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108

2.2.3、LinkedList 的修改

LinkedList 对于修改的则是通过找到原位置的 Node 并修改其 item 值实现的。

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
    // 省略其他方法和实现细节
  	...
  
    /**
     * 替换指定索引处的元素，并返回被替换的元素。
     *
     * @param index 要替换元素的位置
     * @param element 要设置的新元素
     * @return 被替换的旧元素
     * @throws IndexOutOfBoundsException 如果索引超出范围
     */
    public E set(int index, E element) {
        // 检查索引是否在范围内
        checkElementIndex(index);
        // 获取指定索引处的节点
        Node<E> x = node(index);
        // 保存当前节点的旧元素
        E oldVal = x.item;
        // 将节点的元素设置为新元素
        x.item = element;
        // 返回被替换的旧元素
        return oldVal;
    }
  
      	/**
         * 将迭代器返回的最后一个元素替换为指定的元素。
         *
         * @param e 要设置的新元素
         * @throws IllegalStateException 如果没有调用 next() 或 previous() 方法
         */
        public void set(E e) {
            if (lastReturned == null)
                // 如果 lastReturned 为 null，表示未调用 next() 或 previous()
                // 抛出非法状态异常
                throw new IllegalStateException();
            // 检查是否发生并发修改
            checkForComodification();
            // 将 lastReturned 节点的元素设置为新元素 e
            lastReturned.item = e;
        }

    // 省略其他方法和实现细节
  	...
}
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

2.2.4、LinkedList 的查询

LinkedList 的查询即获取指定索引处的元素。它的实现同前面的其他方法获取索引处元素一样，依赖 node(int index) 方法。

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
    // 省略其他方法和实现细节
  	...
  
    /**
     * 获取指定索引处的元素
     *
     * @param index 要获取元素的位置
     * @return 指定索引处的元素
     */
    public E get(int index) {
        checkElementIndex(index);
        return node(index).item;
    }
  
    /**
     * 返回指定索引处的节点。
     *
     * @param index 要获取节点的位置
     * @return 指定索引处的节点
     */
    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;
        }
    }

    // 省略其他方法和实现细节
  	...
}
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

2.3、LinkedList 对链表结构的实现

LinkedList 类实现了 Queue 接口，因此提供了队列相关的方法。这些方法允许 LinkedList 作为一个双端队列（Deque）使用，支持在队列的头部和尾部进行插入和删除操作。下面是对 LinkedList 中与 Queue 相关方法的概括说明：

offer(E e)：将指定的元素添加到队列的尾部并返回 true。实现：调用 linkLast(E e) 方法，将元素添加到链表的尾部；
poll()：获取并移除此队列的头部，如果队列为空，则返回 null。实现：调用 unlinkFirst(Node<E> f) 方法，移除并返回链表的第一个元素；
remove()：获取并移除此队列的头部，如果队列为空，则抛出 NoSuchElementException。实现：调用 unlinkFirst(Node<E> f) 方法，移除并返回链表的第一个元素。如果链表为空，抛出 NoSuchElementException；
peek()：获取但不移除此队列的头部；如果队列为空，则返回 null。实现：返回链表的第一个元素 first.item，如果链表为空返回 null。
element()：获取但不移除此队列的头部；如果队列为空，则抛出 NoSuchElementException。实现：返回链表的第一个元素 first.item，如果链表为空抛出 NoSuchElementException。

具体实现：

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
    // 省略其他方法和实现细节
  	...
      
    /**
     * 将指定的元素添加到队列的尾部。
     *
     * @param e 要添加的元素
     * @return 添加成功返回 true
     */
    public boolean offer(E e) {
        // 调用 add 方法，将元素添加到链表的尾部
        return add(e);
    }
  
    /**
     * 获取并移除此队列的头部，如果队列为空，则返回 null。
     *
     * @return 队列头部的元素，如果队列为空则返回 null
     */
    public E poll() {
        // 保存链表的第一个节点
        final Node<E> f = first;
        // 如果链表为空返回 null，否则移除并返回第一个元素
        return (f == null) ? null : unlinkFirst(f);
    }
  
    /**
     * 获取并移除此队列的头部，如果队列为空，则抛出 NoSuchElementException。
     *
     * @return 队列头部的元素
     * @throws NoSuchElementException 如果队列为空
     */
    public E remove() {
        // 保存链表的第一个节点
        final Node<E> f = first;
        // 如果链表为空，抛出 NoSuchElementException
        if (f == null)
            throw new NoSuchElementException();
        // 移除并返回第一个元素
        return unlinkFirst(f);
    }
  
    /**
     * 获取但不移除此队列的头部；如果队列为空，则返回 null。
     *
     * @return 队列头部的元素，如果队列为空则返回 null
     */
    public E peek() {
        // 保存链表的第一个节点
        final Node<E> f = first;
        // 返回第一个元素但不移除，如果链表为空返回 null
        return (f == null) ? null : f.item;
    }
  
    /**
     * 获取但不移除此队列的头部；如果队列为空，则抛出 NoSuchElementException。
     *
     * @return 队列头部的元素
     * @throws NoSuchElementException 如果队列为空
     */
    public E element() {
        return getFirst();
    }
  
    /**
     * 返回链表的第一个元素；如果链表为空，则抛出 NoSuchElementException。
     *
     * @return 链表的第一个元素
     * @throws NoSuchElementException 如果链表为空
     */
    public E getFirst() {
        // 保存链表的第一个节点
        final Node<E> f = first;
        // 如果链表为空，抛出 NoSuchElementException
        if (f == null)
            throw new NoSuchElementException();
        // 返回第一个元素
        return f.item;
    }

    // 省略其他方法和实现细节
  	...
}
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

内部辅助方法，unlinkFirst(Node<E> f)：移除并返回链表的第一个节点。实现：更新链表的头节点 first 为当前头节点 f 的下一个节点 f.next，并将旧头节点的前驱引用设为 null。

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
    // 省略其他方法和实现细节
  	...
      
    /**
     * 移除并返回链表的第一个节点。
     *
     * @param f 要移除的第一个节点
     * @return 被移除节点存储的元素
     */
    private E unlinkFirst(Node<E> f) {
        // 保存第一个节点的元素
        final E element = f.item;
        // 保存第一个节点的后继节点
        final Node<E> next = f.next;
        // 清空第一个节点的元素
        f.item = null;
        // 清空第一个节点的后继引用，帮助垃圾回收
        f.next = null;
        // 更新链表的头节点为原头节点的后继节点
        first = next;
        // 如果新的头节点为 null，说明链表现在为空
        if (next == null) {
            // 更新链表的尾节点为 null
            last = null;
        } else {
            // 将新的头节点的前驱引用设为 null
            next.prev = null;
        }
        // 链表大小减 1
        size--;
        // 修改计数器增加 1，用于快速失败机制
        modCount++;
        // 返回被移除的元素
        return 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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

3、LinkedList 相关知识点

3.1、关于 Queue 队列

队列（Queue）：也是一种操作受限的线性表，只允许在表的一端进行插入，而在表的另一端进行删除。向队列中插入元素称为入队或进队；删除元素称为出队或离队。

这和我们日常生活中的排队是一致的，最早排队的也是最早离队的。其操作的特性是先进先出（First In First Out, FIFO），故又称为先进先出的线性表。基本上，一个队列就是一个先入先出（FIFO）的数据结构

在Java 中 Queue 接口与 List、Set 同一级别，都是继承了 Collection 接口。LinkedList 实现了 Deque 接口。

3.2、关于 ArrayList 和 LinkedList 的区别

ArrayList 和 LinkedList 都是 List 接口的实现，但它们在内部数据结构和性能上有一些区别：

内部数据结构：ArrayList 是基于动态数组实现的，支持随机访问，按索引访问元素非常快，时间复杂度为 O(1)。LinkedList 是基于双向链表实现的，不支持高效的随机访问，按索引访问元素需要从头（或尾）开始遍历，时间复杂度为 O(n)。
插入和删除：ArrayList 的插入和删除操作需要进行数组元素的移动（除非插入和删除操作在列表末尾进行），所以插入和删除元素的时间复杂度为 O(n)。LinkedList 的插入和删除操作只需要改变节点的引用，所以在列表中间插入和删除元素的时间复杂度为 O(1)（前提是已经获取到了要插入位置的节点）。
内存占用：ArrayList 的内存占用相对较低，因为它只需要存储元素数据和数组的引用。LinkedList 的内存占用较高，因为它需要额外存储节点之间的引用。

总的来说，ArrayList 更适合随机访问场景，LinkedList 更适合插入和删除操作频繁的场景。

3.3、算法：翻转链表

假设链表为 1→2→3→∅，我们想要把它改成 ∅←1←2←3。

在遍历链表时，将当前节点的 next 指针改为指向前一个节点。由于节点没有引用其前一个节点，因此必须事先存储其前一个节点。在更改引用之前，还需要存储后一个节点。最后返回新的头引用。

class Solution {
    /**
     * 反转链表。
     *
     * @param head 链表的头节点
     * @return 反转后的链表的头节点
     */
    public ListNode reverseList(ListNode head) {
        // 初始化前一个节点为 null
        ListNode prev = null;
        // 初始化当前节点为头节点
        ListNode curr = head;
        // 遍历链表直到当前节点为 null
        while (curr != null) {
            // 保存当前节点的下一个节点
            ListNode next = curr.next;
            // 将当前节点的下一个节点指向前一个节点，完成反转
            curr.next = prev;
            // 将前一个节点更新为当前节点
            prev = curr;
            // 将当前节点更新为下一个节点
            curr = next;
        }
        // 返回反转后的链表头节点
        return prev;
    }
}
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

4、LinkedList 的使用（常用方法）

下面是对 LinkedList 的常用方法和 Collections 类中的一些涉及 LinkedList 的方法进行详细介绍：

4.1、LinkedList 的常用方法

add(E e)

功能：将元素添加到链表的末尾。
用例：

LinkedList<String> list = new LinkedList<>();
list.add("Apple");
1
2

add(int index, E element)

功能：在指定位置插入元素。
用例：

LinkedList<String> list = new LinkedList<>();
list.add("Apple");
list.add("Banana");
list.add(1, "Orange"); // 将 "Orange" 插入在 "Banana" 前面
1
2
3
4

remove(Object o)

功能：删除链表中首次出现的指定元素。
用例：

LinkedList<String> list = new LinkedList<>();
list.add("Apple");
list.add("Banana");
list.remove("Apple");
1
2
3
4

remove(int index)

功能：删除指定索引处的元素。
用例：

LinkedList<String> list = new LinkedList<>();
list.add("Apple");
list.add("Banana");
list.remove(0); // 删除 "Apple"
1
2
3
4

get(int index)

功能：返回链表中指定位置的元素。
用例：

LinkedList<String> list = new LinkedList<>();
list.add("Apple");
String item = list.get(0); // 获取第一个元素 "Apple"
1
2
3

set(int index, E element)

功能：替换指定位置的元素，并返回旧值。
用例：

LinkedList<String> list = new LinkedList<>();
list.add("Apple");
String oldItem = list.set(0, "Orange"); // 将 "Apple" 替换为 "Orange"
1
2
3

size()

功能：返回链表中的元素数量。
用例：

LinkedList<String> list = new LinkedList<>();
list.add("Apple");
int size = list.size(); // size 为 1
1
2
3

isEmpty()

功能：检查链表是否为空。
用例：

LinkedList<String> list = new LinkedList<>();
boolean empty = list.isEmpty(); // 判断链表是否为空
1
2

clear()

功能：清空链表中的所有元素。
用例：

LinkedList<String> list = new LinkedList<>();
list.add("Apple");
list.clear(); // 清空链表
1
2
3

contains(Object o)

功能：检查链表是否包含指定的元素。
用例：

LinkedList<String> list = new LinkedList<>();
list.add("Apple");
boolean contains = list.contains("Apple"); // 检查是否包含 "Apple"
1
2
3

indexOf(Object o) 和 lastIndexOf(Object o)

功能：返回指定元素首次出现和最后一次出现的索引位置。
用例：

LinkedList<String> list = new LinkedList<>();
list.add("Apple");
list.add("Banana");
list.add("Apple");
int firstIndex = list.indexOf("Apple"); // 返回 0
int lastIndex = list.lastIndexOf("Apple"); // 返回 2
1
2
3
4
5
6

toArray()

功能：将链表中的元素转换为数组。
用例：

LinkedList<String> list = new LinkedList<>();
list.add("Apple");
Object[] array = list.toArray(); // 转换为数组
1
2
3

addAll(Collection<? extends E> c)

功能：将指定集合中的所有元素添加到链表的尾部。
用例：

LinkedList<Integer> list = new LinkedList<>();
LinkedList<Integer> newElements = new LinkedList<>(Arrays.asList(1, 2, 3));
list.addAll(newElements);  // 添加多个元素
1
2
3

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

功能：将指定集合中的所有元素添加到链表中的指定位置。
用例：

LinkedList<String> list = new LinkedList<>(Arrays.asList("a", "b", "c"));
LinkedList<String> newElements = new LinkedList<>(Arrays.asList("x", "y"));
list.addAll(1, newElements);  // 在索引1的位置添加多个元素
1
2
3

removeAll(Collection<?> c)

功能：从链表中移除指定集合中也存在的所有元素。
用例：

LinkedList<String> list = new LinkedList<>(Arrays.asList("a", "b", "c", "b"));
list.removeAll(Collections.singleton("b"));  // 移除所有 "b"
1
2

retainAll(Collection<?> c)

功能：仅保留链表中那些也包含在指定集合中的元素。
用例：

LinkedList<String> list = new LinkedList<>(Arrays.asList("a", "b", "c"));
list.retainAll(Arrays.asList("a", "b"));  // 保留 "a" 和 "b"
1
2

containsAll(Collection<?> c)

功能：如果链表包含指定集合中的所有元素，则返回 true。
用例：

LinkedList<String> list = new LinkedList<>(Arrays.asList("a", "b", "c"));
boolean contains = list.containsAll(Arrays.asList("a", "b"));  // 检查是否包含 "a" 和 "b"
1
2

4.2、继承自 `Queue` 接口的方法

offer(E e)

功能：将指定的元素添加到队列的尾部。
用例：

LinkedList<String> queue = new LinkedList<>();
queue.offer("Apple");
1
2

poll()

功能：获取并移除队列的头部元素，如果队列为空，则返回 null。
用例：

LinkedList<String> queue = new LinkedList<>();
queue.offer("Apple");
String item = queue.poll(); // 获取并移除 "Apple"
1
2
3

remove()

功能：获取并移除队列的头部元素，如果队列为空，则抛出 NoSuchElementException。
用例：

LinkedList<String> queue = new LinkedList<>();
queue.offer("Apple");
String item = queue.remove(); // 获取并移除 "Apple"
1
2
3

peek()

功能：获取但不移除队列的头部元素，如果队列为空，则返回 null。
用例：

LinkedList<String> queue = new LinkedList<>();
queue.offer("Apple");
String item = queue.peek(); // 获取但不移除 "Apple"
1
2
3

element()

功能：获取但不移除队列的头部元素，如果队列为空，则抛出 NoSuchElementException。
用例：

LinkedList<String> queue = new LinkedList<>();
queue.offer("Apple");
String item = queue.element(); // 获取但不移除 "Apple"
1
2
3

4.3、Collections 类中涉及 LinkedList 的常用方法

sort(List<T> list)

功能：对链表进行排序（自然顺序）。
用例：

LinkedList<Integer> list = new LinkedList<>(Arrays.asList(3, 1, 4, 1, 5));
Collections.sort(list); // 对链表排序
1
2

reverse(List<?> list)

功能：反转链表中元素的顺序。
用例：

LinkedList<Integer> list = new LinkedList<>(Arrays.asList(1, 2, 3));
Collections.reverse(list); // 链表变为 [3, 2, 1]
1
2

shuffle(List<?> list)

功能：随机打乱链表中元素的顺序。
用例：

LinkedList<Integer> list = new LinkedList<>(Arrays.asList(1, 2, 3));
Collections.shuffle(list); // 打乱链表元素的顺序
1
2

binarySearch(List<? extends Comparable<? super T>> list, T key)

功能：在已排序的链表中使用二分查找法查找指定元素的索引。
用例：

LinkedList<Integer> list = new LinkedList<>(Arrays.asList(1, 2, 3, 4, 5));
Collections.sort(list);
int index = Collections.binarySearch(list, 3); // 在链表中查找数字 3 的索引
1
2
3

copy(List<? super T> dest, List<? extends T> src)

功能：将一个链表中的所有元素复制到另一个链表中。
用例：

LinkedList<Integer> src = new LinkedList<>(Arrays.asList(1, 2, 3));
LinkedList<Integer> dest = new LinkedList<>(Arrays.asList(5, 6, 7, 8));
Collections.copy(dest, src); // 将 src 复制到 dest
1
2
3

fill(List<? super T> list, T obj)

功能：使用指定元素替换链表中的所有元素。
用例：

LinkedList<Integer> list = new LinkedList<>(Arrays.asList(1, 2, 3));
Collections.fill(list, 0); // 将链表中的所有元素替换为 0
1
2

addAll(Collection<? super T> c, T... elements)

功能：向集合中添加多个元素。
用例：

LinkedList<Integer> list = new LinkedList<>();
Collections.addAll(list, 1, 2, 3, 4);  // 向链表中添加多个元素
1
2

replaceAll(List<T> list, T oldVal, T newVal)

功能：替换链表中所有的旧值为新值。
用例：

LinkedList<Integer> list = new LinkedList<>(Arrays.asList(1, 2, 1, 3));
Collections.replaceAll(list, 1, 99);  // 将所有1替换为99
1
2

frequency(Collection<?> c, Object o)

功能：返回指定元素在集合中出现的次数。
用例：

LinkedList<Integer> list = new LinkedList<>(Arrays.asList(1, 2, 1, 3));
int freq = Collections.frequency(list, 1);  // 计算1在链表中出现的次数
1
2

disjoint(Collection<?> c1, Collection<?> c2)

功能：如果两个集合没有共同的元素，则返回 true。
用例：

LinkedList<Integer> list1 = new LinkedList<>(Arrays.asList(1, 2, 3));
LinkedList<Integer> list2 = new LinkedList<>(Arrays.asList(4, 5, 6));
boolean isDisjoint = Collections.disjoint(list1, list2);  // 检查两个链表是否没有共同元素
1
2
3

通过以上方法，可以对 LinkedList 进行各种常用操作，如添加、删除、获取元素等，以及使用 Collections 类中的方法对 LinkedList 进行排序、反转、打乱顺序等批量操作。特别是继承自 Queue 接口的方法，可以使 LinkedList 作为队列使用，提供了队列相关的操作。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/喵喵爱编程/article/detail/748530