单链表简要分析与实现（Java）

线性表是一个序列，元素之间是有顺序的，若元素存在多个，则第一个元素无前驱，最后一个元素无后继，其他每个元素都有且仅有一个前驱和后继，这其实就是线性的由来。
线性表是强调有序的，存储在线性表中的元素必须是有限的，实际上计算机中处理的对象都是一个有限集，那种存储了无限元素的集合（序列）是只存在于数学概念的，不然爆栈、缓冲区溢出等内存问题不就频繁发生了？

假设线性表中维护了如下几个数据 {1, 3, 2, 7, 5}，线性表在逻辑上的示意图如下：

线性表两种实现方式

线性表具有两种物理结构——顺序存储结构及链式存储结构（链表）。顺序存储通过字面理解，就是计算机在内存中开辟了一定范围的连续存储空间用来存储元素，所以线性表的书奴需存储结构指的就是使用一段地址连续的存储单元依次存储线性表的数据元素，线性表在逻辑上连续，在物理上也连续，不难得出，我们使用一个一维数组 $eq?array%5Blength%5D$ 就可以实现线性表的顺序存储结构，由于在程序设计相关课程中我们已经接触过数组这一数据结构，我们不再花费大量篇幅介绍线性表的顺序存储。

相应的，线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的，换言之，线性表的数据元素可以存储在内存中未被占用的任意位置，当然了解计算机操作系统相关知识的读者应该清楚，计算机内存的低地址部分往往存放了操作系统内核代码、中断向量表等关键数据和代码，随意分配使用低地址空间会产生很多系统风险，所以在 $eq?malloc$ 分配内存时一般不会分配低地址内存。在顺序存储结构中，线性表的数据元素存放在一个数组中，我们很容易通过数组索引找到一个数据元素的直接前驱和直接后继，例如假设当前数据元素存储在数组 $eq?array$ 的 $eq?i$ 位置，那么 $eq?array%5Bi%5D$ 的直接前驱就是 $eq?array%5Bi%20-%201%5D$ ，直接后继就是 $eq?array%5Bi%20+%201%5D$ ，当然前提是这个数据元素并不是线性表的第一个结点或最后一个结点，通过顺序存储结构实现线性表只需要存储数据元素本身即可，但是在链式存储结构中，由于存储这些数据元素的存储空间并不一定是连续的，大多数时候是离散的，所以除了要存储数据元素本身的信息之外，还要存储这个数据元素的直接后继元素的存放地址。对于链式存储结构中的每个元素来说，我们将元素中存储数据元素信息的区域称为数据域Data，将存储此数据元素直接后继位置（物理地址）的区域称为指针域Next，链式存储结构中的存储对象称为结点Node。

结点的结构示意如下：

$eq?n$ 个结点链接而成就形成了一个链表，即线性表的链式存储结构，在刚才提到的存储对象中，我们只存储了这个对象直接后继的物理地址，换言之每个对象只有一个指针域，所以此时的链表称为单链表，我们还需要使用一个头指针来指向链表的第一个结点，为了更方便实现一些操作，我们往往在链表的第一个结点之前再添加一个数据域任意的结点，称为哑元结点或哨兵结点，一般也称为虚拟头节点，哨兵结点的直接后继就是单链表真正存储元素的第一个结点，我们称这个结点为首元结点，由于单链表最后一个元素没有直接后继，于是需要让最后一个结点的指针域指向空（ $eq?NULL$ 、 $eq?nullptr$ 或 $eq?null$ ，具体取决于实现链表的语言）。

一个具有哨兵结点的空链表结构示意图如下：

子问题：线性表顺序存储结构与链式存储结构的比较

顺序存储结构的优点：顺序存储结构的线性表是基于一维数组 $eq?array%5Blength%5D$ 实现的，所以无需为表示元素的前驱后继关系而引入额外的存储空间（如链式存储结构的指针域 $eq?Next$ ）；在顺序存储结构中查找元素的效率较高，通过循环遍历数组即可；

