788 字
4 分钟
链表数据结构
链表数据结构学习笔记
1. 链表的基本概念
-
链表是一种线性数据结构，由一系列节点（Node）组成，每个节点包含：
- 数据域 ：存储实际数据
- 指针域 ：存储指向下一个节点的引用
-
链表的特点：
- 动态数据结构，大小可灵活变化
- 内存非连续分配
- 插入/删除操作效率高（在已知位置时）
- 不支持随机访问
2. 链表与数组的对比
| 特性 | 数组 | 链表 |
|---|---|---|
| 内存分配 | 连续内存块 | 非连续内存 |
| 大小 | 固定（静态）Ps. 例外：可变长数组（vector） | 动态（可扩展） |
| 访问方式 | 随机访问（O(1)）（下标） | 顺序访问（O(n)）（顺着指针域的指向） |
| 插入/删除 | 效率低（O(n)），需要挪动插入点后所有元素的位置 | 效率高（O(1)，已知位置），只需要指针的重新指向 |
| 内存效率 | 可能浪费或不足 | 按需分配，无浪费 |
3. 常见链表类型
- 单链表：每个节点只有一个指向下一个节点的指针
- 双向链表：每个节点有两个指针，分别指向前一个节点和后一个节点
- 循环链表：最后一个节点的指针指向头节点，形成一个环
单链表的实现
- 节点定义
struct ListNode { int val = 0; // 数据域: 该节点要存储的值 ListNode* next = nullptr; // 指针域: 指向下一节点的指针};- 需要一个头节点来存储链表的头指针
ListNode* head = nullptr;- 初始化链表
head = new ListNode();- 完整示例
- 题目：用一个单链表来实现学生信息的存储和管理
- 代码
// 链表示例：用一个单链表来实现学生信息的存储和管理#include <iostream>
// 定义学生信息结构体struct Student { int id = 0; std::string name = ""; int age = 0;};
// 定义链表节点struct ListNode { // 构造函数 ListNode(const Student& student) : val(student) {}
// 输出函数 void print() const { std::cout << "ID: " << val.id << ", Name: " << val.name << ", Age: " << val.age << std::endl; }
Student val; ListNode* next = nullptr; // 指针默认置空};
// 添加节点函数void addNode(ListNode* &head, const Student& student) { if (head == nullptr) { head = new ListNode(student); return; } ListNode* temp = head; while (temp->next != nullptr) { temp = temp->next; } temp->next = new ListNode(student);}
// 删除节点函数void deleteNode(ListNode* &head, const int &id) { if (head == nullptr) { return; } // 删除头节点 if (head->val.id == id) { ListNode* temp = head; head = head->next; delete temp; return; } // 删除非头节点 ListNode* temp = head; while (temp->next != nullptr) { if (temp->next->val.id == id) { // 找到要删除的节点 ListNode* del = temp->next; temp->next = del->next; // 前一个节点的next指向要删除节点的next delete del; // 删除的节点 return; } temp = temp->next; }}
int main() { ListNode* head = nullptr; // 添加节点 addNode(head, {1001, "张三", 20}); addNode(head, {1002, "李四", 21}); addNode(head, {1003, "王五", 22});
// 遍历链表打印全部信息 ListNode* temp = head; while (temp != nullptr) { temp->print(); temp = temp->next; }
// 删除节点 deleteNode(head, 1002);
// 再次遍历链表打印全部信息 temp = head; while (temp != nullptr) { temp->print(); temp = temp->next; }
return 0;}