GESP 6级 · 链表概念

📖概念讲解

【考点 · 6级】链表概念 —— 属于数据结构基础，是理解动态数据组织的核心。

【说人话】

数组是"一排连续的格子"，链表是"一串用绳子串起来的珠子"。每个节点（珠子）存两样东西：数据和指向下一个节点的指针。好处是增删不用挪动后面的元素，坏处是不能随机访问（不能直接跳到第 n 个）。

⚡ 易错点：链表遍历时，判断条件是 cur != nullptr，不是 cur->next != nullptr！后者会漏掉最后一个节点。

💻代码示例

#include <iostream>
using namespace std;
// 定义链表节点结构体
struct Node {
    int data;          // 存数据
    Node* next;        // 指向下一个节点的指针
};
// 头插法：新节点插到链表头部
Node* insertHead(Node* head, int val) {
    Node* newNode = new Node();  // 动态申请一个新节点
    newNode->data = val;         // 赋值
    newNode->next = head;        // 新节点指向原来的头
    return newNode;             // 新节点变成新的头！
}
// 遍历打印链表
void printList(Node* head) {
    Node* cur = head;             // cur 从头开始走
    while (cur != nullptr) {     // ⚠️ 判断 cur，不是 cur->next！
        cout << cur->data << " -> ";
        cur = cur->next;          // 往后走一步
    }
    cout << "nullptr" << endl;
}
int main() {
    Node* head = nullptr;        // 初始空链表
    head = insertHead(head, 3); // 插入 3
    head = insertHead(head, 2); // 插入 2
    head = insertHead(head, 1); // 插入 1
    printList(head);             // 打印整条链表
    return 0;
}
// 输出: 1 -> 2 -> 3 -> nullptr

🧩互动小测

❓ 题目 1：链表相比数组的最大优势是？

❓ 题目 2：遍历链表时，为什么判断条件应该写 `cur != nullptr` 而不是 `cur->next != nullptr`？

❓ 题目 3：下面这段代码的输出是？

        Node* a = new Node{1, nullptr};

        Node* b = new Node{2, nullptr};

        a->next = b;

        cout << a->next->data;

🏋️动手练一练

📝 编程练习

实现一个函数 int getLength(Node* head)，返回链表的节点个数。

要求：从头遍历到尾，用一个计数器累加，返回总数。
提示：想想 while 循环里 cur 怎么移动，以及何时退出。

参考答案：

int getLength(Node* head) {
    int cnt = 0;              // 计数器初始化为0
    Node* cur = head;         // 从头开始遍历
    while (cur != nullptr) {  // 每次处理一个节点
        cnt++;                // 计数+1
        cur = cur->next;      // 移到下一个节点
    }
    return cnt;               // 返回总节点数
}

要点：遍历时 cur 从 head 开始，每次移到 cur->next，当 cur 变成 nullptr 时说明到尾了，cnt 就是节点个数。

📝易错点提醒

1. 忘记释放内存 —— 用 new 创建的节点，程序结束前要用 delete 释放，否则内存泄漏。

2. 遍历判断条件 —— while(cur != nullptr) 是标准写法，while(cur->next != nullptr) 会漏掉尾节点。

3. 头指针丢失 —— 头插法必须返回新头：head = insertHead(head, val)，不能直接调用 insertHead(head, val) 然后不管返回值。

4. 空链表边界 —— 写函数时第一件事检查 head == nullptr，防止对空指针解引用。

📘链表概念

📖概念讲解

💻代码示例

🧩互动小测

❓ 题目 1：链表相比数组的最大优势是？

❓ 题目 2：遍历链表时，为什么判断条件应该写 cur != nullptr 而不是 cur->next != nullptr？

❓ 题目 3：下面这段代码的输出是？

🏋️动手练一练

📝 编程练习

📝易错点提醒

❓ 题目 2：遍历链表时，为什么判断条件应该写 `cur != nullptr` 而不是 `cur->next != nullptr`？