单链表入门

单链表是编程入门必学的线性数据结构，相比于数组，它无需连续的内存空间，插入或者删除操作无需移动大量元素，是理解指针和链式存储的核心载体，本文将会用简单的代码实现单链表的核心功能，适合零基础的新手快速上手并理解。

1、单链表的核心概念

单链表是若干个节点串联而成，每个节点包含两部分
数据域：存储实际数据
指针域：存储下一个结点的内存地址，最后一个结点的指针域为nullptr（空指针），表示链表结束
链表的访问方式为顺序访问—-必须从头节点开始，通过指针逐个遍历，不能像数组一样随机访问（直接通过下标访问取值）

2、极简的单链表实现

以下代码仅仅保留单链表最核心的三个功能，尾插添加节点，遍历输出，删除指定值

#include <iostream>
using namespace std;

// 1. 定义单链表节点结构体
// 每个节点包含数据域和指针域
struct Node {
int data; // 数据域：存储整型数据（可根据需求改为其他类型）
Node* next; // 指针域：指向链表中下一个节点的指针

// 节点构造函数：创建节点时直接初始化数据和指针
// 避免每次创建节点都手动赋值，简化代码
Node(int val) : data(val), next(nullptr) {}
};

// 2. 尾插法添加节点（核心功能1）
// 功能：在链表的末尾添加新节点
// 参数：head为链表头节点的引用（需修改头节点，故用引用），val为要添加的数据
void addNode(Node*& head, int val) {
// 1. 创建新节点，初始化数据为val，指针为空
Node* newNode = new Node(val);

// 2. 处理空链表：如果头节点为空，新节点直接作为头节点
if (head == nullptr) {
head = newNode;
return;
}

// 3. 非空链表：遍历到链表最后一个节点
Node* cur = head; // 定义遍历指针，从头节点开始
// 循环条件：当前节点的下一个节点不为空（未到末尾）
while (cur->next != nullptr) {
cur = cur->next; // 指针后移，指向下一个节点
}
// 4. 将最后一个节点的指针指向新节点，完成插入
cur->next = newNode;
}

// 3. 遍历链表并输出（核心功能2）
// 功能：从头节点开始，逐个输出所有节点的数值
// 参数：head为链表头节点（仅读取，无需修改，故不用引用）
void traverse(Node* head) {
// 处理空链表
if (head == nullptr) {
cout << "当前链表为空，无数据可输出！" << endl;
return;
}

// 非空链表：逐个遍历输出
cout << "链表数据：";
Node* cur = head; // 遍历指针从头节点开始
while (cur != nullptr) {
cout << cur->data << " "; // 输出当前节点数据
cur = cur->next; // 指针后移
}
cout << endl; // 换行，优化输出格式
}

// 4. 删除指定值的节点（核心功能3）
// 功能：删除链表中第一个值为val的节点
// 参数：head为链表头节点的引用（可能修改头节点，故用引用），val为要删除的数据
void deleteNode(Node*& head, int val) {
// 1. 处理空链表：直接返回，无需操作
if (head == nullptr) {
cout << "链表为空，无法删除节点！" << endl;
return;
}

// 2. 处理头节点就是目标节点的情况
if (head->data == val) {
Node* temp = head; // 暂存头节点（用于释放内存）
head = head->next; // 头节点后移，指向原第二个节点
delete temp; // 释放原头节点内存，避免内存泄漏
cout << "已删除头节点（值为" << val << "）" << endl;
return;
}

// 3. 处理中间/末尾节点：找到目标节点的前驱节点
Node* cur = head; // 遍历指针从头节点开始
// 循环条件：下一个节点不为空，且下一个节点的值不等于目标值
while (cur->next != nullptr && cur->next->data != val) {
cur = cur->next; // 指针后移
}

// 4. 判断是否找到目标节点
if (cur->next == nullptr) {
cout << "未找到值为" << val << "的节点，删除失败！" << endl;
} else {
Node* temp = cur->next; // 暂存待删除节点
cur->next = cur->next->next; // 前驱节点跳过待删除节点，指向其后继节点
delete temp; // 释放待删除节点内存
cout << "已删除值为" << val << "的节点" << endl;
}
}

// 主函数：测试单链表所有功能
int main() {
Node* head = nullptr; // 初始化头节点为空，代表空链表

// 1. 添加节点：尾插1、2、3
addNode(head, 1);
addNode(head, 2);
addNode(head, 3);
traverse(head); // 输出：链表数据：1 2 3

// 2. 删除节点：删除值为2的节点
deleteNode(head, 2);
traverse(head); // 输出：链表数据：1 3

// 3. 测试删除不存在的节点
deleteNode(head, 5); // 输出：未找到值为5的节点，删除失败！

// 4. 测试删除头节点
deleteNode(head, 1);
traverse(head); // 输出：链表数据：3

return 0;
}

3、运行结果

4、核心逻辑解析

节点定义：用结构体封装数据域和指针域，构造函数简化节点初始化，避免重复写赋值代码
尾插添加：核心是找到最后一个节点，通过遍历指针cur，等到cur->next为空，再将新的节点挂到末尾
遍历输出：从头结点开始，逐个反复问加点并输出数据，直到指针为空
删除节点，分三种情况处理（空链表，删除头节点，删除中间末尾节点），重点是“找到前驱节点”，并记得释放内存避免泄露

5、总结

单链表的核心是指针操作，所有功能都围绕着遍历“指针找目标节点”展开
实现时必须处理Nullptr，否则会导致程序崩溃
本文极简代码覆盖了单链表的核心场景，新手掌握后可扩展头插，指定位置插入，清空链表等功能