链表是一种在物理上非连续的存储结构。在单向链表中，每一个节点都是一个对象，其中包含了数据和引用两部分，通过引用指向下一个节点。这种结构相比线性存储结构要复杂，并且由于增加了指针(引用)域导致内存开销更大，但它不像数组那样需要预先知道数据规模，可以充分利用计算机的内存空间。

首先我们和ArrayList一样，将MySingleList单独定义为一个Java文件，然后每一个结点我们将它定义成一个静态内部类，这样就方便我们访问结点的成员，，还是和ArrayList一样，我们再定义一个Test类用来测试我们的单链表，写一个函数可以测试一下

1. MySingleList的大概实现框架

public class MySingleList {
    // 静态内部类ListNode，表示链表的节点
    static class ListNode {
        public int value; // 节点存储的数据
        public ListNode next; // 指向下一个节点的引用

        // 构造函数，初始化节点的值
        public ListNode(int value) {
            this.value = value;
        }
    }

    public ListNode head; // 链表的头节点

    // 构造函数，初始化链表为一个空链表
    public MySingleList() {
        this.head = null;
    }

    // 创建一个简单的链表用于演示
    public void createList() {
        // 创建三个节点
        ListNode listNode1 = new ListNode(23);
        ListNode listNode2 = new ListNode(22);
        ListNode listNode3 = new ListNode(23);
 
        // 链接这些节点，形成链表
        listNode1.next = listNode2;
        listNode2.next = listNode3;
 
        // 将链表的头节点指向第一个节点
        this.head = listNode1;
    }

    // 在链表头部添加一个新节点
    public void addFirst(int data){}

    // 在链表尾部添加一个新节点
    public void addLast(int data){}
    
    // 在链表的指定位置添加一个新节点
    public void addIndex(int index, int data){}
    
    // 检查链表中是否包含指定的值
    public boolean contains(int key){return false;}
    
    // 从链表中删除第一次出现的指定值的节点
    public void remove(int key){}
    
    // 从链表中删除所有出现的指定值的节点
    public void removeAllKey(int key){}
    
    // 返回链表中的节点数量
    public int size(){return -1;}
    
    // 打印链表中的所有值
    public void display(){}
    
    // 清空链表
    public void clear(){}
}

2. addFirst--头插

addFirst方法用于在单链表的头部插入一个新的节点。每个节点包括两部分：数据部分和指向下一个节点的引用。当一个新的节点被添加到链表的头部时，这个新节点的next引用指向原先的头节点，然后更新链表的头节点引用为这个新节点。

public void addFirst(int data) {
    // 创建一个新的节点，节点的数据部分为传入的data
    ListNode node = new ListNode(data);
    // 将新节点的next引用指向当前的头节点
    // 如果链表为空（即head为null），新节点的next将是null
    node.next = head;
    // 更新链表的头节点为新创建的节点
    head = node;
}

头插没啥细节点，以上图做辅助理解，我就不多赘述了，，

---

3. addLast--尾插

addLast方法用于在单链表的尾部添加一个新的节点。根据单链表是否为空，这个操作可以分为两种情况处理：链表为空时直接将新节点设为头节点；链表不为空时，需要遍历到链表的最后一个节点，然后将其next引用指向新节点。

// 尾插法实现，在链表尾部添加一个新节点
public void addLast(int data) {
    // 创建一个新节点，节点值为传入的data
    ListNode node = new ListNode(data);
    
    // 1. 链表为空的情况
    if(this.head == null) {
        // 如果链表为空，直接将新节点设置为头节点
        this.head = node;
    } else {
        // 2. 链表不为空的情况
        // 初始化一个指针cur，用于遍历链表，从头节点开始
        ListNode cur = this.head;
        // 遍历链表找到最后一个节点，即cur.next为null的节点
        while(cur.next != null) {
            cur = cur.next; // 移动到下一个节点
        }
        // 将最后一个节点的next引用指向新创建的节点，从而实现在尾部添加节点
        cur.next = node;
    }
}

这里要注意链表为空的时候，只需要将head指向node即可；

---

4. addIndex--任意位置插入

addIndex方法用于在单链表的任意有效位置插入一个新节点。该方法首先检查插入位置的合法性，然后根据插入位置是头部、中间位置还是尾部进行相应的插入操作。

