1. 内容大纲

本章节的代码：https://github.com/wicksonZhang/data-structure/tree/main/2-LinkedList/src/main/java/com/wickson/linkedlist/single

01-链表

2. 基础知识

2.1. 什么是链表

链表是一种线性的数据结构，主要存储和组织元素的一个集合节点。

2.2. 链表优缺点

优点

  1. 链表可以动态管理数据大小：链表可以根据节点动态分配内存，不需要分配固定大小的内存。
  2. 插入和删除的效率高：由于我们插入和删除时，只需要更改节点的指针，而不需要大量移动元素。
  3. 不需要固定容量。

缺点

  1. 随机访问效率低：当我们查找一个元素时，需要从头找到尾因此最好情况时间复杂度是O(1)，最坏时间复杂度是O(n)。
  2. 不适合高性能计算。

2.3. 链表的分类

链表的分类存在很多种，但如我们目前只讨论如下三种情况：

  1. 单向链表：单向链表是最基本的链表类型，每个节点包含数据和指向下一个节点的引用，节点之间的连接是单向的。

    image-20231105213648546

  2. 双向链表：双向链表是扩展自单链表的一种，每个节点包含数据、指向下一个节点的引用以及指向前一个节点的引用。节点的连接是双向的。

    image-20231105215614720

  3. 循环链表：循环链表是一种链表，其最后一个节点指向第一个节点，形成一个环。这意味着可以无限地循环遍历链表。

    3.1. 单向循环链表：

    image-20231105220007379

    3.2. 双向循环链表：

    image-20231105221002863

2.4. 生活中具体的例子

  1. 火车车厢链接：火车的车厢满足链表这种数据结构。火车有具体的编号，乘客类似于数据，车厢必须要与下一节车厢连接。
  2. 音乐播放列表：音乐播放列表足链表这种数据结构。当前播放的音乐必须知道下一首和上一首歌曲是什么。

3. 接口设计

我们从动态数组中我们可以再次对 List 集合进行优化，我们将公共部分进行封装为 AbstractList 。

image-20231106212829525

  • List<E>.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public interface List<E> {
    
    int size();	// 元素数量
    
    boolean isEmpty(); // 数组是否为空

    boolean contains(E element); // 是否包含某个元素
    
    void add(E element); // 添加元素

    E get(int index); // 获取指定位置元素

    E set(int index, E element); // 设置指定位置元素

    void add(int index, E element); // 将元素添加到指定位置

    E remove(int index); // 删除指定位置元素

    int indexOf(E element); // 获取元素索引

    void clear(); // 清除所有元素

}
  • AbstractList<E>.java
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
public abstract class AbstractList<E> implements List<E> {

    protected int size = 0;
    
    // 元素数量
    @Override
    public int size() { return size; }

    // 数组是否为空
    @Override
    public boolean isEmpty() { return size == 0; }

    // 数组是否包含某个元素
    @Override
    public boolean contains(E e) { return indexOf(e) >= 0; }

    // 添加元素到首尾部
    @Override
    public void add(E element) { add(size, element);
                                
	// 范围检查
    public void rangeChecked(int index) { if (index >= size || index < 0) { indexOutOfBounds(index); } }

    // 元素新增范围检查
    public void rangeAddChecked(int index) { if (index > size || index < 0) { indexOutOfBounds(index); } }

    // 数组越界异常
    public void indexOutOfBounds(int index) { throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size); }

}
  • LinkedList<E>.java
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 class LinkedList<E> extends AbstractList<E>{

    @Override
    public E get(int index) {
        return null;
    }

    @Override
    public E set(int index, E element) {
        return null;
    }

    @Override
    public void add(int index, E element) { }

    @Override
    public E remove(int index) {
        return null;
    }

    @Override
    public int indexOf(E element) {
        return 0;
    }

    @Override
    public void clear() {}
    
}

4. 代码实现

4.1. 初始化

需求：我们初始化一个原始的链表节点元素。

image-20231106223916047