顺序存储结构的缺点：虽然在顺序存储结构中执行查询操作的效率较高，但执行插入和删除的效率就比较低了。对于插入操作，如果只需要在线性表的最后新增存储一个元素，只需要执行 $eq?array%5B++%20len%5D%20%3D%20data$ 即可，若需要在线性表的第一个元素之前插入一个元素呢？那就需要将第一个元素到最后一个元素统一向后移动一个位置，然后再执行 $eq?array%5B0%5D%20%3D%20data%3B%20len%20++$ ，这种牵一发而动全身的操作是比较耗时的，不止如此，如果存储线性表的数组最初定义的长度随着元素的加入逐渐不再满足需求，还需要执行数组扩容和数组拷贝等工作，这些工作都需要耗费一定时间；删除操作同理，不再赘述。

链式存储结构的优点：相比于顺序存储结构，顺序存储结构的一些缺点都在链式存储结构中完美规避了，例如要执行插入操作，我们只需要将待插入结点的指针域指向待插入位置的前驱结点的后继，然后更新待插入位置的前驱结点的指针域，使指针域指向待插入结点即可；对于删除操作，只需要将待删除结点的直接前驱结点的指针域指向待删除结点的直接后继即可，即执行一次 $eq?previous.next%20%3D%20previous.next.next$ ，并没有出现顺序存储结构中的牵一发动全身的情况；除此之外我们在叙述链式存储结构时提到，数据元素存储在计算机内存中未被使用的位置，试问，你需要维护的元素数量能把计算机内存填充满吗？显然不能，所以链式存储结构规避了顺序存储结构中的数组扩容和拷贝的低效率缺点。

链式存储结构的缺点：第一个最大的缺点就是，实现较复杂，尤其对于那些对指针和引用相关概念理解不透彻的初学者；相比于顺序存储结构，链式存储结构在查找指定数据元素时需要沿着指针链查找，很多能够提高效率的基于线性结构的查找算法实现起来较复杂，故链表不适合使用在查找频率较高的场景（毕竟 Java 中 LinkedList 集合的作者Joshua Bloch 就曾提到，“我是 LinkedList 的作者，但在开发中我从未使用过”），除此之外，链表还具有空间局部性差等缺陷。

单链表的实现

为了更方便执行一些操作，我们选择实现带哨兵结点的单链表。

0. 开发环境介绍

作为Java后端学习者，我使用Java语言实现单链表，当然后续会附上其他语言的实现方式。基于 $eq?Maven$ 脚手架构建项目，引入 $eq?junit-jupiter-api$ 单元测试依赖，在一些重要方法上我使用了 $eq?Java%20Doc$ 注释，建议将代码复制到开发工具中查看。

<dependencies>
    <dependency>
        <groupId>org.openjdk.jol</groupId>
        <artifactId>jol-core</artifactId>
        <version>0.16</version>
    </dependency>
    <dependency>
        <groupId>org.springframework</groupId>
        <artifactId>spring-context</artifactId>
        <version>5.3.23</version>
    </dependency>
    <dependency>
        <groupId>org.junit.jupiter</groupId>
        <artifactId>junit-jupiter-api</artifactId>
        <version>5.8.2</version>
        <scope>test</scope>
    </dependency>
    <dependency>
        <groupId>com.lmax</groupId>
        <artifactId>disruptor</artifactId>
        <version>3.4.4</version>
    </dependency>
    <dependency>
        <groupId>org.jctools</groupId>
        <artifactId>jctools-core</artifactId>
        <version>3.1.0</version>
    </dependency>
    <dependency>
        <groupId>com.google.guava</groupId>
        <artifactId>guava</artifactId>
        <version>30.1-jre</version>
    </dependency>
</dependencies>

所有对单链表操作的方法都定义在类 $eq?SinglyLinkedListSentinel$ 中，此类实现了接口用于执行遍历操作。

public class SinglyLinkedListSentinel implements Iterable<Integer> {}

1. 结点类ListNode

刚才介绍过，单链表的结点具有两个属性，数据域 $eq?Data$ 以及指针域 $eq?Next$ ，我们在类 $eq?SinglyLinkedListSentinel$ 中定义一个 $eq?ListNode$ 静态内部类，用于表示链表结点，同时提供构造方法。

