单向链表入门指南：从零开始理解数据结构基础

10小时前其他资料25

一、简介和应用

单向链表是一种基础的数据结构，它由一系列节点组成，每个节点包含数据和指向下一个节点的指针。与数组不同，链表中的元素在内存中不是连续存储的，而是通过指针链接在一起。

‌应用场景‌：

1.实现文件系统目录结构
2.浏览器历史记录管理
3.音乐播放器的播放列表
4.内存管理中的空闲内存块管理
5.实现栈和队列等高级数据结构

单向链表特别适合需要频繁插入和删除操作的场景，因为它的时间复杂度是O(1)，而数组在这些操作上通常是O(n)。

二、特点和注意事项

‌特点‌：

1.动态大小：链表可以根据需要动态增长或缩小
2.高效插入/删除：在已知位置插入或删除节点非常高效
3.内存利用率：不需要预先分配连续内存空间
4.实现简单：基本操作逻辑清晰易懂

‌注意事项‌：

1.访问效率：随机访问效率低，需要从头遍历
2.内存开销：每个节点需要额外空间存储指针
3.边界条件：处理头节点和尾节点时需要特别注意
4.内存管理：需要手动管理节点的内存分配和释放
5.循环引用：注意避免形成循环链表（除非有意为之）

三、实现步骤解析

‌1.定义节点结构‌：创建包含数据和next指针的结构体
‌2.初始化链表‌：创建头节点作为链表的起点
‌3.实现基本操作‌：

添加节点：遍历到链表末尾并添加新节点
插入节点：找到指定位置并调整指针
删除节点：绕过要删除的节点并释放内存
修改节点：定位到指定节点并修改数据
查询节点：遍历到指定位置并返回数据

‌4.实现反转功能‌：

递归反转：使用递归调用来反转链表
迭代反转：使用三个指针逐步反转链表

四、完整代码和注释

#include<iostream>
using namespACe std;

// 定义链表节点结构体
struct node
{
    int data=0;       // 节点存储的数据，默认为0
    node* next=nullptr; // 指向下一个节点的指针，默认为空
};

// 定义链表类
class linklist
{
public:
    node* head=new node; // 创建头节点
    
    // 在链表末尾添加新节点
    void add(int data)
    {
        node* tmp = head; // 从头节点开始
        while (tmp->next != nullptr) // 遍历到最后一个节点
        {
            tmp = tmp->next;
        }
        node* datanode = new node; // 创建新节点
        datanode->data = data;     // 设置新节点数据
        tmp->next = datanode;      // 将新节点链接到链表末尾
    }
    
    // 在指定位置插入新节点
    void insert(int data, int idx)
    {
        node* datanode = new node; // 创建新节点
        datanode->data = data;     // 设置新节点数据
        node* tmp = head;          // 从头节点开始
        for (int i = 0;i < idx;i++) // 移动到要插入位置的前一个节点
        {
            tmp = tmp->next;
        }
        datanode->next = tmp->next; // 新节点指向原位置节点
        tmp->next = datanode;       // 前一个节点指向新节点
    }
    
    // 删除指定位置的节点
    void deleteNode(int idx)
    {
        node* tmp = head;          // 从头节点开始
        for (int i = 0;i < idx;i++) // 移动到要删除位置的前一个节点
        {
            tmp = tmp->next;
        }
        tmp->next = tmp->next->next; // 绕过要删除的节点
        // 注意：这里应该释放被删除节点的内存
    }
    
    // 修改指定位置节点的数据
    void change(int data, int idx)
    {
        node* tmp = head;          // 从头节点开始
        for (int i = 0;i <= idx;i++) // 移动到目标节点
        {
            tmp = tmp->next;
        }
        tmp->data = data;          // 修改节点数据
    }
    
    // 查询指定位置节点的数据
    int select(int idx)
    {
        node* tmp = head;          // 从头节点开始
        for (int i = 0;i <= idx;i++) // 移动到目标节点
        {
            tmp = tmp->next;
        }
        return tmp->data;          // 返回节点数据
    }
    
    // 递归方式反转链表
    node* reverse(node* head)
    {
        // 基本情况：空链表或只有一个节点
        if (head == nullptr or head->next == nullptr)
        {
            return head;
        }
        // 递归反转剩余部分
        node* newHead = reverse(head->next);
        // 将当前节点连接到反转后的链表末尾
        head->next->next = head;
        head->next = nullptr;
        // 更新头节点指针
        linklist::head->next = newHead;
        return newHead;
    }
    
    // 迭代方式反转链表
    node* otherReverse(node* head)
    {
        node* a = head;       // 前一个节点指针
        node* b = a->next;    // 当前节点指针
        a->next = nullptr;    // 第一个节点变为最后一个节点
        while (b)             // 遍历整个链表
        {
            node* tmp = b->next; // 保存下一个节点
            b->next = a;      // 反转指针方向
            a = b;            // 移动a指针
            b = tmp;          // 移动b指针
        }
        // 更新头节点指针
        linklist::head->next = a;
        return a;
    }
};