C++ 链表

前言刚学C数据结构是不是被链表搞得头大很多新手觉得链表复杂搞不懂其中的指针操作、分不清单链表/双链表等。今天我们来一起梳理一下关于链表的这些事情。目录一、什么是链表二、链表 vs 数组三、链表的分类3.1 单向链表3.2 双向链表3.3 循环链表四、完整代码示例五、常见避坑指南一、什么是链表链表是一种非连续、非顺序的物理存储结构。它由一系列节点组成每个节点包含两部分数据域存储数据和指针域存储下一个节点的地址。逻辑上链表像一串珍珠通过指针将零散的内存块串联起来。最常见的是单向链表此外还有双向链表和循环链表。链表的核心结构是节点。在C中一般使用结构体或类来定义例如struct Node { int data; // 数据域 Node* next; // 指针域指向下一个节点 };二、链表 vs 数组我们将链表与数组进行对比能够帮助我们更好地理解链表。数组是一种连续、顺序的物理存储结构。特性数组链表内存结构连续内存非连续内存访问效率O(1) - 支持随机访问O(n) - 必须从头遍历插入/删除O(n) - 需要移动元素O(1) - 只需修改指针已知位置空间利用固定大小可能浪费动态分配按需申请内存布局差异对比数组内存地址: 0x1000 0x1004 0x1008 0x100C 0x1010 ┌────────┬────────┬────────┬────────┬────────┐ 数组: | A[0] │ A[1] │ A[2] │ A[3] │ A[4] │ │ 10 │ 20 │ 30 │ 40 │ 50 │ └────────┴────────┴────────┴────────┴────────┘链表内存地址: 0x2000 0x5000 0x1000 0x7000 ┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ 节点: │ 10 │────►│ 20 │────►│ 30 │────►│ 40 │───► NULL │ next │ │ next │ │ next │ │ next │ │0x5000 │ │0x1000 │ │0x7000 │ │ NULL │ └────────┘ └────────┘ └────────┘ └────────┘如果需要频繁随机访问选数组如果需要频繁插入删除选链表。三、链表的分类这里介绍常用的三种链表单向链表、双向链表、循环链表。3.1 单向链表特点只有一个next指针指向下一个节点只能单向遍历内存占用最小(仅一个指针)无法直接访问前驱节点struct Node { int data; // 数据域 Node* next; // 指针域指向下一个节点 };图例3.2 双向链表特点有pre和next两个指针可双向遍历内存占用更大2个指针可直接访问前驱删除更方便struct Node { int data; //数据 Node* prev; //指向前一个节点 Node* next; //指向后一个节点 };图例3.3 循环链表循环链表是一种特殊的链表最后一个节点的指针不指向 NULL而是指向头节点形成一个环。单向循环链表: A → B → C → D → (回到A) 双向循环链表: A ↔ B ↔ C ↔ D ↔ (回到A)单向循环链表图例四、完整代码示例常用的链表操作包括 遍历、查找、插入、删除。这里以单向链表为例#include iostream // 1. 定义节点结构体 struct Node { int data; Node* next; // 构造函数方便创建节点 Node(int val) : data(val), next(nullptr) {} }; // 2. 定义链表类 class LinkedList { private: Node* head; // 头指针 public: // 构造函数初始化空链表 LinkedList() : head(nullptr) {} // 析构函数程序结束时自动调用释放所有节点内存 ~LinkedList() { Node* current head; while (current ! nullptr) { Node* nextNode current-next; delete current; // 释放当前节点 current nextNode; } std::cout 链表内存已释放 std::endl; } // -------------------- 基本操作 -------------------- // 1. 头插法在链表头部插入新节点 void insertAtHead(int value) { Node* newNode new Node(value); newNode-next head; // 新节点指向原来的头节点 head newNode; // 更新头节点 } // 2. 尾插法在链表尾部插入新节点 void insertAtTail(int value) { Node* newNode new Node(value); // 如果链表为空新节点即为头节点 if (head nullptr) { head newNode; return; } // 否则遍历到最后一个节点 Node* temp head; while (temp-next ! nullptr) { temp temp-next; } temp-next newNode; // 将新节点链接到尾部 } // 3. 删除节点删除第一个值为 value 的节点 void deleteNode(int value) { if (head nullptr) { std::cout 链表为空无法删除 std::endl; return; } // 情况1要删除的是头节点 if (head-data value) { Node* temp head; head head-next; // 头指针后移 delete temp; // 释放原头节点 return; } // 情况2要删除的是中间或尾部节点 Node* current head; Node* prev nullptr; // 遍历寻找目标节点 while (current ! nullptr current-data ! value) { prev current; current current-next; } // 如果没找到 if (current nullptr) { std::cout 未找到值为 value 的节点 std::endl; return; } // 找到了从链表中摘除 prev-next current-next; delete current; // 释放内存 } // 4. 查找节点判断值是否存在 bool search(int value) { Node* temp head; while (temp ! nullptr) { if (temp-data value) { return true; } temp temp-next; } return false; } // 5. 遍历打印链表 void display() { Node* temp head; std::cout 链表内容: ; while (temp ! nullptr) { std::cout temp-data - ; temp temp-next; } std::cout NULL std::endl; } };五、常见避坑指南1) 空指针单节点情况// ❌ 错误删除尾部时未考虑单节点 Node* popBack(Node* head) { Node* curr head; while (curr-next-next ! nullptr) { // 崩溃curr-next 可能为 nullptr curr curr-next; } // ... } // ✅ 正确单独处理单节点 Node* popBack(Node* head) { if (head nullptr) return nullptr; if (head-next nullptr) { // 单节点 delete head; return nullptr; } // 正常处理... }2) 内存泄漏删除头节点时没有释放节点内存// ❌ 错误直接修改指针丢失节点地址 Node* removeHead(Node* head) { head head-next; // 原 head 节点丢失内存泄漏 return head; } // ✅ 正确先释放再移动 Node* removeHead(Node* head) { if (head nullptr) return nullptr; Node* newHead head-next; delete head; // 释放内存 return newHead; }