在本文中，我们将基于 MySingleLinkedList 类，深入探讨单链表的实现，包括创建、插入、删除等核心操作，同时分享完整的代码示例。单链表是一种灵活的数据结构，适用于处理需要频繁插入和删除操作的场景，例如实现队列 📜、链式栈 🔥、循环队列 🔄 等。在计算机科学和实际开发中，链表结构被广泛应用。它不仅可以高效地处理插入和删除操作，还能够根据实际需求实现不同的链表结构。🚀本篇不仅涵盖了基本功能的代码展示，还补充了各种操作的实现细节和优化建议，旨在让读者能够全面掌握单链表的使用与实现。😊💡
目录
链表的基本结构 📊
代码实现 🖥️
讲解 🧑🏫
a. 链表的基本操作 🔧
1. 链表的创建 🛠️
动态创建链表 💻
讲解 💡
2. 链表的遍历 🔍
讲解 📚
3. 获取链表长度 🔢
讲解 🧐
b. 插入操作 ➕
1. 头插法 🏁
讲解 ⚡
2. 尾插法 🔚
讲解 📈
3. 任意位置插入 🔄
讲解 📘
c. 删除操作 ❌
1. 删除第一个匹配的节点
讲解 🧠
2. 删除所有匹配的节点
讲解 🔍
3. 清空链表
讲解 💬
总结 🌟
链表的基本结构 📊
单链表由节点（ListNode）组成，每个节点包含三个部分：
代码实现 🖥️
以下是链表的基础结构代码：
java">public class MySingleLinkedList {static class ListNode {public ListNode next;public int val;public ListNode prev;public ListNode(int val) {this.val = val;}}public ListNode head; // 头节点 🧑💻public ListNode last; // 尾节点 🎯
}
讲解 🧑🏫
- 每个节点由
ListNode类表示，包含数据域val和两个指针域next和prev。 head用于标记链表的起始位置，last标记链表的尾节点（可选）。- 相较于数组，链表在插入和删除操作中更具灵活性，但随机访问性能较差。链表的插入和删除操作无需移动其他元素，且通过指针的变动即可实现动态扩展，极大提高了操作效率。
链表的基本操作 🔧
1. 链表的创建 🛠️
手动链接节点的方式可以快速构建一个简单的链表。我们通过手动指定每个节点的连接方式，构造一个简单的链表。它适用于学习和理解链表基本结构：
java">public void createList() {ListNode listNode1 = new ListNode(1);ListNode listNode2 = new ListNode(2);ListNode listNode3 = new ListNode(3);ListNode listNode4 = new ListNode(4);ListNode listNode5 = new ListNode(5);this.head = listNode1;listNode1.next = listNode2;listNode2.next = listNode3;listNode3.next = listNode4;listNode4.next = listNode5;listNode5.next = null;
}
动态创建链表 💻
动态创建链表可以根据输入动态生成节点并构建链表，这样不仅增加了代码的灵活性，而且便于应对不同长度和结构的链表需求：
java">public void createListDynamic(int[] values) {if (values == null || values.length == 0) {return;}this.head = new ListNode(values[0]);ListNode cur = this.head;for (int i = 1; i < values.length; i++) {cur.next = new ListNode(values[i]);cur = cur.next;}
}
讲解 💡
- 动态连接节点：
node1.next = node2是构建链表的核心逻辑，通过该步骤，node1的next指向了node2，形成了节点之间的连接，链表的扩展就是通过这种方式完成的。🎯这种方式也适用于链表的动态增长，在需要时可以随时添加新的节点。 - 灵活性：动态方法使得链表的创建不再依赖固定的结构，可以根据用户的输入或其他需求动态生成节点，极大提高了代码的通用性。
2. 链表的遍历 🔍
通过遍历链表打印节点值，同时考虑链表为空时的情况，避免出现空指针异常。遍历链表时，需要从头节点开始依次访问每个节点：
java">public void display() {if (head == null) {System.out.println("链表为空");return;}ListNode cur = head;while (cur != null) {System.out.print(cur.val + " ");cur = cur.next;}System.out.println();
}
讲解 📚
- 动态连接节点：
node1.next = node2是构建链表、插入节点的基础，解决了链表动态扩展问题。 - 安全遍历链表：
while (cur != null)确保链表遍历过程可靠且高效，避免了指针错误或无限循环的问题。这样可以避免遍历时访问空指针或进入无限循环。⚠️ - 前进推进的流畅性：
cur = cur.next是链表遍历的核心语句，它使得cur从当前节点指向下一个节点，实现了链表的逐步推进。这个简洁的推进逻辑符合链表的递归结构特性，也使得代码更易于理解。😊
3. 获取链表长度 🔢
链表的长度可以通过遍历链表的所有节点来计算，直到达到链表的末尾：
java">public int size() {ListNode cur = head;int length = 0;while (cur != null) {length++;cur = cur.next;}return length;
}
讲解 🧐
- 递增计数：每遍历一个节点，计数器
length加 1，直至链表末尾，遍历过程确保了准确的节点统计。📊 - 优化建议：可以增加一个
size属性，在链表增删时动态更新，避免每次都需要遍历整个链表来计算长度。
插入操作 ➕
1. 头插法 🏁
java">public void addFirst(int val) {ListNode listNode = new ListNode(val);listNode.next = head;head = listNode;
}
讲解 ⚡
- 直接插入头部：将新节点的
next指向当前头节点，并更新head指针，使新节点成为链表的头节点。这种方式的时间复杂度为O(1)，是最为高效的插入方法，尤其适用于栈结构等需要优先级插入的场景。🔝
2. 尾插法 🔚
java">public void addLast(int val) {ListNode listNode = new ListNode(val);if (head == null) {head = listNode;return;}ListNode cur = head;while (cur.next != null) {cur = cur.next;}cur.next = listNode;
}
讲解 📈
- 遍历尾部：通过遍历找到尾节点，将其
next指向新节点。尾插法的时间复杂度是O(n)，如果链表较长，效率较低。⏳ - 优化建议：通过维护尾指针
last，可以直接将新节点插入尾部，避免每次遍历链表，提升效率。⚙️
3. 任意位置插入 🔄
java">public void addIndex(int index, int val) {if (index < 0 || index > this.size()) {System.out.println("索引不合法");return;} else if (index == 0) {this.addFirst(val);return;} else if (index == this.size()) {this.addLast(val);return;} else {ListNode cur = findIndexSubOne(index);ListNode node = new ListNode(val);node.next = cur.next;cur.next = node;}
}private ListNode findIndexSubOne(int index) {int count = 0;ListNode cur = head;while (count != index - 1) {cur = cur.next;count++;}return cur;
}
讲解 📘
- 定位前驱节点：通过
findIndexSubOne方法找到目标索引的前驱节点，便于在目标位置进行插入。 - 边界处理：针对索引为 0 或链表尾部的情况，分别调用头插法或尾插法。对其他位置的插入需要找到前驱节点，并调整指针，使得新节点被插入到正确的位置。🎯
删除操作 ❌
1. 删除第一个匹配的节点
java">public void remove(int val) {if (head == null) return;if (head.val == val) {head = head.next;return;}ListNode cur = head;while (cur.next != null) {if (cur.next.val == val) {cur.next = cur.next.next;return;}cur = cur.next;}
}
讲解 🧠
- 遍历匹配：从头开始遍历链表，查找目标值所在节点。找到匹配节点后，通过调整前后节点的
next指针，实现删除。 - 特殊情况：若目标值位于头节点，则直接更新
head指针，避免访问无效的null指针。⚠️
2. 删除所有匹配的节点
java">public void removeAllKey(int key) {ListNode cur = head;while (cur != null) {if (cur.val == key) {if (cur == head) {head = head.next;} else {cur.prev.next = cur.next;if (cur.next != null) {cur.next.prev = cur.prev;}}}cur = cur.next;}
}
讲解 🔍
3. 清空链表
java">public void clear() {ListNode cur = head;while (cur != null) {ListNode next = cur.next;cur.next = null;cur.prev = null;cur = next;}head = last = null;
}
讲解 💬
- 逐一断开连接：通过遍历依次清除每个节点的引用，确保没有悬挂引用。
- 释放内存：同时将头尾指针设为
null，彻底清空链表。🚀
总结 🌟
通过本文的讲解，我们实现了以下操作：
链表作为基础数据结构，适用于动态插入和删除频繁的场景，但其随机访问性能较差。由于链表无法通过索引直接访问特定位置的节点，需要从头节点开始逐一遍历，因此在随机访问频繁的场景中可能不如数组高效。在实际开发中，链表的灵活性可以解决许多复杂的数据管理问题。希望这篇文章能帮助您更好地理解单链表的实现，也为后续学习更复杂的链表结构（如双向链表和循环链表）打下基础！😊🎉