实现步骤

  1. 初始化类 LinkedList<E> ，其中存放两个元素，第一个元素存放 size , 第二个元素指向下一个节点。
  2. 创建节点 Node<E> ，其中也是存放两个元素，第一个元元素存放 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 class LinkedList<E> extends AbstractList<E>{
    
	private int size;    

	/**
	 * 指向下个节点的引用
	 */
	private Node<E> first;

    private static class Node<E> {
        /**
         * 元素
         */
        E element;

        /**
         * 指向下一个节点
         */
        Node<E> next;

        public Node(E element, Node<E> next) {
            this.element = element;
            this.next = next;
        }
    }
    
    // TODO
}

4.2. 获取节点

需求：通过 index 索引获取 Node 节点。

image-20231106225817793

实现步骤

  1. 例如，我们需要获取索引为 2 的节点，那就是通过 first.next.next 直接就获取到了索引为 2 的 Node 节点。
  2. 首先，我们找到头节点。
  3. 然后，我们在通过索引的遍历直接找到对应的 Node 节点即可。

具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
 * 获取节点
 *
 * @param index 索引
 * @return Node<E>
 */
private Node<E> node(int index) {
    rangeChecked(index);
    Node<E> node = first;
    for (int i = 0; i < index; i++) {
        node = node.next;
    }
    return node;
}

4.3. 添加元素到指定位置

需求：我们需要将新的节点添加到节点为 0 的后面

注意：我们需要考虑添加到 0 节点的位置和最后一个节点的位置

动画

实现步骤

  1. 例如，我们需要将新节点(Node)元素添加到 index 为 1 的位置。
  2. 首先，我们需要找到 index 为 1 的节点。
  3. 然后，我们需要将新节点(Node)的 next 指向 index = 1 的节点。
  4. 最后，我们将上一个节点的next 指向 新节点(Node)。
  5. 注意，我们需要考虑 index = 0 的情况。

具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * 添加元素到指定位置
 *
 * @param index   索引
 * @param element 元素
 */
@Override
public void add(int index, E element) {
    rangeAddChecked(index);
    
    if (index == 0) {
        first = new Node<>(element, null);
    } else {
        Node<E> prevNode = node(index - 1);
        Node<E> nextNode = prevNode.next;
        prevNode.next = new Node<>(element, nextNode);
    }
    size++;
}

4.4. 设置指定位置元素

需求：设置指定位置元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
 * 设置指定位置元素
 *
 * @param index   索引
 * @param element 元素
 * @return E
 */
@Override
public E set(int index, E element) {
    Node<E> node = node(index);
    E old = node.element;
    node.element = element;
    return old;
}

4.5. 删除指定元素

需求：我们删除 index=1 这个元素。

动画

实现步骤

  1. 例如，我们需要删除 index 为 1 的节点。
  2. 首先，我们获取当前节点信息。【node(index)】
  3. 然后，我们获取到当前节点的下一个节点信息。【node(index).next】

  4. 最后，我们获取当前节点的上一个节点信息，指向当前节点的下一个节点。【node(index - 1).next = node(index).next】

  5. 注意，我们需要考虑 index = 0 的情况。

具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * 删除指定元素
 *
 * @param index 索引
 * @return
 */
@Override
public E remove(int index) {
    rangeChecked(index);
    
    Node<E> node = node(index);
    if (index == 0) {
        first = first.next;
    } else {
        Node<E> prevNode = node(index - 1);
        prevNode.next = prevNode.next.next;
    }
    size--;
    return node.element;
}

4.6. 清空元素

需求：清空所有元素。

1
2
3
4
5
6
7
8
/**
 * 清空元素
 */
@Override
public void clear() {
    size = 0;
    first = null;
}

4.7. 获取指定位置元素

需求：获取指定位置元素。

1
2
3
4
5
6
7
8
9
/**
 * 获取指定位置元素
 * @param index 索引
 * @return
 */
@Override
public E get(int index) {
    return node(index).element;
}

4.8. 获取元素索引

需求：根据给定的元素，找到对应的索引

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
/**
 * 获取元素索引
 *
 * @param element 元素
 * @return
 */
