使用Java语言深度探索数据结构中的单向链表：完美结合详解与示例代码

版本说明

当前版本号[20231010]。

目录

2.2 链表

1) 概述

定义

​ 在计算机科学中，链表是数据元素的线性集合，其每个元素都指向下一个元素，元素存储上并不连续。

简单分类

• 单向链表，每个元素只知道其下一个元素是谁

• 双向链表，每个元素知道其上一个元素和下一个元素

• 循环链表，通常的链表尾节点 tail 指向的都是 null，而循环链表的 tail 指向的是头节点 head

​ 链表内还有一种特殊的节点称为哨兵（Sentinel）节点，也叫做哑元（ Dummy）节点，它不存储数据，通常用作头尾，用来简化边界判断，如下图所示

随机访问性能

根据 index 查找，时间复杂度 $O(n)$

插入或删除性能

• 起始位置：$O(1)$
• 结束位置：如果已知 tail 尾节点是 $O(1)$，不知道 tail 尾节点是 $O(n)$
• 中间位置：根据 index 查找时间 + $O(1)$

2) 单向链表

根据单向链表的定义，首先定义一个存储 value 和 next 指针的类 Node，和一个描述头部节点的引用

public class SinglyLinkedList {
    
    private Node head; // 头部节点
    
    private static class Node { // 节点类
        int value;
        Node next;