// 结点类
private static class ListNode {
    int data;
    ListNode next;
    
    // 数据域为data，指针域为null
    public ListNode(int data) {
        this.data = data;
    }
    public ListNode(int data, ListNode next) {
        this.data = data;
        this.next = next;
    }
}

2. 初始化操作

我们指定哨兵结点的数据域为 666（任意），同时创建一个结点表示哨兵结点，同时让头指针指向哨兵结点，由于此时链表中只有一个哨兵结点，于是让哨兵结点的指针域指向 $eq?null$ 。如下：

// 哨兵结点数据域默认值
private final int SENTINEL_VALUE = 666;
// 头指针最初为哨兵结点的引用
private ListNode head = new ListNode(SENTINEL_VALUE);

3. 参数异常

在后续的查询、删除、插入等方法需要对索引合法性判断，于是自定义一个私有化方法，用来返回简明扼要的参数异常信息。

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

4. 头插法插入结点

何为头插法？头插法就是在链表头部插入一个结点，使这个结点成为新的首元结点。执行的操作实际上很简单：首先创建一个数据域为 $eq?data$ 的结点，使此结点指向原先链表哨兵结点的直接后继，再让哨兵结点的直接后继指向这个新创建的结点即可，不少读者应该会提出这样的疑问——如果此时只有哨兵结点呢？实际上下面的处理方法可以涵盖到这种情况。创建一个数据域为 $eq?data$ 的结点，使此结点指向原先链表哨兵结点的直接后继，也就是 $eq?null$ ，因为此情况下哨兵结点的直接后继就是 $eq?null$ ，然后更新哨兵结点的指针域，使指针域指向这个新创建的结点，并不会出现空引用或空指针等问题。假设链表中已经有 {1, 2, 3} 三个数据元素。现将元素插入链表头部，如下：

   /**
     * <h3>头插法，向链表头部插入元素</h3>
     *
     * @param data 插入结点的数据域
     */
    public void addFirst(int data) {
        head.next = new ListNode(data, head.next);
    }

5. 查找链表最后一个结点

这是一个私有化的工具方法，此方法并不会暴露在外部供使用者调用，我们会在执行一些操作时使用到这个方法。实现过程很简单，定义一个结点类型的临时变量 $eq?temp$ ，初始化为哨兵结点，通过循环让 $eq?temp$ 沿着链表的指针链前进，如果 $eq?temp$ 的指针域为空，意味着此时的已经到达了最后一个结点，因为在单链表中最后一个结点的指针域为空，直接返回 $eq?temp$ 即可。

/**
 * 查找链表最后一个结点
 * @return  最后一个结点
 */
private ListNode findLast() {
    ListNode temp = head;
    while (temp.next != null)
        temp = temp.next;
    return temp;
}

6. 尾插法插入结点

在实现了 $eq?findLast$ 查找链表最后一个结点的方法后，就可以实现尾插法插入结点方法了，与头插法大相径庭，先通过 $eq?findLast$ 方法查找到链表的最后一个结点，创建一个新结点，新结点的数据域为 $eq?data$ ，指针域为 $eq?null$ （虽然没有显式为指针域赋值，但是Java中的对象变量在未显式赋值时默认为 $eq?null$ ），由于此结点的指针域为 $eq?null$ ，说明此结点就是链表新的尾结点（最后一个结点），于是需要修改通过 $eq?findLast$ 方法得到的原先结点的指针域，使指针域指向这个新创建的结点。以上是一般情况，但是如果此时链表只有哨兵结点呢？可以直接调用之前实现好的头插法插入结点方法 $eq?addFirst$ ，因为在此情况下，尾插法与头插法实现的功能是相同的，但实际上没有必要，在实现 $eq?findLast$ 查找链表最后一个结点的方法时，我们初始化的 $eq?temp$ 变量就是哨兵结点，在此情况下根本不会经过下面的循环，进而直接将指向哨兵结点的 $eq?temp$ 结点变量返回到 $eq?addLast$ 方法中的 $eq?lastNodeRef$ 变量，不会出现空指针异常，后续直接修改指针域即可。