@Override
public int indexOf(E element) {
    Node<E> node = first;
    if (element == null) {
        for (int i = 0; i < size; i++) {
            if (null == node.element) {
                return i;
            }
            node = node.next;
        }
    } else {
        for (int i = 0; i < size; i++) {
            if (element.equals(node.element)) {
                return i;
            }
            node = node.next;
        }
    }
    return -1;
}

4.9. 打印元素

需求：打印节点元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * 打印元素
 *
 * @return
 */
@Override
public String toString() {
    StringBuilder builder = new StringBuilder();
    builder.append("{ size = ").append(size).append(" , [");
    Node<E> node = first;
    for (int i = 0; i < size; i++) {
        if (i != 0) {
            builder.append(",");
        }
        builder.append(node.element);
        node = node.next;
    }
    builder.append(" ]}");
    return builder.toString();
}

4.10. 测试用例

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
public class LinkedListTest {

    private LinkedList<String> list;

    @Before
    public void setUp() {
        list = new LinkedList<>();
    }

    @Test
    public void testAddToEmptyList() {
        list.add(0, "A");
        assertEquals("A", list.get(0));
        assertEquals(1, list.size());
    }

    @Test
    public void testAddToNonEmptyList() {
        list.add(0, "A");
        list.add(1, "B");
        list.add(1, "C");
        assertEquals("A", list.get(0));
        assertEquals("C", list.get(1));
        assertEquals("B", list.get(2));
        assertEquals(3, list.size());
    }

    @Test
    public void testGet() {
        list.add(0, "A");
        list.add(1, "B");
        list.add(2, "C");
        assertEquals("A", list.get(0));
        assertEquals("B", list.get(1));
        assertEquals("C", list.get(2));
    }

    @Test
    public void testSet() {
        list.add(0, "A");
        list.add(1, "B");
        list.set(1, "C");
        assertEquals("A", list.get(0));
        assertEquals("C", list.get(1));
    }

    @Test
    public void testRemove() {
        list.add(0, "A");
        list.add(1, "B");
        list.add(2, "C");
        String removedElement = list.remove(1);
        assertEquals("B", removedElement);
        assertEquals(2, list.size());
        assertEquals("A", list.get(0));
        assertEquals("C", list.get(1));
    }

    @Test
    public void testIndexOf() {
        list.add(0, "A");
        list.add(1, "B");
        list.add(2, "C");
        list.add(3, null);
        assertEquals(1, list.indexOf("B"));
        assertEquals(3, list.indexOf(null));
    }

    @Test
    public void testClear() {
        list.add(0, "A");
        list.add(1, "B");
        list.clear();
        assertEquals(0, list.size());
    }

    @Test(expected = IndexOutOfBoundsException.class)
    public void testGetWithInvalidIndex() {
        list.get(0); // Expecting an exception since the list is empty
    }

    @Test(expected = IndexOutOfBoundsException.class)
    public void testSetWithInvalidIndex() {
        list.set(0, "A"); // Expecting an exception since the list is empty
    }

    @Test(expected = IndexOutOfBoundsException.class)
    public void testRemoveWithInvalidIndex() {
        list.remove(0); // Expecting an exception since the list is empty
    }

    @After
    public void printf() {
        System.out.println("toString() = " + list.toString());
    }

}

5. 实战练习

如下练习题主要来源于 LeetCode

5.1. 删除链表中的节点