// 在链表的指定index位置插入新的数据节点
public void addIndex(int index, int data) throws MySingleListIndexOutOfException {
    // 1. 检查插入位置是否合法
    checkAddIndex(index);

    // 创建新节点
    ListNode node = new ListNode(data);

    // 2. 如果链表为空，直接将新节点设置为头节点
    if(this.head == null) {
        this.head = node;
        return;
    }

    // 3. 如果插入位置是0，即头插法
    if(index == 0) {
        addFirst(data);
        return;
    }

    // 4. 找到插入位置的前一个节点
    ListNode cur = findAddIndexSubOne(index);

    // 5. 插入新节点
    node.next = cur.next; // 新节点的next指向原位置的节点
    cur.next = node;      // 前一个节点的next指向新节点
}

// 检查插入位置的合法性
private void checkAddIndex(int index) {
    if(index < 0 || index > this.size()) {
        throw new MySingleListIndexOutOfException("任意位置插入时，index不合法！");
    }
}

// 找到待插入位置的前一个节点
private ListNode findAddIndexSubOne(int index) {
    ListNode cur = this.head;
    // 遍历链表直到找到待插位置的前一个节点
    while(index - 1 != 0) {
        cur = cur.next;
        index--;
    }
    return cur;
}

实现逻辑

1. 检查插入位置合法性：通过checkAddIndex方法验证给定的插入位置index是否在链表的有效范围内，即是否在0到链表长度之间。如果位置不合法，则抛出自定义异常MySingleListIndexOutOfException。
2. 创建新节点：基于给定的数据data创建一个新的ListNode节点。
3. 链表为空时的处理：如果链表当前为空，则直接将新节点设置为头节点。
4. 头部插入：如果index为0，调用addFirst方法在链表头部插入新节点。
5. 中间位置和尾部插入：
   • 使用findAddIndexSubOne方法找到待插入位置的前一个节点cur。
   • 将新节点的next指针指向cur的下一个节点，然后将cur的next指针指向新节点。这样新节点就被插入到了指定的位置。

---

5. contains--查找是否包含关键字key

contains方法用于检查单链表中是否存在值为key的节点。该方法通过遍历链表，并逐个比较节点的值是否等于key来实现。如果找到匹配的节点，则方法返回true；如果遍历完成都没有找到，或链表为空，则返回false。

public boolean contains(int key) {
    // 检查链表是否为空
    if(this.head == null) {
        // 如果头节点为null，表示链表为空，打印提示信息并返回false
        System.out.println("链表为空！");
        return false;
    }
    // 初始化一个指针cur，用于遍历链表，从头节点开始
    ListNode cur = this.head;
    // 遍历链表，直到cur为null，即遍历到链表的末尾
    while(cur != null) {
        // 检查当前节点的值是否等于key
        if(cur.value == key) {
            // 如果找到值为key的节点，返回true
            return true;
        }
        // 移动cur到下一个节点，继续遍历
        cur = cur.next;
    }
    // 如果遍历完整个链表都没有找到值为key的节点，返回false
    return false;
}

实现逻辑

1. 检查链表是否为空：首先判断链表是否为空，即头节点head是否为null。如果链表为空，则直接返回false，表示链表中不存在任何节点，因此也不可能包含值为key的节点。
2. 遍历链表：如果链表不为空，则使用一个循环遍历链表。循环的继续条件是当前遍历到的节点cur不为null。
3. 比较节点值：在遍历过程中，对每个节点的值cur.value与key进行比较。如果找到一个节点的值等于key，则说明链表中存在值为key的节点，方法返回true。
4. 处理未找到的情况：如果遍历到链表的末尾都没有找到值等于key的节点，或链表为空，则方法返回false，表示链表中不包含值为key的节点。

---

6. remove--删除第一次出现的key

remove方法用于删除单链表中第一次出现的值为key的节点。该方法分几个步骤处理：首先检查链表是否为空；然后特别处理删除头节点的情况；最后处理删除非头节点的情况。

// 删除第一次出现关键字为key的节点
public void remove(int key) {
    // 1.判断链表是否为空
    if(this.head == null) {
        System.out.println("链表为空，不能删除！");
        return;
    }

    // 2.特别处理头节点是要删除节点的情况
    if(this.head.value == key) {
        this.head = this.head.next; // 将头节点指向下一个节点，即删除了原头节点
        return;
    }

    // 3.删除非头节点
    ListNode cur = this.head;
    // 调用removeSubOne查找要删除的节点的前一个节点
    cur = removeSubOne(key, cur);
    // 如果没找到要删除的节点，提示信息并返回
    if(cur == null) {
        System.out.println("链表中没有这个元素！");
        return;
    }
    // 执行删除操作，将前一个节点的next指向要删除节点的下一个节点
    cur.next = cur.next.next;
}