/**
 * 尾插法
 * @param data     尾插结点的数据域
 */
public void addLast(int data) {
//    if (head.next == null) {
//        addFirst(value);
//        return;
//    }
    ListNode lastNodeRef = findLast();
    lastNodeRef.next = new ListNode(data);
}

7. 根据索引查找结点

这是一个私有化方法，我们默认链表中结点索引从 $eq?0$ 开始，于是索引为 $eq?index$ 的结点即为链表中第 $eq?index%20+%201$ 个结点，首先需要对索引合法性判断，从逻辑结构上看，哨兵结点是索引为 $eq?0$ 的结点，但是哨兵结点中存储的值并没有作用，于是尚且认为首元结点是索引为 $eq?0$ 的结点；由于头指针指向哨兵结点，定义一个初始值为 $eq?-1$ 的计数器，执行下面的循环，如果计数器与索引相同，就会直接返回当前遍历的结点，如果退出循环，说明在计数器还没达到 $eq?index$ 时链表已经遍历完毕，进而可以说明此索引仍是一个不合法索引，最终抛出异常即可。

/**
 * 根据索引查找结点
 * @param index     索引
 * @return          索引对应结点
 */
private ListNode findNode(int index) {
    if (index < 0)
        throw illegalIndex(index);
    int cur = -1;
    for (ListNode indexNode = head; indexNode != null; indexNode = indexNode.next, cur++) {
        if (cur == index) return indexNode;
    }
    return illegalIndex(index);
}

8. 根据索引得到索引对应结点的数据

在实现了根据索引查找结点的 $eq?findNode$ 方法后再着眼于此需求，发现很简单，相信读者看到这里会产生疑问——在 $eq?findNode$ 方法中已经对 $eq?index$ 的合法性进行了判断，为什么还需要在 $eq?get$ 方法外部进行“额外”判断？实际上如果索引不合法，方法 $eq?findNode$ 会返回 $eq?null$ ，如果不进行额外判断，会出现空指针异常。

/**
 * 根据索引查找结点，返回结点的数据域
 * @param index     索引
 * @return          索引对应结点的数据域
 */
public int get(int index) {
    if (index < 0) {
        throw illegalIndex(index);
    }
    ListNode node = findNode(index);
    if (node == null)
        throw illegalIndex(index);
    return node.data;
}

9. 在指定索引处插入结点

前面提到，在链表中指定位置插入结点，只需要找到此位置对应结点的直接前驱，让新创建的结点的指针域指向直接前驱的指针域，然后更新直接前驱指针域，使指针域指向新结点即可。在代码中仍然需要对 $eq?index$ 合法性判断，之后找到索引 $eq?index%20-%201$ 对应的结点，然后更新指针域即可，如果 $eq?findNode%28index%20-%201%29$ 返回值为 $eq?null$ ，仍说明此索引是不合法的，抛出异常即可。假设在索引 2 处插入数据元素 7，如下：

/**
 * 在指定索引处插入结点，届时新插入的结点即为第 index 个结点
 * @param index     索引
 * @param data     结点数据域
 */
public void insert(int index, int data) {
    if (index < 0) {
        throw illegalIndex(index);
    }
    ListNode previous = findNode(index - 1);
    if (previous == null)
        throw illegalIndex(index);
    previous.next = new ListNode(data, previous.next);
}

10. 删除首元结点

前面提到，如果需要删除结点，只需要找到待删除结点的直接前驱，更改直接前驱指针域，将指针域指向待删除结点的直接后继即可， $eq?JVM$ 会通过垃圾回收机制将空引用的对象从堆内存中清除，回收堆内存。删除首元结点就是删除结点的一种特殊情况，有两种实现方案：直接将哨兵结点的指针域指向首元结点的指针（未注释代码）域或让首元结点变成哨兵结点（注释代码）。

/**
 * 删除首元结点
 */
public void removeFirst() {
    if (head.next == null)
        throw tips("当前链表为空，无法删除！");
//    head = head.next;
    head.next = head.next.next;
}