地址：https://leetcode.cn/problems/delete-node-in-a-linked-list/description/

  • 需求如下：

    image-20231107220904126

  • 实现方案：
    • 方案一：如果能获取到当前节点【5】的上一个节点【4】，然后再通过节点【4】指向下下个节点【1】，就解决问题了，但我们无法获取到节点【4】。
    • 方案二（实践方案）：如果我们不走节点，而是移动节点内的元素，这个问题就很好解决了。
  • 实现步骤：
    • Step-1：我们将当前节点【5】(的下一个节点【1】元素覆盖掉当前节点【5】元素。==》 node.element = node.next.element;
    • Step-2：我们在将当前节点【1】指向到下下个节点【9】。 ==》 node.next= node.next.next;
  • 实现代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class ListNode {
    int val;

    ListNode next;

    ListNode(int x) {
        val = x;
    }
}

public void deleteNode(ListNode node) {
    node.val = node.next.val;
    node.next = node.next.next.next;
}

5.2. 反转一个链表

地址：https://leetcode.cn/problems/reverse-linked-list/description/

  • 需求如下：

    image-20231107230902530

  • 实现方式：

    • 方式一（递归法）：递归就是自己调用自己，其核心思想是反转剩余部分的链表，然后再处理当前节点。
    • 方式二（迭代法）：通过改变当前节点的下一指针指向,实现局部反转,再通过移动节点顺序扩展到全局反转。

5.2.1. 递归法

  • 实现步骤：

    • 思路：递归分为两个部分，第一个部分是寻找出口，第二个部分是处理拆分后每个节点的逻辑。
    • Step-1：首先，我们的出口应该满足当前节点为空，或者当前节点的 next 为空。 head == null || head.next == null。
    • Step-2：然后，我们在处理逻辑部分，首先我们需要知道那个节点先出来。 head -> ListNode{val=4, next=ListNode{val=5, next=null}}。
    • Step-3：最后，处理共同的逻辑。head.next.next = head、head.next = null。
  • 代码实现：
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
public class _206_反转链表 {

    /**
     * 需求：反转链表
     * <p>
     * list：   1 -> 2 -> 3 -> 4 -> 5 -> null
     * reverse：5 -> 4 -> 3 -> 2 -> 1 -> null
     *
     * @param head 头节点
     * @return
     */
    public static ListNode reverseList(ListNode head) {
        // 递归反分为两部分：第一部分找到程序出口，第二部分处理核心逻辑
        // ================================= 寻找出口 =================================
        // 1. 为什么 reverseList(head) 是从 head.next 开始，而不是从 head 开始？
        // >  如果从 head 开始我们最后的结果就是死循环。
        // >  解决方案： head.next。
        // >  递归的核心思想是反转剩余部分的链表，然后再处理当前节点。
        // ================================= 寻找出口 =================================
        // Step-1: 寻找出口
        if (head == null || head.next == null) {
            return head;
        }
        System.out.println("head = " + head);
        ListNode listNode = reverseList(head.next);
        // ================================= 逻辑处理 =================================
        // 1. listNode 返回的又是谁？head 最后指向的是谁？
        // >  listNode -> ListNode{val=5, next=null};
        // >  head -> ListNode{val=4, next=ListNode{val=5, next=null}}.
        // ================================= 逻辑处理 =================================
        head.next.next = head;
        head.next = null;
        return listNode;
    }

}

5.2.2. 迭代法

实现步骤：

  • 进入的数据：ListNode{val=1, next=ListNode{val=2, next=null}}

  • 定义一个临时节点 tempNode 初始化为null

  • 当头节点head不为空时,进入循环
  • 保存head的下一个节点为 nextNode
  • 将head的next指针指向 tempNode 实现局部反转
  • 将head赋值给 tempNode 保存反转后的部分链表
  • head移动到 nextNode 继续下一次反转
  • 循环结束后 tempNode 指向反转后的链表
  • 返回 tempNode 作为新链表的头节点
1
2
3
4
5
6
7
8
9
10
11
12
13
public static ListNode reverseList2(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    ListNode tempNode = null;
    while (head != null) {
        ListNode nextNode = head.next;
        head.next = tempNode;
        tempNode = head;
        head = nextNode;
    }
    return tempNode;
}

5.3. 环形链表

地址：https://leetcode.cn/problems/linked-list-cycle/

  • 需求如下：

image-20231108234019283

  • 实现方式

    • 快慢指针：通过快慢指针进行解决问题，例如在一个操场跑步，一个快一个慢，他们总会相遇。

  • 实现步骤

    • 主要使用快慢指针进行实现，慢指针走一步，快指针走两步，如果存在环那么他们一定会相遇。

    动画

  • 实现代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    public boolean hasCycle(ListNode head) {
      if (head == null || head.next == null) return false;

      ListNode slow = head;
      ListNode fast = head.next;

      while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) return true; 
      }

      return false;
    }

6. 参考博文