顺序表和链表都属于线性表但它们对内存的使用方式完全不同。理解二者差异不只是为了应付考试或面试更能帮助我们在实际开发中选对数据结构。一、什么是线性表线性表Linear List是由多个具有相同类型的数据元素组成的有限序列。例如一个待办事项列表复习数据结构 - 提交作业 - 晚上跑步其中每个任务都有明确的前后关系“提交作业”的前一个任务是“复习数据结构”“提交作业”的后一个任务是“晚上跑步”这就是线性结构。需要注意的是线性表描述的是逻辑关系而不是内存中的实际存储方式。线性表在逻辑上是一条线但在物理内存中可以有两种主要实现实现方式物理存储特点常见代表顺序存储元素在内存中连续存放顺序表、数组链式存储元素可以分散存放通过指针连接链表二、顺序表让元素在内存中连续排列顺序表通常基于数组实现。它要求元素在内存中连续存储。例如下标 0 1 2 3 数据 [10] [20] [30] [40]如果数组首地址是base每个元素大小为sizeof(int)那么第i个元素的地址可以直接计算base i * sizeof(int)因此顺序表可以快速访问任意位置的元素。int value array[3];这类操作的时间复杂度是O(1)这被称为随机访问。三、静态顺序表与动态顺序表1. 静态顺序表静态顺序表使用固定长度的数组。typedef struct { int data[100]; size_t size; } StaticList;优点是实现简单。缺点也很明显数组开得太小数据装不下数组开得太大浪费内存容量无法动态调整。因此实际开发中更常见的是动态顺序表。2. 动态顺序表动态顺序表会根据需要动态申请内存。typedef int SLDataType; typedef struct { SLDataType* data; size_t size; size_t capacity; } SeqList;其中data指向动态数组size当前有效元素个数capacity当前数组最多能存放多少元素。例如capacity 10 size 6表示已经申请了能存放 10 个元素的空间但目前只存了 6 个元素。四、动态顺序表的初始化与扩容1. 初始化#include assert.h #include stdlib.h void SeqListInit(SeqList* ps) { assert(ps); ps-data NULL; ps-size 0; ps-capacity 0; }初始化后顺序表暂时没有申请空间。2. 扩容操作当size capacity时说明顺序表已经满了需要扩容。#include stdio.h void SeqListCheckCapacity(SeqList* ps) { assert(ps); if (ps-size ps-capacity) { return; } size_t newCapacity ps-capacity 0 ? 4 : ps-capacity * 2; SLDataType* tmp realloc( ps-data, newCapacity * sizeof(SLDataType) ); if (tmp NULL) { perror(realloc failed); exit(EXIT_FAILURE); } ps-data tmp; ps-capacity newCapacity; }这里通常采用“容量翻倍”的策略4 - 8 - 16 - 32 - 64这样可以减少频繁申请空间的次数。虽然某一次扩容可能需要复制很多数据时间复杂度是 O(N)但从长期来看多次尾插的平均时间复杂度仍然是O(1)这叫作摊销时间复杂度。五、顺序表的插入和删除1. 尾插void SeqListPushBack(SeqList* ps, SLDataType x) { SeqListCheckCapacity(ps); ps-data[ps-size] x; ps-size; }尾插不需要移动原有元素因此通常是 O(1)。2. 任意位置插入如果要在pos位置插入元素需要把后面的元素整体向后移动。void SeqListInsert(SeqList* ps, size_t pos, SLDataType x) { assert(ps); assert(pos ps-size); SeqListCheckCapacity(ps); for (size_t i ps-size; i pos; --i) { ps-data[i] ps-data[i - 1]; } ps-data[pos] x; ps-size; }例如原数据[10, 20, 30, 40] 在下标 1 插入 15 结果[10, 15, 20, 30, 40]为了插入15原本的20、30、40都需要向后移动。因此在顺序表中操作时间复杂度按下标访问O(1)尾插O(1)尾删O(1)头插O(N)中间插入O(N)中间删除O(N)顺序表的最大问题就是为了保持内存连续插入和删除往往需要搬移元素。六、链表元素不必连续只要能找到下一个结点链表不要求结点在内存中连续存储。每个结点除了保存数据还保存下一个结点的地址。typedef int SLTDataType; typedef struct SListNode { SLTDataType data; struct SListNode* next; } SListNode;逻辑结构如下[10 | next] - [20 | next] - [30 | next] - NULL即使这三个结点在内存中的地址完全不连续也不会影响链表结构。可以把链表理解成“寻宝游戏”每个结点保存自己的数据每个结点都告诉你下一个结点在哪里只要沿着指针走就能访问完整个链表。七、单链表的结点申请#include stdio.h #include stdlib.h SListNode* BuyNode(SLTDataType x) { SListNode* node (SListNode*)malloc(sizeof(SListNode)); if (node NULL) { perror(malloc failed); exit(EXIT_FAILURE); } node-data x; node-next NULL; return node; }链表中的每个结点通常通过malloc动态申请。使用完成后必须记得free否则会产生内存泄漏。八、为什么单链表通常在 pos 后插入给定一个结点pos在它后面插入新结点非常方便。void SListInsertAfter(SListNode* pos, SLTDataType x) { assert(pos); SListNode* node BuyNode(x); node-next pos-next; pos-next node; }例如插入前 10 - 20 - 30 在 20 后插入 25 10 - 20 - 25 - 30只需要修改两个指针。因此如果已经知道目标结点位置链表插入操作的时间复杂度是O(1)不过要注意一个容易误解的点链表插入快的前提是“已经找到插入位置”。如果要在第k个位置插入仍然需要从头开始遍历找到第k个结点这一步的复杂度依旧是 O(N)。九、链表的删除操作删除pos后面的结点void SListEraseAfter(SListNode* pos) { assert(pos); assert(pos-next); SListNode* del pos-next; pos-next del-next; free(del); }例如删除前 10 - 20 - 30 - 40 删除 20 后面的结点 10 - 20 - 40同样只需要修改指针不需要搬移其他元素。十、链表有哪些类型链表可以根据三个维度分类单向或双向带头或不带头循环或非循环。组合起来一共有 8 种链表结构。实际中最常见的是以下两种1. 无头单向非循环链表结构简单head - node1 - node2 - node3 - NULL常用于哈希桶图的邻接表面试中的链表题。2. 带头双向循环链表每个结点有前驱和后继指针。typedef struct ListNode { int data; struct ListNode* next; struct ListNode* prev; } ListNode;逻辑结构head - node1 - node2 - node3 ^ | |____________________________|这种结构虽然看起来复杂但因为有哨兵头结点并且首尾相连很多边界问题会被统一处理。十一、经典链表问题快慢指针判环判断链表是否有环是面试高频题。思路是使用两个指针慢指针每次走一步快指针每次走两步。如果链表无环快指针一定会先走到NULL。如果链表有环快指针会在环中追上慢指针。int HasCycle(SListNode* head) { SListNode* slow head; SListNode* fast head; while (fast fast-next) { slow slow-next; fast fast-next-next; if (slow fast) { return 1; } } return 0; }时间复杂度O(N)空间复杂度O(1)这也是快慢指针算法的价值不需要额外的哈希表就能判断链表是否存在环。十二、顺序表与链表的区别对比维度顺序表链表物理存储内存必须连续内存不要求连续随机访问支持O(1)不支持O(N)中间插入删除需要移动元素O(N)已知位置时 O(1)扩容空间不足时需要扩容不需要整体扩容额外空间较少每个结点需要额外指针缓存利用率高较低适合场景高频访问、遍历高频插入、删除十三、为什么顺序表遍历通常更快从复杂度上看顺序表和链表遍历都是 O(N)。但是在实际运行中顺序表通常更快。原因在于 CPU 缓存。顺序表的元素在内存中连续存储[10][20][30][40][50]CPU 读取一个元素时往往会把附近的数据一起加载到缓存中。因此访问下一个元素时很可能已经在缓存中。而链表结点可能散落在内存的不同位置10 - 内存地址A 20 - 内存地址F 30 - 内存地址CCPU 每访问一个结点都可能需要重新从内存加载数据缓存命中率较低。所以不要只看 Big-O 复杂度真实机器上的缓存性能也很重要。十四、实际开发中如何选择如果业务特点是高频按下标访问需要大量遍历数据量相对稳定希望利用缓存提升性能优先考虑顺序表。例如学生成绩表图像像素数组排行榜动态数组。如果业务特点是已知位置后需要频繁插入删除数据规模变化较大不强调按下标随机访问可以考虑链表。例如LRU 缓存中的双向链表哈希桶图的邻接表某些任务调度结构。十五、总结顺序表和链表都是线性表的实现方式但它们的核心思想不同顺序表依靠连续内存访问快、缓存友好链表依靠指针连接插入删除更灵活顺序表适合频繁访问链表适合已知位置后的频繁插入和删除。真正重要的不是死记硬背“顺序表快”或“链表插入快”而是先分析自己的业务是查询更多还是插入删除更多是否需要按下标访问是否已经知道目标位置选对数据结构代码会更简单性能也会更稳定。