11. 根据索引删除结点

实现原理在上面提到了，不再赘述，我们这里只说空指针的处理。首先还是对 $eq?index$ 的合法性进行判断，然后直接调用之前实现好的根据索引查找结点方法，接收方法返回值，如果方法返回值为空，说明此 $eq?index%20-%201$ 索引是一个非法索引。进而说明在删除结点背景下 $eq?index$ 是一个非法索引，如果返回值不为空，但是返回值的后继为空，此时同样说明 $eq?index$ 是一个非法索引，因为在此情况下，方法返回值后继为空说明索引 $eq?index%20-%201$ 对应的结点是尾结点，即链表的最后一个结点，说明想要删除的结点是尾结点的后继，Are You Kidding Me?假设删除索引 2 处的结点，如下：

/**
 * 根据索引删除结点
 * @param index     索引
 */
public void remove(int index) {
    if (index < 0)
        throw illegalIndex(index);
    ListNode prev = findNode(index - 1);
    if (prev == null || prev.next == null) {
        throw illegalIndex(index);
    }
    prev.next = prev.next.next;
}

12. 迭代器遍历

Java中返回迭代器需要重写迭代器中的两个方法—— $eq?hasNext$ 和 $eq?next$ ，不再赘述。

@Override
public Iterator<Integer> iterator() {
    return new Iterator<Integer>() {
        ListNode temp = head.next;
        @Override
        public boolean hasNext() {
            return temp != null;
        }
        @Override
        public Integer next() {
            Integer value = temp.data;
            temp = temp.next;
            return value;
        }
    };
}

final：完整实现代码 & 单元测试

Java实现

import java.util.Iterator;
import java.util.function.Consumer;

/**<h3>单向链表（有哨兵结点）</h3>
 * @Author Arrebol
 * @Date 2025/1/11 20:37
 * @Project datastructure_algorithm
 * @Description：
 * 方法列表：
 * <ol>
 *     <li>头插法</li>
 *     <li>获取最后一个结点</li>
 *     <li>尾插法</li>
 *     <li>根据索引获取结点</li>
 *     <li>根据索引获取结点的数据</li>
 *     <li>指定位置插入指定元素</li>
 *     <li>删除首元结点</li>
 *     <li>根据索引删除</li>
 * </ol>
 */
public class SinglyLinkedListSentinel implements Iterable<Integer>{

    // 结点类
    private static class ListNode {
        int data;
        ListNode next;

        // 数据域为data，指针域为null
        public ListNode(int data) {
            this.data = data;
        }

        public ListNode(int data, ListNode next) {
            this.data = data;
            this.next = next;
        }
    }

    // 哨兵结点数据域默认值
    private final int SENTINEL_VALUE = 666;

    // 头指针最初为哨兵结点的引用
    private ListNode head = new ListNode(SENTINEL_VALUE);

    /**
     * <h3>头插法，向链表头部插入元素</h3>
     *
     * @param data 插入结点的数据域
     *             <br>
     *             方法中执行了如下步骤
     *             <ol>
     *                  <li>创建一个新的结点，结点指针域指向先前链表的首元结点（即 head）</li>
     *                  <li>由于是头插法，所以这个要插入的结点将成为链表新的首元结点，所以需要将头指针 head 指向这个结点</li>
     *                  <li>在此操作中，已经考虑到了最初链表为空的情况，此操作不会出现问题。</li>
     *             </ol>
     * head.next = new ListNode(data, head.next)：创建一个结点指向哨兵结点的直接后继，
     * 然后让哨兵结点直接后继指向新创建的结点，由于当前已经实现了比较通用的insert方法，
     * 故可以直接在头插方法中嵌套调用 insert(0, data)
     */
    public void addFirst(int data) {
        head.next = new ListNode(data, head.next);
    }