// 辅助方法：查找要删除节点的前一个节点
private ListNode removeSubOne(int key, ListNode cur) {
    // 遍历链表，直到找到要删除节点的前一个节点
    while(cur.next != null) {
        if(cur.next.value == key) {
            return cur; // 返回要删除节点的前一个节点
        }
        cur = cur.next; // 继续遍历
    }
    // 如果遍历完整个链表都没有找到，返回null
    return null;
}

实现逻辑

1. 链表为空检查：首先检查链表是否为空，如果为空，则输出提示信息并终止删除操作。
2. 删除头节点：如果头节点就是要删除的节点（即头节点的值等于key），则直接将头节点更新为原头节点的下一个节点，从而达到删除头节点的效果。
3. 删除非头节点：
   • 使用辅助方法removeSubOne查找到要删除节点的前一个节点。该方法通过遍历链表，直到找到其next节点的值等于key。
   • 如果找到了要删除的节点的前一个节点，则将该前一个节点的next指向要删除节点的下一个节点，从而实现删除操作。
   • 如果未找到（removeSubOne返回null），则输出提示信息，表示链表中没有这个元素。

---

7. removeAllkey--删除所有key

7.1 方案一

removeAllKey1方法是用于删除单链表中所有值为key的节点的第一种实现。这种方法利用了之前实现的removeSubOne辅助方法，通过反复调用以删除每个值为key的节点，包括头节点和中间节点。

// 方法一: 时间复杂度O(N^2) - 通过反复调用removeSubOne方法删除所有值为key的节点
public void removeAllKey1(int key) {
    // 1.判断链表是否为空
    if(this.head == null) {
        System.out.println("链表为空，不能删除！");
        return;
    }
    
    // 2.处理中间和尾巴，反复调用removeSubOne删除所有值为key的节点
    ListNode cur = this.head;
    while(cur != null) {
        cur = removeSubOne(key,cur); 
        if(cur != null) {
            cur.next = cur.next.next; // 删除当前cur指向的下一个节点
        }
    }
    
    // 3.处理头节点，如果头节点的值为key，更新头节点
    if(this.head.value == key) {
        this.head = this.head.next;
    }
}

// 辅助方法：查找要删除节点的前一个节点
private ListNode removeSubOne(int key, ListNode cur) {
    // 遍历链表，直到找到要删除节点的前一个节点
    while(cur.next != null) {
        if(cur.next.value == key) {
            return cur; // 返回要删除节点的前一个节点
        }
        cur = cur.next; // 继续遍历
    }
    // 如果遍历完整个链表都没有找到，返回null
    return null;
}

实现逻辑：

1. 链表空检查：如果链表为空，则打印提示信息并结束方法执行。
2. 删除中间和尾部节点：通过循环遍历链表，利用removeSubOne查找每个值为key的节点，并删除它。removeSubOne方法返回值为key的节点的前一个节点，允许对后续节点进行删除操作。
3. 删除头节点：在处理完中间和尾部节点之后，如果链表的头节点值也为key，则更新头节点为下一个节点，实现头节点的删除。

7.1 方案二

removeAllKey2是另一种实现，通过只遍历链表一遍来删除所有值为key的节点，具有更高的效率（时间复杂度O(N)）。

// 方法二: 只遍历一遍链表, 时间复杂度O(N)
// 使用前后指针解决删除所有值为key的节点问题
public void removeAllKey2(int key){
    // 处理链表为空的情况
    if(head == null) {
        return;
    }

    ListNode pre = head; // 前指针
    ListNode cur = head.next; // 游标，后指针

    // 遍历链表，使用前后指针进行节点删除
    while(cur != null) {
        if(cur.value == key) {
            // 删除当前cur节点，前指针不动
            pre.next = cur.next;
            cur = cur.next;
        } else {
            // 不删除当前cur节点，前后指针同时向后移动
            pre = cur;
            cur = cur.next;
        }
    }

    // 最后处理头节点为key的情况
    if(head.value == key) {
        head = head.next;
    }
}

实现逻辑：

