当前位置：首页 > 其他 > 手把手教你理解单向链表：代码注释+新手入门指南

手把手教你理解单向链表：代码注释+新手入门指南

5个月前 (06-19)

一、简介和应用

单向链表是一种基础的数据结构，它由一系列节点组成，每个节点包含数据和指向下一个节点的指针。这种结构在数据存储和动态操作中非常实用，例如实现队列、栈，或在需要频繁插入、删除的场景中（如用户登录记录、任务列表等）。相比数组，链表无需连续内存空间，插入和删除效率更高，但无法随机访问元素。

二、特点和注意事项

特点：

1. 灵活性：节点动态分配，支持任意长度。

2. 简单性：单向指针，逻辑清晰，适合新手入门。

3. 操作高效：插入和删除节点只需修改指针，时间复杂度为O(1)（找到位置后）。

注意事项：

1.避免空指针操作：访问节点前需判断是否为nullptr。

2.内存管理：手动分配节点（如new node）后，需确保程序结束前释放（未实现删除功能时需注意）。

3.索引越界：插入、删除等操作需检查索引是否合法。

三、代码的实现步骤

1. 定义节点结构：包含数据data和指向下一个节点的指针next。

2. 创建链表类：linklist类以head指针指向链表头部。

3. 添加节点：从头部遍历到末尾，将新节点插入末尾。

4. 插入节点：根据索引找到目标位置的前一个节点，插入新节点并调整指针。

5. 删除节点：找到目标位置前一个节点，跳过要删除的节点并连接后续节点。

6. 修改和查询：通过索引遍历到目标节点，修改数据或返回数据。

7. 反转链表：提供递归和非递归两种方法，改变指针方向形成逆序链表。

四、代码与注释

#include <iostream>
using namespace std;

// 定义节点结构
struct node {
    int data = 0;          // 节点存储的数据（默认值0）
    node* next = nullptr;  // 指向下一个节点的指针
};

class linklist {
public:
    node* head = new node;  // 链表头部节点（初始化为空节点）

    // 1. 添加节点到末尾
    void add(int data) {
        node* tmp = head;   // 临时指针从头部开始遍历
        while (tmp->next!= nullptr) {  // 循环直到末尾
            tmp = tmp->next;
        }
        node* datanode = new node;  // 创建新节点
        datanode->data = data;     // 赋值数据
        tmp->next = datanode;      // 将末尾指针指向新节点
    }

    // 2. 在指定索引插入节点
    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;        // 前一个节点指向新节点
    }

    // 3. 删除指定索引的节点
    void deleteNode(int idx) {
        node* tmp = head;
        for (int i = 0; i < idx; i++) {
            tmp = tmp->next;
        }
        tmp->next = tmp->next->next;  // 跳过要删除的节点，连接后续节点
    }

    // 4. 修改指定索引节点的数据
    void change(int data, int idx) {
        node* tmp = head;
        for (int i = 0; i <= idx; i++) {  // 注意：i <= idx，因为要访问到目标节点
            tmp = tmp->next;
        }
        tmp->data = data;
    }

    // 5. 查询指定索引的节点数据
    int select(int idx) {
        node* tmp = head;
        for (int i = 0; i <= idx; i++) {
            tmp = tmp->next;
        }
        return tmp->data;  // 返回目标节点的数据
    }

    // 6. 反转链表（递归方法）
    node* reverse(node* head) {
        if (head == nullptr || head->next == nullptr) {  // 递归终止条件：空链表或只有一个节点
            return head;
        }
        node* newHead = reverse(head->next);            // 递归处理后续节点
        head->next->next = head;                       // 原头部的下一个节点指向原头部
        head->next = nullptr;                          // 原头部指向空（新链表的末尾）
        linklist::head->next = newHead;                // 更新链表头部指针（注意：此处可能影响原链表结构，需谨慎使用）
        return newHead;
    }

    // 7. 反转链表（迭代方法）
    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;                   // 更新当前节点
            b = tmp;                 // 更新下一个节点
        }
        linklist::head->next = a;     // 更新链表头部指针
        return a;
    }
};