    /**
     * 尾插法
     * @param data     尾插结点的数据域
     *
     * 当链表为空时（只有哨兵结点），即 head.next == null，直接调用头插结点方法，
     * 实际是没有必要的，这种情况下根本不会执行 while 循环，直接执行最后的尾插语句，
     * 在哨兵结点的加持下，不需要做很多的额外判断。
     */
    public void addLast(int data) {
//        if (head.next == null) {
//            addFirst(value);
//            return;
//        }
        ListNode lastNodeRef = findLast();
        lastNodeRef.next = new ListNode(data);
    }

    /**
     * 查找链表最后一个结点
     * @return  最后一个结点
     *
     * 异常说明：如果链表为空，当然没有最后一个结点，抛出参数非法异常
     */
    private ListNode findLast() {
        ListNode temp = head;
        while (temp.next != null)
            temp = temp.next;
        return temp;
    }

    /**
     * 根据索引查找结点
     * @param index     索引
     * @return          索引对应结点
     */
    private ListNode findNode(int index) {
        if (index < 0)
            throw illegalIndex(index);
        int cur = -1;
        for (ListNode indexNode = head; indexNode != null; indexNode = indexNode.next, cur++) {
            if (cur == index) return indexNode;
        }
        throw illegalIndex(index);
    }

    /**
     * 根据索引查找结点，返回结点的数据域
     * @param index     索引
     * @return          索引对应结点的数据域
     */
    public int get(int index) {
        if (index < 0) {
            throw illegalIndex(index);
        }
        ListNode node = findNode(index);
        if (node == null)
            throw illegalIndex(index);
        return node.data;
    }

    /**
     * 在指定索引处插入结点，届时新插入的结点即为第 index 个结点
     * @param index     索引
     * @param data     结点数据域
     */
    public void insert(int index, int data) {
        if (index < 0) {
            throw illegalIndex(index);
        }
        ListNode previous = findNode(index - 1);
        if (previous == null)
            throw illegalIndex(index);
        previous.next = new ListNode(data, previous.next);
    }

    /**
     * 删除首元结点
     *
     * 两者执行效果相同：
     * <ol>
     *     <li>head = head.next：将头指针指向首元结点，也就是说此时的首元结点就变成了哨兵结点</li>
     *     <li>head.next = head.next.next：直接将首元结点断开链表的指针链，即首元结点变成了空引用，JVM可以进行垃圾回收</li>
     * </ol>
     */
    public void removeFirst() {
        if (head.next == null)
            throw tips("当前链表为空，无法删除！");
//        head = head.next;
        head.next = head.next.next;
    }

    /**
     * 根据索引删除结点
     * @param index     索引
     */
    public void remove(int index) {
        if (index < 0)
            throw illegalIndex(index);
        ListNode prev = findNode(index - 1);
        if (prev == null || prev.next == null) {
            throw illegalIndex(index);
        }
        prev.next = prev.next.next;
    }

    /**
     * 遍历链表
     * @param consumer  用户需要对获取到的元素执行的操作（sum、print、average etc.）
     */
    public void traverse(Consumer<Integer> consumer) {
        for (ListNode temp = head.next; temp != null; temp = temp.next)
            consumer.accept(temp.data);
    }

    @Override
    public Iterator<Integer> iterator() {
        return new Iterator<Integer>() {
            ListNode temp = head.next;
            @Override
            public boolean hasNext() {
                return temp != null;
            }

            @Override
            public Integer next() {
                Integer value = temp.data;
                temp = temp.next;
                return value;
            }
        };
    }

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

    private static RuntimeException tips(String tipStr) {
        return new RuntimeException(tipStr);
    }
}

import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.BeforeEach;
import org.junit.jupiter.api.Test;

import java.util.Iterator;

/**
 * @Author Arrebol
 * @Date 2025/1/11 19:12
 * @Project datastructure_algorithm
 * @Description：
 */
public class SinglyLinkedListSentinelTest {

    private SinglyLinkedListSentinel list;

    @BeforeEach
    public void setUp() {
        list = new SinglyLinkedListSentinel();
    }

    @Test
    public void testAddFirst() {
        list.addFirst(1);
        Assertions.assertEquals(1, list.get(0));
        list.addFirst(2);
        Assertions.assertEquals(2, list.get(0));
        Assertions.assertEquals(1, list.get(1));
    }