1. 链表空检查：首先检查链表是否为空，为空则直接返回。
2. 使用前后指针：定义两个指针，pre作为前指针指向当前考察节点的前一个节点，cur作为游标指针指向当前考察节点。遍历链表时，根据cur指针所指节点的值与key比较来决定是否删除该节点。
3. 节点删除操作：如果cur指针所指节点的值等于key，则执行删除操作，将pre指针的next更新为cur的next，即跳过cur节点。如果不等于key，则同时移动pre和cur指针向后遍历。
4. 处理头节点：遍历结束后，单独检查头节点是否为key。如果是，更新头节点为原头节点的下一个节点。

7.3 图示如下

下面这些方法是单链表的常用操作，包括获取链表长度、打印链表中的所有元素和清空链表。

8. size() 方法

• 初始化一个从头节点开始的遍历指针cur和计数器count。
• 遍历链表，每遍历到一个节点，计数器加1。
• 遍历结束时，计数器的值即为链表的长度。

// 得到单链表的长度
public int size() {
    ListNode cur = this.head; // 使用一个临时指针cur遍历链表，从头节点开始
    int count = 0; // 初始化计数器为0
    while(cur != null) { // 当cur不为null时，表示链表尚未结束
        count++; // 对于链表中的每个节点，计数器加1
        cur = cur.next; // 移动cur到下一个节点
    }
    return count; // 返回计数器的值，即链表的长度
}

9. display() 方法

• 使用临时指针cur遍历整个链表。
• 对于每个节点，打印其存储的值。
• 保持头指针head不变，确保链表结构不被破坏。

// 打印单链表
public void display() {
    ListNode cur = this.head; // 同样使用一个临时指针cur从头节点开始遍历链表
    while(cur != null) { // 遍历链表直到链表结束
        System.out.print(cur.value + " "); // 打印当前节点的值
        cur = cur.next; // 移动到下一个节点
    }
    System.out.println(); // 打印完所有节点后换行
}

10. clear() 方法

• 将头指针head设置为null，从而断开链表中所有节点之间的链接。
• 在Java中，被断开链接的节点将由垃圾回收器（GC）回收，因此不需要显式删除每个节点。

// 清除单链表
public void clear() {
    this.head = null; // 直接将头节点设置为null，逻辑上清空整个链表
}

遍历链表的结束条件

• 在size()和display()方法中，遍历链表的循环结束条件是当前遍历指针cur为null。这保证了即使在链表为空的情况下，方法也能正确执行，并且在执行过程中，头指针head保持不变，确保了链表的结构在遍历后仍然完整。

这里说说清除函数，我这种方式是比较暴力，也可以用温柔的方式：

用cur结点保存head的next，然后将head的val和next不断置为0或空，然后两个"指针"不断往后走

11.递归打印链表

// 递归打印链表
public void disPlay(ListNode pHead) {
    if(pHead == null) { // 基础情况：如果当前节点为null，表示链表遍历结束，直接返回
        return;
    }
    // 递归调用，先递归打印当前节点之后的所有节点
    disPlay(pHead.next);
    // 在递归返回的过程中，打印当前节点的值
    System.out.println(pHead.val + " ");
}

实现逻辑

• 递归方法以pHead为起点遍历链表。
• 通过递归调用，先访问链表的末尾，然后在递归返回的过程中，从链表末尾向头部依次打印每个节点的值。
• 这种方法实现了链表的逆序打印，因为它最先打印的是链表的最后一个节点。

12. 使用栈打印链表

// 用栈打印链表
public void disPlay2(ListNode pHead) {
    Stack<ListNode> stack = new Stack<>(); // 创建一个栈来存储链表中的所有节点
    ListNode cur = pHead; // 使用cur遍历链表
    while (cur != null) { // 遍历链表
        stack.push(cur); // 将每个节点压入栈中
        cur = cur.next; // 移动到下一个节点
    }
    // 遍历栈，逐个弹出并打印节点的值
    while (!stack.isEmpty()) {
        ListNode top = stack.pop(); // 弹出栈顶节点
        System.out.println(top.val + " "); // 打印节点的值
    }
}

实现逻辑

• 使用栈存储整个链表的节点，利用栈先进后出的特性。
• 先将链表的所有节点按顺序压入栈中，这样栈顶的节点就是链表的最后一个节点。
• 通过逐个弹出栈中的节点并打印，实现链表的逆序打印。