        public Node(int value, Node next) {
            this.value = value;
            this.next = next;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

• 这个类有一个私有成员变量head，它是一个指向Node类型的指针，用于存储链表的头节点。
• public Node 是一个私有静态内部类，表示链表中的节点。其中还具有一个构造函数，用于初始化节点的值和下一个节点的引用。包含两个成员变量：
• • value：一个整数类型的值，表示节点存储的数据。
  • next：一个指向下一个节点的引用，用于在链表中连接多个节点。
• 定义为 static 内部类，是因为 Node 不需要与 SinglyLinkedList 实例相关，多个 SinglyLinkedList实例能共用 Node 类定义

头部添加

addFirst方法：用于在链表的头部添加一个新的节点。

public class SinglyLinkedList {
    // ...
    public void addFirst(int value) {
		this.head = new Node(value, this.head);
    }
}
1
2
3
4
5
6

• 创建一个新的Node对象，将其值设置为value，并将其next指针指向当前的头节点。最后，将头节点更新为新创建的节点。
• 如果 this.head == null，新增节点指向 null，并作为新的 this.head
• 如果 this.head != null，新增节点指向原来的 this.head，并作为新的 this.head
  • 注意赋值操作执行顺序是从右到左

如何创建一个新的节点？

分为两种情况。一种是链表为空，另一种是链表非空。

1、在链表为空下，只要将头指针指向新节点。最后，新节点就是我们链表中第一个节点。

this.head = new Node(value, null);
1

2、在链表非空下，只要将新节点指向下一个节点，然后头指针指向新节点。最后，新节点就是我们链表中第一个节点，而原来的那个节点就是第二个节点了。

this.head = new Node(value, head);//括号里的head指的是原来旧的那个节点，新节点下一个就要指向这个节点
1

循环遍历

while遍历

​ 在循环中，首先将头节点赋值给指针p。然后，使用条件判断p != null来检查指针是否为空。如果指针不为空，就执行循环体内的操作。在这个示例中，我们简单地打印了当前节点的值。

​ 接下来，通过p = p.next将指针p更新为下一个节点，以便在下一次循环中处理下一个节点。循环会一直执行，直到指针p为空，即到达链表的末尾。

public void loop()
    {
        Node p = head;
        while(p != null)
        {
            System.out.println(p.value);
            p = p.next;
        }
    }
1
2
3
4
5
6
7
8
9

测试类：

 @Test
    public void test_loop(){
        单向链表 p = new 单向链表();
        p.addFirst(1);
        p.addFirst(2);
        p.addFirst(3);
        p.addFirst(4);
        p.loop();
    }
1
2
3
4
5
6
7
8
9

测试结果如下：

或者以参数的形式传递：

你可以将要对每个节点执行的操作作为Consumer类型的参数传递给loop方法。例如，你可以使用System.out.println打印节点的值，或者将节点的值添加到集合中等。

public void loop(Consumer<Integer> consumer) {
    Node p = head; // 将头节点赋值给指针p
    while (p != null) { // 当指针p不为空时执行循环
        consumer.accept(p.value); // 调用consumer的accept方法处理当前节点的值
        p = p.next; // 将指针p更新为下一个节点，继续遍历链表
    }
}
1
2
3
4
5
6
7

测试类

@Test
    public void test_loop(){
        单向链表 p = new 单向链表();
        p.addFirst(1);
        p.addFirst(2);
        p.addFirst(3);
        p.addFirst(4);

       p.loop(value->{
           System.out.println(value);
       });
    }
1
2
3
4
5
6
7
8
9
10
11
12

测试结果与上面的图相同。

for 遍历

​ 在循环中，我们使用了一个传统的for循环来遍历链表。首先，将头节点赋值给指针p。然后，使用条件判断p != null来检查指针是否为空。如果指针不为空，就执行循环体内的操作。在这个示例中，我们调用了consumer的accept方法，并将当前节点的值作为参数传递给它。

​ 接下来，通过p = p.next将指针p更新为下一个节点，以便在下一次循环中处理下一个节点。循环会一直执行，直到指针p为空，即到达链表的末尾。

 public void loop_for(Consumer<Integer> consumer) {
        for (Node p = head; p != null; p = p.next) {
            consumer.accept(p.value);
        }
    }
1
2
3
4
5

迭代器遍历

​ 这个类，实现了Iterable接口。这个类用于表示一个单向链表，其中包含一个头指针head，以及一个内部类Node用于表示链表中的节点。

​ 在这个类中，实现了iterator()方法，该方法返回一个Iterator对象，用于遍历链表中的元素。Iterator接口有两个方法：hasNext()和next()。

• hasNext 用来判断是否还有必要调用 next

• next 做两件事

  • 返回当前节点的 value
  • 指向下一个节点

  NodeIterator 要定义为非 static 内部类，是因为它与 SinglyLinkedList 实例相关，是对某个 SinglyLinkedList 实例的迭代

public class 单向链表 implements Iterable<Integer>//整体
{
    private Node head = null;//头指针

    //匿名内部类
    @Override //alt+enter 快捷键
    public Iterator<Integer> iterator() {
        return new Iterator<Integer>() {
            Node p = head;
            @Override
            public boolean hasNext() {//是否有下一个元素
                return p != null;
            }

            @Override
            public Integer next() {//返回当前值，并指向下一个元素
                int v = p.value;
                p = p.next;
                return v;
            }
        };
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

测试类

@Test
    public void test_class(){
        单向链表 p = new 单向链表();
        p.addFirst(6);
        p.addFirst(9);
        p.addFirst(2);
        p.addFirst(5);

       for(Integer value : p)
       {
           System.out.println(value);
       }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13

测试结果如下：

匿名内部类转换为带名字的内部类

在 IDEA 中，可以使用以下快捷键将匿名内部类转换为带名称的内部类：

1. 选中匿名内部类。
2. 按下 右键，选Refactor（Windows/Linux）后，在选中 Convert Anonymous to Inner..即可将匿名内部类转换为带名称的内部类。
3. IDEA 会自动为该匿名内部类生成一个具有描述性名称的新内部类，并将其放置在当前文件中。

生成的新内部类代码如下：

 @Override //alt+enter 快捷键
    public Iterator<Integer> iterator() {
        return new NodelIterator();
    }
    
    private class NodelIterator implements Iterator<Integer> {
        Node p = head;

        @Override
        public boolean hasNext() {//是否有下一个元素
            return p != null;
        }

        @Override
        public Integer next() {//返回当前值，并指向下一个元素
            int v = p.value;
            p = p.next;
            return v;
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

尾部添加

递归遍历

在尾部添加之前，需要先找到链表中最后一个元素，才可以指向下一个元素，完成尾部的添加。

• 第一个findLast方法首先检查链表是否为空（head == null），如果为空，则返回 null。
• 接下来，它定义了一个指针 p，并将其初始化为链表的头节点（head）。
• 然后，使用一个循环来遍历链表，直到找到最后一个节点为止。
• 
• 在每次迭代中，它将指针 p 更新为下一个节点（p.next），直到 p.next 为 null，即找到了最后一个节点。
• 
• 最后，它返回最后一个节点的引用（p）。

private Node findLast(){
    if(head == null) {
        return null;
    }
    Node p;
    for(p = head; p.next != null; p = p.next) {
        // 遍历链表，直到找到最后一个节点
    }
    return p;
}
1
2
3
4
5
6
7
8
9
10

• 第二个addLast方法首先调用 findLast() 方法来查找链表的最后一个节点，并将其赋值给变量 last。
• 然后，它检查链表是否为空（head == null），如果为空，说明链表为空，因此调用 addFirst(value) 方法将新节点作为第一个节点添加到链表中，并立即返回。
• 如果链表不为空，它将创建一个新的节点，使用给定的值 value 作为节点的值，并将下一个节点的引用设置为 null。
• 然后，它将新节点的 next 指针指向最后一个节点的 next 指针，即将新节点添加到最后一个节点的后面。

public void addLast(int value) {
    Node last = findLast();
    if(head == null) {
        addFirst(value);
        return;
    }
    last.next = new Node(value, null);
    // 将新节点添加到最后一个节点的后面
}
1
2
3
4
5
6
7
8
9

• 注意，找最后一个节点，终止条件是 curr.next == null
• 分成两个方法是为了代码清晰，而且 findLast() 之后还能复用

写了一个相对应的测试类进行测试代码是否正确：

 @Test
    public void test_addLast(){
        单向链表 p = new 单向链表();
        p.addFirst(2);
        p.addFirst(4);
        p.addFirst(6);
        p.addFirst(8);
        p.addLast(7);

        for(Integer value : p)
        {
            System.out.println(value);
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

测试结果如下，p.addLast添加的 7 在整个链表的最尾部。

根据索引获取

先查找到具有指定索引的节点，再对应去找到这个节点所对应的值。

寻找节点对象

• 这个方法接受一个整数参数 index，表示要查找的节点的索引。它首先初始化一个计数器变量 i 为 0。
• 然后，使用一个循环来遍历链表，从头节点开始，依次访问每个节点。在每次迭代中，它将指针 p 更新为下一个节点（p.next），并将计数器 i 增加 1。
• 在每次迭代中，它检查计数器 i 是否等于要查找的索引 index。
• 如果相等，说明找到了具有指定索引的节点，它返回该节点的引用（p）。
• 如果循环结束后仍未找到具有指定索引的节点，说明链表中不存在具有该索引的节点，它返回 null。

 private Node findNode(int index)//返回节点对象
    {
        int i = 0;
        for(Node p = head; p != null; p = p.next, i++)
        {
            if(i == index)
            {
                return p;
            }
        }
        return null;
    }
1
2
3
4
5
6
7
8
9
10
11
12

寻找节点的值

• 这个方法接受一个整数参数 index，表示要查找的节点的索引。
• 它首先调用 findNode 方法来查找具有指定索引的节点，并将结果存储在变量 node 中。
• 然后，它检查 node 是否为 null，即是否找到了具有指定索引的节点。
• 如果 node 为 null，说明链表中不存在具有该索引的节点，它抛出一个 IllegalArgumentException 异常，并使用格式化字符串提供有关错误的详细信息。
• 如果 node 不为 null，则说明找到了具有指定索引的节点，它返回该节点的值（node.Value）。

public int getNode(int index) { //返回节点中的值
        Node node = findNode(index);
        if (node == null) {
            throw new IllegalArgumentException
                    (String.format("索引 [%d] 不合法，无法找到对应的节点", index));
        }
        return node.value;
    }
1
2
3
4
5
6
7
8

测试类

@Test
    public void test_getNode(){
        单向链表 p = new 单向链表();
        p.addFirst(2);
        p.addFirst(4);
        p.addFirst(6);
        p.addFirst(8);

        System.out.println("原链表为：");
        for(Integer value : p)
        {
            System.out.println(value);
        }
        System.out.println("---------------");
        int i = p.getNode(2);
        System.out.println("下标为所对应的值为："+i);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

测试结果如下，输入下标 2 后就会返回其所对应的值为 4 .

插入

• 这个方法接受两个参数：index表示要插入的位置，value表示要插入的值。
• 首先，它调用findNode方法来查找给定索引的前一个节点，并将结果存储在prev变量中。
• 如果找不到前一个节点（即prev为null），则抛出一个IllegalArgumentException异常，指示索引不合法。
• 如果找到了前一个节点，那么将创建一个新的节点，并将其插入到链表中。
• 
• 新节点的值为value，它将作为前一个节点的下一个节点。
• 通过将新节点的next指针指向前一个节点的下一个节点，实现了节点的插入操作。
• 

 public void insert(int index, int value)
    {
        Node prev = findNode(index - 1);
        if(prev == null)
        {
            throw new IllegalArgumentException(
                    String.format("索引 [%d] 不合法，无法找到对应的节点", index));
        }
        prev.next = new Node(value, prev.next);
    }
1
2
3
4
5
6
7
8
9
10

测试类

@Test
    public void test_insert(){
        单向链表 p = new 单向链表();
        p.addLast(2);
        p.addLast(4);
        p.addLast(6);
        p.addLast(8);

        p.insert(2,5);
        for(Integer value : p)
        {
            System.out.println(value);
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

测试结果如下：

删除

删除链表中的第一个节点

• 首先，它会检查链表的头节点是否为空（即head == null），如果为空，则抛出一个IllegalArgumentException异常，表示没有节点可以继续删除。
• 如果链表不为空，那么它会将头节点指向下一个节点（即head = head.next）。
• 这样就实现了删除第一个节点的操作。
• 需要注意的是，在调用该方法之后，原先的第一个节点将不再存在，并且与该节点相关联的其他节点的引用也会发生变化。

public void removeFirst()
    {
        if(head == null)
        {
            throw new IllegalArgumentException(
                    String.format("无节点继续删除"));
        }
        head = head.next;
    }
1
2
3
4
5
6
7
8
9

测试类

@Test
    public void test_removeFirst(){
        单向链表 p = new 单向链表();
        p.addLast(2);
        p.addLast(4);
        p.addLast(6);
        p.addLast(8);

        p.removeFirst();
        for(Integer value : p)
        {
            System.out.println(value);
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

测试结果如下：

删除某个索引位置中的节点

​ 这个方法接受一个整数参数index，表示要删除节点的位置。首先，它会检查index是否为0，如果是，则调用removeFirst()方法来删除第一个节点，并立即返回。

​ 如果index不为0，那么它会调用findNode(index - 1)方法来查找指定位置的前一个节点，并将结果存储在prev变量中。如果找不到前一个节点（即prev为null），则抛出一个IllegalArgumentException异常，指示无法找到上一个节点。

​ 接下来，它会根据index找到要删除的节点，并将其存储在removed变量中。如果找不到要删除的节点（即removed为null），则抛出一个IllegalArgumentException异常，指示无法找到需要删除的节点。

​ 最后，它将前一个节点的next指针指向要删除节点的下一个节点，从而完成了节点的删除操作。需要注意的是，在调用该方法之后，原先指定位置的节点将被移除，并且与该节点相关联的其他节点的引用也会发生变化。

public void remove(int index)
    {
        if(index == 0)
        {
            removeFirst();
            return;
        }

        Node prev = findNode(index - 1);
        if(prev == null)
        {
            throw new IllegalArgumentException(
                    String.format("上一个节点无法找到"));
        }

        Node removed = prev.next;
        if(removed == null)
        {
            throw new IllegalArgumentException(
                    String.format("需要删除的节点无法找到"));
        }
        prev.next = removed.next;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

测试类

 @Test
    public void test_remove(){
        单向链表 p = new 单向链表();
        p.addLast(1);
        p.addLast(3);
        p.addLast(5);
        p.addLast(7);

        p.remove(2);
        for(Integer value : p)
        {
            System.out.println(value);
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

测试结果如下：

3) 单向链表（带哨兵）

观察之前单向链表的实现，发现每个方法内几乎都有判断是不是 head 这样的代码，能不能简化呢？

​ 用一个不参与数据存储的特殊 Node 作为哨兵，它一般被称为哨兵或哑元，拥有哨兵节点的链表称为带头链表。

//private Node head = null;//头指针
    //加上哨兵节点后,哨兵的值不那么重要，其下一个指向为空
    private Node head = new Node(666,null);
1
2
3

加入哨兵后，相关代码就可以适当进行修改了。

如：

​ 既然已经有哨兵节点了，就证明其头节点不可能为空。

​ 修改后的代码将直接在找到的最后一个节点后插入新的节点，而不需要先调用findLast()方法来获取最后一个节点。这样做可以减少一次不必要的查找操作，提高代码的效率。

//原代码 
public void addLast(int value) {
        Node last = findLast();
        if (head == null) {
            addFirst(value);
            return;
        }
        last.next = new Node(value, null);
    }

//修改后的代码
public void addLast(int value) {
        Node last = findLast();
        last.next = new Node(value, null);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

使用原先未进修改的测试类进行测试：

@Test
    public void test_addLast(){
        单向链表 p = new 单向链表();
        p.addFirst(2);
        p.addFirst(4);
        p.addFirst(6);
        p.addFirst(8);

        for(Integer value : p)
        {
            System.out.println(value);
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13

测试的结果如下。发现它会把哨兵节点的值也一并输出：

然后我们对输出的接口方法修改一下，要求只需要输出不包括哨兵节点的节点值即可。

一旦涉及要遍历，都需要将代码修改成 Node p = head.next;.

private class NodelIterator implements Iterator<Integer> {
        Node p = head.next;// 将其改成 head.next 即可直接遍历哨兵节点后面的节点值了

        @Override
        public boolean hasNext() {//是否有下一个元素
            return p != null;
        }

        @Override
        public Integer next() {//返回当前值，并指向下一个元素
            int v = p.value;
            p = p.next;
            return v;
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

4) 双向链表（带哨兵）

双向链表是一种链式存储结构，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。

相比于单向链表，双向链表可以更好地解决反向查找问题。

图解如下：

头部添加

addFirst(int value)：在链表的开始处添加一个新的节点。

 public void addFirst(int value) {
        insert(0, value);
    }
1
2
3

赋予初值

InitialValue()：初始化双向链表，设置头哨兵和尾哨兵的值。

public void InitialValue()//初值
    {
        head = new Node(null, 666, null);
        tail = new Node(null, 888, null);
        head.next = tail;
        tail.next = head;
    }
1
2
3
4
5
6
7

寻找节点的值

findNode(int index)：查找给定索引的节点。

private Node findNode(int index)
    {
        int i = -1;//从头节点开始去查找
        for(Node p = head; p != tail; p = p.next, i++)
        {
            if(i == index)
            {
                return p;
            }
        }
        return tail;
    }
1
2
3
4
5
6
7
8
9
10
11
12

插入

insert(int index, int value)：在给定索引处插入一个新的节点。

1、确定插入新的节点的位置。

2、插入之前，先要确定新的节点的上一个和下一个节点。每一次的插入操作，需要改变四次的指针的方向。

分别是：

• 新节点的prev指针指向上一个节点
• 新节点的next指针指向下一个节点
• 上一个节点的next指针指向新节点
• 下一个节点的prev指针指向新节点

参考代码如下：

public void insert(int index, int value)
    {
        Node prev = findNode(index - 1);
        if(prev == null)
        {
            throw new IllegalArgumentException(
                    String.format("出现异常，请检查后再次提交！")
            );
        }
        Node next = prev.next;
        Node now = new Node(prev, value, next);
    //- 新节点的prev指针指向上一个节点,新节点的next指针指向下一个节点
        prev.next = now;//上一个节点的next指针指向新节点
        next.prev = now;//下一个节点的prev指针指向新节点
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

删除

• remove(int index)：删除给定索引处的节点。
• removeFirst()：删除第一个节点。
• removeLast()：删除最后一个节点。

1、确定待删除的节点的位置。

2、删除之前，先要确定新的节点的上一个和下一个节点。每一次的删除操作，只需要改变两次的指针的方向。

• 上一个节点的next指针指向下一个节点
• 下一个节点的prev指针指向上一个节点
• 不用关心待删除节点的指针指向。

参考代码如下：

 public void remove(int index)
    {
        Node prev = findNode(index - 1);
        if(prev == null)
        {
            throw new IllegalArgumentException(
                    String.format("出现异常，请检查后再次提交！")
            );
        }
        Node removed = prev.next;
        if(removed == null)
        {
            throw new IllegalArgumentException(
                    String.format("出现异常，请检查后再次提交！")
            );
        }
        Node next = removed.next;

        prev.next = next;//上一个节点的next指针指向下一个节点
        next.prev = prev;//下一个节点的prev指针指向上一个节点
    }

    public void removeFirst()
    {
        remove(0);
    }
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

尾部添加

addLast(int value)：在链表的末尾添加一个新的节点。

​ 对于双向链表来说，其尾节点的prev指针指的就是链表中最后的一个节点，这是双向链表与单向链表之间最大的差别。

在尾部添加之前，先要确定新的节点的上一个节点和尾节点。每一次的尾部添加，需要改变四次的指针的方向。

分别是：

• 新节点的prev指针指向上一个节点
• 新节点的next指针指向尾哨兵节点
• 上一个节点的next指针指向新节点
• 尾哨兵节点的prev指针指向新节点

参考代码如下：

 public void addLast(int value)
    {
        Node last = tail.prev;  //通过尾哨兵的prev指针，能找出上一个节点
        Node added = new Node(last , value , tail);
        last.next = added;
        tail.prev = added;
    }
1
2
3
4
5
6
7

抛出异常

这个内部异常类illegalIndex(int index)，用于在尝试访问无效索引时抛出异常。

private IllegalArgumentException illegalIndex(int index) {
        return new IllegalArgumentException(
                String.format("index [%d] 不合法%n", index));
    }
1
2
3
4

输出接口

​ 这段代码是Java语言中双向链表的一个简单实现。它实现了Iterable接口，这意味着它可以用于for-each循环。

​ 这个类的主要部分是iterator()方法，它返回一个实现了Iterator接口的匿名内部类的实例。这个匿名内部类覆盖了Iterator接口的两个方法：hasNext()和next()。

• hasNext()方法用于检查**是否还有更多的元素可以迭代。**在这个实现中，如果当前节点（由变量p表示）不是尾节点，那么就还有下一个元素，所以返回true；否则，如果没有下一个元素，就返回false。
• next()方法用于获取下一个元素。这个方法首先获取当前节点的值（由变量value表示），然后将p移动到下一个节点，最后返回这个值。

public class 双向链表 implements Iterable<Integer>
{
@Override
    public Iterator<Integer> iterator()
    {
        return new Iterator<Integer>() {
            Node p = head.next;//遍历要从有值的节点开始遍历
            @Override
            public boolean hasNext() {
                return p != tail;
            }

            @Override
            public Integer next() {
                int value = p.value;
                p = p.next;
                return value;
            }
        };
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

双向链表完整源代码：

public class 双向链表 implements Iterable<Integer>
{
    static class Node
    {
        Node prev;//上一个节点指针
        int value;//值
        Node next;//下一个节点指针

        public Node(Node prev, int value, Node next) {
            this.prev = prev;
            this.value = value;
            this.next = next;
        }
    }

    private Node head;//头哨兵
    private Node tail;//尾哨兵

    public void InitialValue()//初值
    {
        head = new Node(null, 666, null);
        tail = new Node(null, 888, null);
        head.next = tail;
        tail.next = head;
    }

    private Node findNode(int index)
    {
        int i = -1;
        for(Node p = head; p != tail; p = p.next, i++)
        {
            if(i == index)
            {
                return p;
            }
        }
        return tail;
    }

    public void insert(int index, int value)
    {
        Node prev = findNode(index - 1);
        if(prev == null)
        {
            throw new IllegalArgumentException(
                    String.format("出现异常，请检查后再次提交！")
            );
        }
        Node next = prev.next;
        Node now = new Node(prev, value, next);
        prev.next = now;
        next.prev = now;
    }

    public void remove(int index)
    {
        Node prev = findNode(index - 1);
        if(prev == null)
        {
            throw new IllegalArgumentException(
                    String.format("出现异常，请检查后再次提交！")
            );
        }
        Node removed = prev.next;
        if(removed == null)
        {
            throw new IllegalArgumentException(
                    String.format("出现异常，请检查后再次提交！")
            );
        }
        Node next = removed.next;

        prev.next = next;
        next.prev = prev;
    }

    public void removeFirst()
    {
        remove(0);
    }

    public void addFirst(int value) {
        insert(0, value);
    }

    public void addLast(int value)
    {
        Node last = tail.prev;
        Node added = new Node(last , value , tail);
        last.next = added;
        tail.prev = added;
    }

    public void removeLast()
    {
        Node removed = tail.prev;
        if(removed == null)
        {
            throw new IllegalArgumentException(
                    String.format("出现异常，请检查后再次提交！")
            );
        }
        Node prev = removed.prev;
        prev.next = tail;
        tail.prev = prev;
    }

    private IllegalArgumentException illegalIndex(int index) {
        return new IllegalArgumentException(
                String.format("index [%d] 不合法%n", index));
    }

    @Override
    public Iterator<Integer> iterator()
    {
        return new Iterator<Integer>() {
            Node p = head.next;
            @Override
            public boolean hasNext() {
                return p != tail;
            }

            @Override
            public Integer next() {
                int value = p.value;
                p = p.next;
                return value;
            }
        };
    }
}
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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131

5) 双向环形链表（带哨兵）

双向环形链表带哨兵，这时哨兵既作为头，也作为尾

遍历的时候，从哨兵节点开始遍历，什么时候遍历到哨兵节点，就意味着我们已经走过了一圈了。

构造函数，初始化节点

​ 环形链表是一种数据结构，它类似于单向链表，但是最后一个节点的下一个节点是第一个节点，形成一个环。环形链表可以用于一些需要循环处理的问题，例如约瑟夫问题、链表中的环检测等。

所以在代码实现中，我们使用：

sentinel.prev = sentinel; // 起点的前驱节点和后继节点都是自己
sentinel.next = sentinel; // 起点的后继节点也是自己
1
2

来完成闭环

完整的初始化代码如下：

public class 环形链表
{
    // 内部类 Node，表示链表中的节点
    public static class Node
    {
        Node prev; // 前驱节点
        int value; // 节点的值
        Node next; // 后继节点

        // 构造函数，用于初始化节点的属性
        public Node(Node prev, int value, Node next) {
            this.prev = prev;
            this.value = value;
            this.next = next;
        }
    }

    // 特殊节点 sentinel，作为链表的起点和终点
    private Node sentinel = new Node(null, -1, null);

    // 构造函数，用于初始化环形链表
    public 环形链表() {
        sentinel.prev = sentinel; // 起点的前驱节点和后继节点都是自己
        sentinel.next = sentinel; // 起点的后继节点也是自己
    }
}

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

头部添加

addFirst(int value)：向环形链表的开头插入新节点时调用，通过传入节点的值来实现。

代码逻辑如下：

1. 首先，创建两个指针变量a和b，分别指向链表的起点（即哨兵节点）和哨兵节点的下一个节点。
2. 然后，创建一个新的节点add，它的前驱节点是a，后继节点是b，值为传入的value。
3. 接下来，将add节点插入到链表中，使得a节点的下一个节点变为add，b节点的前驱节点变为add。
4. 这样就完成了在环形链表开头插入新节点的操作。

特指红色的箭头为：

    a.next = add; // 将a节点的下一个节点设置为add
    b.prev = add; // 将b节点的前驱节点设置为add
1
2

图解如下：

参考代码如下：

public void addFirst(int value) {
    Node a = sentinel; // 定义指针变量a，指向链表的起点
    Node b = sentinel.next; // 定义指针变量b，指向哨兵节点的下一个节点
    Node add = new Node(a, value, b); // 创建新节点add，前驱节点为a，后继节点为b，值为传入的value
    a.next = add; // 将a节点的下一个节点设置为add
    b.prev = add; // 将b节点的前驱节点设置为add
}
1
2
3
4
5
6
7

同时也可以写一个测试类用于测试该功能是否可行：

@Test
    public void addFirst(){
        环形链表 list = new 环形链表();
        list.addFirst(1);
        list.addFirst(2);
        list.addFirst(3);
        list.addFirst(4);
        list.addFirst(5);

        for(Integer value : list)
        {
            System.out.println(value);
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

输出结果如下，符合我们的预期：

尾部添加

1. 首先，我们定义两个节点a和b，其中a指向链表的哨兵节点（sentinel），而b为哨兵节点（sentinel）的上一个（prev）。哨兵节点是一种特殊的节点，它不存储任何实际的数据，只是用来作为链表的起始和结束节点。

   

2. 然后，我们创建一个新的节点last，它的前一个节点是b，后一个节点是a，存储的值是传入的value。

3. 接着，我们将b的next指针指向last，表示last节点后面跟着的是原来的最后一个节点。

4. 最后，我们将a的prev指针指向last，表示新的最后一个节点（last）的前一个节点是原来的最后一个节点。

   如下图所示，红色的箭头就代表着我们两个指针的指向。

   b.next = last;
   a.prev = last;
   1
   2

   

这样，我们就在环形链表的尾部添加了一个新的节点。

参考代码如下：

public void addLast(int value)
    {
        Node a = sentinel;
        Node b = sentinel.prev;
        Node last = new Node(b, value , a);
        b.next = last;
        a.prev = last;
    }
1
2
3
4
5
6
7
8

测试类如下：

@Test
    public void addLast(){
        环形链表 list = new 环形链表();
        list.addLast(4);
        list.addLast(2);
        list.addLast(7);
        list.addLast(6);
        list.addLast(9);

        for(Integer value : list)
        {
            System.out.println(value);
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

输出结果如下：

删除

删除头节点

removeFirst()：这段代码是在实现环形链表的删除第一个节点。

具体步骤如下：

1. 首先，我们定义一个节点removed，它的值是sentinel的下一个节点。

   

2. 如果removed等于sentinel，那么说明链表只有一个节点，无法进行删除操作，因此抛出一个非法参数异常。

3. 如果removed不等于sentinel，那么我们就将sentinel的next指针指向removed的下一个节点，即将原来的第一个节点移到了第二个位置。

4. 同时，我们也将removed的next节点的prev指针指向sentinel，表示新的第二个节点的前一个节点是原来的第一个节点。

如下图所示，红色的箭头就代表着我们两个指针的指向。

a.next = b;
b.prev = a;
1
2

这样，我们就完成了环形链表的删除操作。

参考代码如下：

public void removeFirst()
    {
        Node removed = sentinel.next;
        if(removed == sentinel)
        {
            throw new IllegalArgumentException("非法异常！");
        }
        Node a =sentinel;
        Node b = removed.next ;
        a.next = b;
        b.prev = a;
    }
1
2
3
4
5
6
7
8
9
10
11
12

测试类：

@Test
    public void removeFirst(){
        环形链表 list = new 环形链表();
        list.addLast(4);
        list.addLast(2);
        list.addLast(7);
        list.addLast(6);
        list.addLast(9);

        list.removeFirst();

        for(Integer value : list)
        {
            System.out.println(value);
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

测试结果如下：

删除尾节点

removeLast()：这段代码是在实现环形链表的删除最后一个节点。

具体步骤如下：

1. 首先，我们定义一个节点remove，它的值是sentinel的前一个节点。
2. 如果remove等于sentinel，那么说明链表只有一个节点，无法进行删除操作，因此抛出一个非法参数异常。
3. 如果remove不等于sentinel，那么我们就将sentinel的prev指针指向remove的前一个节点，即将原来的最后一个节点移到了倒数第二个位置。
4. 同时，我们也将remove的前一个节点的next指针指向sentinel，表示新的倒数第二个节点的后一个节点是原来的最后一个节点。

这样，我们就完成了环形链表的删除操作。

参考代码如下：

public void removeLast()
    {
        Node remove = sentinel.prev;
        if(remove == sentinel)
        {
            throw new IllegalArgumentException("非法异常");
        }
        Node a = sentinel;
        Node b = remove.prev;
        a.prev = b;
        b.next = a;
    }
1
2
3
4
5
6
7
8
9
10
11
12

测试类：

@Test
    public void removeLast(){
        环形链表 list = new 环形链表();
        list.addLast(4);
        list.addLast(2);
        list.addLast(7);
        list.addLast(6);
        list.addLast(9);

        list.removeLast();

        for(Integer value : list)
        {
            System.out.println(value);
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

测试结果如下：

根据值进行删除

要想根据所输入的值在链表中进行对应的删除，就得先查找到这个值所在的节点。所以我们得先设计能 返回 查找到的值 的节点findValue(int value)方法。

查找操作

findValue(int value)：实现环形链表的查找操作。

具体步骤如下：

1. 首先，我们定义一个节点p，它的值是sentinel的下一个节点。
2. 然后，我们进入一个循环，只要p不等于sentinel，就一直进行下去。
3. 在循环中，我们判断p的值是否等于我们要查找的值。如果等于，就返回p。
4. 如果p的值不等于我们要查找的值，那么就继续循环，将p的值设置为它的下一个节点。
5. 如果循环结束后还没有找到我们要查找的值，那么就返回null。

这样，我们就实现了环形链表的查找操作。

参考代码如下：

 public Node findValue(int value)
    {
        Node p = sentinel.next;
        while(p != sentinel)
        {
            if(p.value == value)
            {
                return p;
            }
            p = p.next;
        }
        return null;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13

根据值删除

removeByValue(int value)：实现环形链表的根据值进行删除操作。

具体步骤如下：

1. 首先，我们调用findValue方法，传入我们要查找的值，返回值是找到的节点removed。
2. 如果removed等于null，说明链表中没有我们要查找的值，因此抛出一个非法参数异常。
3. 如果removed不等于null，那么我们就将removed的前一个节点a的next指针指向removed的下一个节点b，即将原来的第二个节点移到了第三个位置。
4. 同时，我们也将removed的下一个节点b的prev指针指向a，表示新的第二个节点的前一个节点是原来的第一个节点。

这样，我们就完成了环形链表的删除操作。

参考代码如下：

public void removeByValue(int value)
    {
        Node removed = findValue(value);
        if(removed == null)
        {
            throw new IllegalArgumentException("异常");
        }
        Node a = removed.prev;
        Node b = removed.next;
        a.next = b;
        b.prev = a;
    }
1
2
3
4
5
6
7
8
9
10
11
12

测试类

@Test
    public void removeByValue(){
        环形链表 list = new 环形链表();
        list.addLast(4);
        list.addLast(2);
        list.addLast(7);
        list.addLast(6);
        list.addLast(9);

        list.removeByValue(7);

        for(Integer value : list)
        {
            System.out.println(value);
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

输出结果如下：

双向环形链表完整源代码：

public class 环形链表 implements Iterable<Integer>
{
    @Override
    public Iterator<Integer> iterator() {
        return new Iterator<Integer>() {//Iterator方法实现后，返回一个迭代对象
            Node p = sentinel.next;//从哨兵的下一个节点开始遍历

            @Override
            public boolean hasNext() {
                return p != sentinel; //什么时候p等于哨兵了就退出循环
            }

            @Override
            public Integer next() {
                int value = p.value;
                p = p.next;
                return value;
            }
        };

    }

    public static class Node
    {
        Node prev;
        int value;
        Node next;

        public Node(Node prev, int value, Node next) {
            this.prev = prev;
            this.value = value;
            this.next = next;
        }
    }

    private Node sentinel = new Node(null, -1, null);

    public 环形链表() {
        sentinel.prev = sentinel;
        sentinel.next = sentinel;
    }

    public void addFirst(int value)
    {
        Node a = sentinel;
        Node b = sentinel.next;
        Node add = new Node(a, value, b);
        a.next = add;
        b.prev = add;
    }

    public void addLast(int value)
    {
        Node a = sentinel;
        Node b = sentinel.prev;
        Node last = new Node(b, value , a);
        b.next = last;
        a.prev = last;
    }

    public void removeFirst()
    {
        Node removed = sentinel.next;
        if(removed == sentinel)
        {
            throw new IllegalArgumentException("非法异常！");
        }
        Node a =sentinel;
        Node b = removed.next ;
        a.next = b;
        b.prev = a;
    }

    public void removeLast()
    {
        Node remove = sentinel.prev;
        if(remove == sentinel)
        {
            throw new IllegalArgumentException("非法异常");
        }
        Node a = sentinel;
        Node b = remove.prev;
        a.prev = b;
        b.next = a;
    }

    public Node findValue(int value)
    {
        Node p = sentinel.next;
        while(p != sentinel)
        {
            if(p.value == value)
            {
                return p;
            }
            p = p.next;
        }
        return null;
    }

    public void removeByValue(int value)
    {
        Node removed = findValue(value);
        if(removed == null)
        {
            throw new IllegalArgumentException("异常");
        }
        Node a = removed.prev;
        Node b = removed.next;
        a.next = b;
        b.prev = a;
    }
}
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
109
110
111
112
113