    @Test
    public void testAddLast() {
        list.addLast(1);
        Assertions.assertEquals(1, list.get(0));
        list.addLast(2);
        Assertions.assertEquals(1, list.get(0));
        Assertions.assertEquals(2, list.get(1));
    }

    @Test
    public void testGet() {
        list.addLast(1);
        list.addLast(2);
        Assertions.assertEquals(1, list.get(0));
        Assertions.assertEquals(2, list.get(1));
    }

    @Test
    public void testGetThrowsExceptionWhenIndexIsInvalid() {
        list.addLast(1);
        Assertions.assertThrows(IllegalArgumentException.class, () -> list.get(-1));
        Assertions.assertThrows(IllegalArgumentException.class, () -> list.get(1));
    }

    @Test
    public void testInsert() {
        list.addLast(1);
        list.addLast(3);
        list.insert(1, 2);
        Assertions.assertEquals(1, list.get(0));
        Assertions.assertEquals(2, list.get(1));
        Assertions.assertEquals(3, list.get(2));
    }

    @Test
    public void testInsertThrowsExceptionWhenIndexIsInvalid() {
        list.addLast(1);
        Assertions.assertThrows(IllegalArgumentException.class, () -> list.insert(-1, 2));
        Assertions.assertThrows(IllegalArgumentException.class, () -> list.insert(2, 2));
    }

    @Test
    public void testRemoveFirst() {
        list.addLast(1);
        list.addLast(2);
        list.removeFirst();
        Assertions.assertEquals(2, list.get(0));
    }

    @Test
    public void testRemoveFirstThrowsExceptionWhenListIsEmpty() {
        Assertions.assertThrows(RuntimeException.class, () -> list.removeFirst());
    }

    @Test
    public void testRemove() {
        list.addLast(1);
        list.addLast(2);
        list.addLast(3);
        list.remove(1);
        Assertions.assertEquals(1, list.get(0));
        Assertions.assertEquals(3, list.get(1));
    }

    @Test
    public void testRemoveThrowsExceptionWhenIndexIsInvalid() {
        list.addLast(1);
        Assertions.assertThrows(IllegalArgumentException.class, () -> list.remove(-1));
        Assertions.assertThrows(IllegalArgumentException.class, () -> list.remove(1));
    }

    @Test
    public void testTraverse() {
        list.addLast(1);
        list.addLast(2);
        list.addLast(3);
        StringBuilder result = new StringBuilder();
        list.traverse(result::append);
        Assertions.assertEquals("123", result.toString());
    }

    @Test
    public void testIterator() {
        list.addLast(1);
        list.addLast(2);
        list.addLast(3);
        Iterator<Integer> iterator = list.iterator();
        Assertions.assertTrue(iterator.hasNext());
        Assertions.assertEquals(1, iterator.next());
        Assertions.assertEquals(2, iterator.next());
        Assertions.assertEquals(3, iterator.next());
        Assertions.assertFalse(iterator.hasNext());
    }
}

C语言实现

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// 定义链表结点结构体
typedef struct ListNode {
    int data;
    struct ListNode* next;
} ListNode;

// 定义单向链表结构体（带哨兵结点）
typedef struct {
    ListNode* head; // 哨兵结点
} SinglyLinkedListSentinel;

// 初始化链表
SinglyLinkedListSentinel* createList() {
    SinglyLinkedListSentinel* list = (SinglyLinkedListSentinel*)malloc(sizeof(SinglyLinkedListSentinel));
    list->head = (ListNode*)malloc(sizeof(ListNode)); // 创建哨兵结点
    list->head->data = 666; // 哨兵结点数据域默认值
    list->head->next = NULL;
    return list;
}

// 释放链表内存
void freeList(SinglyLinkedListSentinel* list) {
    ListNode* current = list->head;
    while (current != NULL) {
        ListNode* temp = current;
        current = current->next;
        free(temp);
    }
    free(list);
}

// 头插法
void addFirst(SinglyLinkedListSentinel* list, int data) {
    ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
    newNode->data = data;
    newNode->next = list->head->next;
    list->head->next = newNode;
}

