单链表基础

链表中的元素不要求连续存放。每个结点既保存数据，也保存下一个结点的地址，这些地址像路标一样把分散在内存中的结点串接成一条线。

链表的核心思想

链表的特点是元素可以存储到内存的任意位置。每个元素通过指针变量保存下一个元素的地址，从而把一个个独立的存储单元连接起来。因为要同时保存数据和连接信息，所以每个结点至少包含两个域。

数据域

用来存储真正的数据元素，例如数值、字符，或者一条完整记录。

指针域

用来存储下一个结点的地址，让当前结点能够找到后继结点。

一条单链表如何串起来

单链表中，每个结点只有一个指针域，这个指针域指向下一个结点。最后一个结点没有后继，通常让它的指针域指向空地址。

任意位置 结点在内存中不必挨在一起，地址可以分散。

指针串接 每个结点靠指针域找到下一个结点。

单链表 每个结点只有一个指向后继的指针域。

单链表的结点

结点是什么

结点是链表的基本存储单元
每个结点至少包含数据域和指针域
数据域保存数据，指针域保存下一个结点地址

为什么叫单链表

一个结点只有一个指针域指向后继
访问时通常从头结点开始顺着 next 往后走
链尾结点的 next 通常为空，表示链表结束

注意：最简单的单链表结点通常是“一个数据域 + 一个指针域”。如果一个结点含有多个指针域，那通常是在讨论双向链表、循环链表或更复杂的链式结构。

C++ 代码实现示例

把代码放进页面后，适合放在“结点结构”之后，用来对应前面的图示：`data` 对应数据域， `next` 对应指针域，`head` 表示链表的起点。

结构对应关系 `struct Node` 就是结点结构，`data` 是数据域，`next` 是指针域，`head` 保存链表起点。

操作对应关系 `AddNode` 建立链表，`InsertNode` 插入结点，`DeleteNode` 删除结点，`SearchNode` 顺着指针查找。

教学提醒 这段代码适合展示指针思想，但作为最终范例需要再整理：建表会多申请一个空结点，删除时遍历指针没有正确前进，打印函数也可能漏掉尾结点。

single_linked_list.cpp

建表 / 插入 / 删除 / 查找

/**************************************************************** 
 * 描述: 单链表的C++实现
 * 作者: Alex Li
 * 日期: 2022-04-18 20:05:00
 * 最后编辑时间: 2024-04-16 12:26:31
****************************************************************/
#include <iostream>
using namespace std;
int n; // 全局变量n，用于存储节点数量

// 链表节点结构的定义
struct Node{
    int data;       // 节点的数据元素
    Node *next;     // 指向下一个节点的指针
};

Node *head = NULL; // 链表的头指针，初始设置为NULL

// 函数原型声明，便于清晰和组织
void PrintNode();

// 向链表中添加节点的函数
void AddNode(){
    cout << "请输入节点的数量: ";
    cin >> n; // 输入节点数量

    Node *newNode = new Node; // 在内存中分配一个新节点
    head = newNode; // 将头指针设置为新节点
    cout << "请输入节点的数据: ";
    int x; // 临时变量x，用于存储节点数据

    for (int i = 0; i < n; i++) {
        cin >> x; // 输入节点数据
        newNode->data = x; // 设置节点的数据
        newNode->next = new Node; // 为下一个节点分配新内存
        newNode = newNode->next; // 移动到下一个节点
        newNode->next = NULL; // 将新节点的next设置为NULL
    }
    PrintNode(); // 打印链表
}

// 在指定位置插入新节点的函数
void InsertNode(){
    int position, data; // 临时变量position和data，用于存储插入位置和数据
    cout << "请输入插入节点的位置和数据: ";
    cin >> position >> data; // 输入插入位置和数据
    Node *p = head, *newNode; // 指针p用于遍历链表，指针newNode用于创建新节点
    int j = 1; // 计数器j，用于遍历链表

    if(position == 0){
        // 在链表头部插入节点
        newNode = new Node;
        newNode->data = data;
        newNode->next = p;
        head = newNode;
    }
    else if (position <= n + 1){
        // 在链表中间或末尾插入节点
        while (j <= position - 1){
            p = p->next; // 移动到插入位置前一个节点
            j++;
        }
        newNode = new Node; // 创建新节点
        newNode->data = data;
        newNode->next = p->next; // 将新节点插入链表
        p->next = newNode;
        n++; // 更新节点数量
    } else {
        cout << "你输入的数字错误" << endl;
    }
    PrintNode(); // 打印更新后的链表
}

// 从链表中删除节点的函数
void DeleteNode(){
    int delete_position; // 临时变量delete_position，用于存储删除位置
    cout << "请输入要删除的节点位置: ";
    cin >> delete_position; // 输入删除位置
    Node *delete_node = head, *temp_delete_node; // 指针delete_node用于遍历链表，指针temp_delete_node用于临时存储节点

    if (delete_position == 1){
        // 删除头节点
        head = head->next; // 更新头指针
        delete delete_node; // 释放头节点的内存
    } else {
        for (int i = 1; i < delete_position - 1; i++) {
            temp_delete_node = delete_node->next; // 移动到删除位置前一个节点
        }
        temp_delete_node = delete_node->next; // 要删除的节点
        delete_node->next = temp_delete_node->next; // 将节点从链表中移除
        delete temp_delete_node; // 释放节点的内存
    }

    n--; // 更新节点数量
    PrintNode(); // 打印更新后的链表
}

// 在链表中查找具有给定值的节点的函数
void SearchNode() {
    int search_value; // 临时变量search_value，用于存储查找值
    cout << "请输入要查找的值: ";
    cin >> search_value; // 输入查找值

    Node *current = head; // 指针current用于遍历链表
    int position = 1; // 计数器position，用于记录节点位置

    while (current != NULL) {
        if (current->data == search_value) {
            cout << "值 " << search_value << " 在位置 " << position << " 找到" << endl;
            return; // 如果找到值则退出函数
        }
        current = current->next; // 移动到下一个节点
        position++; // 更新位置
    }
    cout << "值 " << search_value << " 在链表中未找到." << endl;
}

// 打印链表中所有节点的函数
void PrintNode(){
    Node *link = head; // 指针link用于遍历链表
    if (link == NULL){
        cout << "链表为空." << endl;
        return;
    }
    cout << "节点的数据是: ";
    do {
        cout << link->data << " "; // 打印节点数据
        link = link->next; // 移动到下一个节点
    } while (link->next != NULL);
    cout << endl;
}

int main(){
    AddNode();    // 调用函数添加节点
    InsertNode(); // 调用函数插入节点
    DeleteNode(); // 调用函数删除节点
    SearchNode(); // 调用函数查找节点
    return 0;
}

一句话记住单链表

存储方式 结点可以分散在内存中的任意位置。

基本结点 一个数据域保存数据，一个指针域保存下一个结点地址。

连接方式 通过 next 指针把一个个结点串接起来。

名称来源 每个结点只有一个后继指针，所以称为单链表。