数据结构系列文章目录第一章 顺序表与链表文章目录数据结构系列文章目录前言二、顺序表内存里的连续公寓1.底层构成2.空间扩容3.任意位置插入三、链表散落在内存各处的零散空间1.底层构成2.三种变体3.链表的头节点四、核心操作与复杂度五、优缺点比较六、应用场景总结前言茫茫学海中我们继续前进。今天要讲述的是顺序表与链表的相关知识。一、引言顺序表与链表是数据结构中两种不同的存储结构。二者在逻辑上都是连续的但是在实际的内存结构中顺序表是连续的一块空间而链表是非连续的零散空间组合。想象你有一个书架和一堵便签墙书架上书一本挨一本第三本伸手就能拿到——这是顺序表便签墙上每张写着内容末尾附一句下一张在左下角——这是链表。下面直接用代码把这两样东西拆开看。二、顺序表内存里的连续公寓1.底层构成顺序表的底层其实是malloc申请的一块连续内存空间我们可以将它理解为数组。它由连续的内存空间、计数器、总容量三部分构成。访问下标i等价于base i * sizeof(int)一次地址计算与表大小无关——这是时间复杂度O(1)的来源。代码如下示例typedef struct { int *data; // 指向堆上的数组 int size; // 当前元素个数 int capacity; // 总容量 } SeqList; // 初始化 void seq_init(SeqList *list, int capacity) { list-data (int *)malloc(sizeof(int) * capacity); list-size 0; list-capacity capacity; } // O(1) 随机访问 int seq_get(SeqList *list, int index) { if (index 0 || index list-size) { printf(Index out of range\n); exit(1); } return list-data[index]; // 一次乘法 一次加法恒定时间 }2.空间扩容顺序表在开辟时使用的是一段固定的空间。当元素越来越多导致空间不够用时就需要对顺序表进行扩容一般会采用realloc进行翻倍扩容方式。代码如下示例void seq_resize(SeqList *list, int new_capacity) { int *new_data (int *)realloc(list-data, sizeof(int) * new_capacity); if (new_data NULL) { printf(realloc failed\n); exit(1); } list-data new_data; list-capacity new_capacity; } void seq_add_last(SeqList *list, int value) { if (list-size list-capacity) { seq_resize(list, list-capacity * 2); // 翻倍扩容 } list-data[list-size] value; }realloc相比mallocfree好在哪realloc扩容首先会在当前空间的相邻位置寻找有无连续的内存空间满足扩容需求。如果满足直接开辟空间无需拷贝数据并释放原空间此时时间复杂度是O(1)。如果相邻位置没有连续空间则realloc会自动开辟一块新的空间并拷贝数据释放原空间无需手动完成。扩容本身最坏仍是 O(n)但得益于翻倍策略扩容次数随数据量增长越来越稀疏均摊到每次插入平均仍是 O(1)。3.任意位置插入对于顺序表而言任意位置插入是其最大的软肋。因为在任意位置插入就意味着需要挪动该位置后面的元素时间复杂度较大最坏情况可达到O(n)。void seq_add_first(SeqList *list, int value) { if (list-size list-capacity) { seq_resize(list, list-capacity * 2); } // 从最后一个元素开始逐个往后挪 for (int i list-size; i 0; i--) { list-data[i] list-data[i - 1]; } list-data[0] value; list-size; }三、链表散落在内存各处的零散空间1.底层构成不同于顺序表链表是由不相邻的节点组合而成的空间。链表的最小构成是节点只有两个字段。typedef struct Node { int data; // 数据域 struct Node *next; // 指针域指向下一个节点 } Node;节点 A 在0x1000节点 B 在0x7A30——两者之间毫无物理关联全靠next指针维系逻辑顺序。这就是链字的来源。2.三种变体// 单向只有 next typedef struct SNode { int data;//数据域 struct SNode *next;//指针域 } SNode; // 双向多了 prev typedef struct DNode { int data;//数据域 struct DNode *next;//指向下一个节点 struct DNode *prev;//指向上一个节点 } DNode; // 循环尾节点 next 指向头节点代码结构同单向 // 区别只在尾节点的 next head 而不是 NULL链表可以实现单向链表、双向链表以及循环链表。双向链表每个节点多存一根指针换来的是知道目标节点就能直接删的便利——这是典型的空间换时间。循环链表把末尾这个概念抹掉了适合轮询调度。3.链表的头节点链表没有不存数据的头节点时头插节点会导致链表头节点不断变化。这导致头插节点相对于其他地方插入需要单独处理。// 不带头结点头部插入必须返回新 head Node* insert_head_no_dummy(Node *head, int value) { Node *new_node (Node *)malloc(sizeof(Node)); new_node-data value; new_node-next head; return new_node; // 调用方必须这样用: head insert_head_no_dummy(head, 10) } // 而中间插入完全不需要改 head void insert_after_no_dummy(Node *prev, int value) { Node *new_node (Node *)malloc(sizeof(Node)); new_node-data value; new_node-next prev-next; prev-next new_node; }链表包含头节点则可以将头插的节点直接插入在头节点后此时头插节点不需要单独处理。typedef struct { Node *dummy; // 头结点不存数据只作为起点 Node *tail; // 尾指针方便尾部 O(1) 插入 } LinkedList; void list_init(LinkedList *list) { list-dummy (Node *)malloc(sizeof(Node)); list-dummy-next NULL; list-tail list-dummy; } // 所有插入都走同一个函数 void list_insert_after(Node *prev, int value) {//头部插入时 prev就是不存数据的dummy节点 Node *new_node (Node *)malloc(sizeof(Node)); new_node-data value; new_node-next prev-next; prev-next new_node; } // 头部插入——和中间插入一模一样的调用 void list_add_first(LinkedList *list, int value) { list_insert_after(list-dummy, value); }链表使用不存数据的头节点还拥有一个额外好处C语言本身没有垃圾处理机制带dummy节点可以在释放链表时直接从dummy开始释放不用单独处理空链表情况。四、核心操作与复杂度操作顺序表链表按下标访问O(1)O(n)头部插入/删除O(n)O(1)尾部插入/删除O(1) 均摊情况O(1)有尾指针情况中间插入/删除O(n)数据挪动O(n)查找占大头五、优缺点比较链表的优点1.按需申请空间不会造成空间浪费。2.已知节点的情况下双向链表插入删除数据的时间复杂度为O(1)。链表的缺点1.存储空间不连续CPU缓存命中率较低效率比较低。2.不支持下标的随机访问。顺序表的优点1.支持下标的随机访问访问效率较高。2.存储空间连续CPU缓存命中率较高效率更高。顺序表的缺点1.插入删除数据的时间复杂度较高。2.空间不够时需要不断扩容容易造成空间浪费。六、应用场景用顺序表频繁随机访问——data[i]是 O(1)链表只能持续遍历。数据量固定或只从尾部增删——日志追加、时间序列数据。对遍历性能敏感——CPU 缓存命中率高遍历速度碾压链表。用链表频繁在头部或中间插入删除——LRU 缓存算法的核心操作就是把某个节点从当前位置摘下来插到头部”数据量不可预测——每次都malloc一个节点不会像顺序表那样预留大量未用空间。总结书架有书架的好——算得快还省缓存便签墙有便签墙的妙——插得灵活删得干脆。顺序表胜在O(1)随机访问和内存局部性链表赢在 O(1局部插入和动态伸缩。没有谁绝对优于谁数据结构课的意义从来不是让你记住选谁而是让你在每一个场景里都能清楚地说出为什么选它。希望这篇文章帮你把这两块内存拼图真正拼完整了。如果觉得有用别忘了点赞、投币、收藏——一键三连支持一下这对我真的很重要。有什么问题欢迎在评论区留言我们下篇博客见。别忘了free。希望这篇文章帮你把这两块内存拼图真正拼完整了。如果觉得有用别忘了点赞、投币、收藏——一键三连支持一下这对我真的很重要。有什么问题欢迎在评论区留言我们下篇博客见。别忘了free。