// 查找最后一个结点
ListNode* findLast(SinglyLinkedListSentinel* list) {
    ListNode* temp = list->head;
    while (temp->next != NULL) {
        temp = temp->next;
    }
    return temp;
}

// 尾插法
void addLast(SinglyLinkedListSentinel* list, int data) {
    ListNode* lastNode = findLast(list);
    ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
    newNode->data = data;
    newNode->next = NULL;
    lastNode->next = newNode;
}

// 根据索引查找结点
ListNode* findNode(SinglyLinkedListSentinel* list, int index) {
    if (index < 0) {
        return NULL; // 索引非法
    }
    int cur = -1;
    ListNode* temp = list->head;
    while (temp != NULL) {
        if (cur == index) {
            return temp;
        }
        temp = temp->next;
        cur++;
    }
    return NULL; // 索引超出范围
}

// 根据索引获取结点的数据
int get(SinglyLinkedListSentinel* list, int index) {
    ListNode* node = findNode(list, index);
    if (node == NULL) {
        printf("Index %d is invalid.\n", index);
        exit(1); // 索引非法，退出程序
    }
    return node->data;
}

// 在指定索引处插入结点
void insert(SinglyLinkedListSentinel* list, int index, int data) {
    if (index < 0) {
        printf("Index %d is invalid.\n", index);
        return;
    }
    ListNode* prev = findNode(list, index - 1);
    if (prev == NULL) {
        printf("Index %d is invalid.\n", index);
        return;
    }
    ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
    newNode->data = data;
    newNode->next = prev->next;
    prev->next = newNode;
}

// 删除首元结点
void removeFirst(SinglyLinkedListSentinel* list) {
    if (list->head->next == NULL) {
        printf("List is empty, cannot remove.\n");
        return;
    }
    ListNode* temp = list->head->next;
    list->head->next = temp->next;
    free(temp);
}

// 根据索引删除结点
void removeAt(SinglyLinkedListSentinel* list, int index) {
    if (index < 0) {
        printf("Index %d is invalid.\n", index);
        return;
    }
    ListNode* prev = findNode(list, index - 1);
    if (prev == NULL || prev->next == NULL) {
        printf("Index %d is invalid.\n", index);
        return;
    }
    ListNode* temp = prev->next;
    prev->next = temp->next;
    free(temp);
}

// 遍历链表
void traverse(SinglyLinkedListSentinel* list, void (*consumer)(int)) {
    ListNode* temp = list->head->next;
    while (temp != NULL) {
        consumer(temp->data);
        temp = temp->next;
    }
}

// 打印链表
void printList(SinglyLinkedListSentinel* list) {
    traverse(list, [](int data) { printf("%d ", data); });
    printf("\n");
}

int main() {
    // 创建链表
    SinglyLinkedListSentinel* list = createList();

    // 测试头插法
    addFirst(list, 1);
    addFirst(list, 2);
    printf("After addFirst: ");
    printList(list); // 输出: 2 1

    // 测试尾插法
    addLast(list, 3);
    addLast(list, 4);
    printf("After addLast: ");
    printList(list); // 输出: 2 1 3 4

    // 测试获取结点数据
    printf("Element at index 1: %d\n", get(list, 1)); // 输出: 1

    // 测试插入
    insert(list, 2, 5);
    printf("After insert: ");
    printList(list); // 输出: 2 1 5 3 4

    // 测试删除首元结点
    removeFirst(list);
    printf("After removeFirst: ");
    printList(list); // 输出: 1 5 3 4

    // 测试根据索引删除
    removeAt(list, 2);
    printf("After removeAt index 2: ");
    printList(list); // 输出: 1 5 4

    // 释放链表内存
    freeList(list);

    return 0;
}

总结

以上实现给出了带哨兵结点链表的Java实现方法，需要提出的是，在数据结构中结点与节点表达的意思是相同的，后续会总结LeetCode经典数据结构的题目。

标签：index,结点,简要,Java,list,next,链表,单链,ListNode
From： https://blog.csdn.net/ArrebolMKJ/article/details/145085332