线性表是数据结构课程里最先接触的一类结构，而“顺序表示”作为它的第一种实现方式，看起来就是数组加几个操作函数，很多人学完觉得不过如此。我一开始也是这样想的，直到后来在项目里反复处理动态数组的扩容、元素搬移、容量管理，才发现自己当年对顺序表的理解远远不够。这篇文章就是想把顺序表从原理到实现、从课堂知识到工程习惯，完整地过一遍，重点讲清楚那些教材里容易一笔带过、但实际写代码时一定会遇到的细节。

适合读这篇文章的，包括正在啃数据结构的同学、准备面试手撕代码的开发者，以及想弄明白动态数组底层到底怎么运作的人。顺序表作为数组和动态数组的原型，把这套思路弄清楚，对后面理解栈、队、堆、内存管理都有直接帮助。

1. 顺序表不是“数组换个名字”，先看它解决了什么问题

1.1 线性表的两条实现路线

线性表描述的是“n个数据元素组成的有限序列”，元素之间有前后关系，除了第一个和最后一个，每个元素都只有一个直接前驱和一个直接后继。这个逻辑关系可以用两种物理方式落地：一种是在内存里找一段连续的空间，把元素按顺序一个挨一个放好，这就是顺序表示；另一种是每个元素各自存放，通过指针把前驱和后继串起来，这就是链式表示。

顺序表示的关键词是“连续”，它要求逻辑上相邻的元素在物理地址上也相邻。很多人觉得这不过是数组，但数组只解决了“存”的问题，没有解决“增删改查”的完整操作逻辑。顺序表是在连续存储之上，把初始化、插入、删除、查找、扩容这些行为系统地定义了一遍，这才叫“实现”。

1.2 核心不变量：逻辑相邻必须物理相邻

理解顺序表最有效的方式，是抓住它的不变量——逻辑相邻的元素必须存放在物理地址相邻的存储单元中。这个约束一旦确立，很多操作的推导就顺理成章了。

插入一个元素到中间位置时，为了保持不变量，必须把该位置之后的所有元素往后挪一位；删除一个元素时，则必须把后面的元素往前挪一位。挪动多少元素、从哪个方向挪、什么时候需要扩容，全部由这个不变量决定。如果你写代码时忘了维持它，顺序表就会出现“逻辑顺序和物理顺序对不上”的毛病，表现出来就是遍历时数据错乱、查找结果不对。

1.3 地址计算的数学底座：为什么下标能O(1)

顺序表按下标访问能做到常数时间，本质是地址计算公式在起作用。假设表的起始地址是LOC(a0)，每个元素占用size个字节，那么第i个元素（下标从0开始）的地址为：

LOC(ai) = LOC(a0) + i * size

这是一个一次乘法加一次加法，和表长无关。只要基址和元素大小已知，任何下标都能直接算出地址，不需要遍历。这也是连续存储最大的性能和链表拉开差距的地方——链表访问第i个元素必须从头结点出发，逐个走指针。

这个公式还解释了为什么很多编程语言的数组下标从0开始。下标本质上就是“相对于首元素的偏移量”，从0开始，地址计算最简单；如果从1开始，每一项都要多做一个减一操作，虽然数学上没问题，但工程上没必要。

2. 存储与操作的设计逻辑：读快、写慢的账怎么算的

2.1 连续空间的优点与代价

连续存储带来最直接的好处有两个：一是按下标访问O(1)，二是缓存局部性好。CPU加载内存时不是一次读一个字节，而是按缓存行整体加载，顺序表里相邻元素在地址上连续，遍历时很容易命中缓存，速度非常快。这个特性在数据量大的场景下特别明显，链表虽然逻辑上顺序遍历，但每个结点内存地址不连续，频繁跳转会导致缓存未命中。

代价也很明确：插入和删除需要移动大量元素，而且在表满时还得寻找更大的连续内存块并整体搬移。所以顺序表本质上是“重读轻写”的结构，适合读多写少、按位置访问多的场景。

2.2 插入删除的移动次数期望：n/2 是怎么来的

以长度为n的顺序表为例，在第i个位置（位序从1到n+1）插入新元素时，需要把原第i个到第n个元素全部后移，移动次数是n - i + 1。假设每个位置被插入的概率相等，i从1取到n+1，所有可能插入位置的移动次数总和为：

0 + 1 + 2 + ... + n = n(n+1)/2

除以共n+1个插入位置，得到平均移动次数为 n/2。删除同理，删除第i个位置元素（i从1到n）需要移动n - i个元素，总和为0 + 1 + ... + (n-1) = n(n-1)/2，平均移动(n-1)/2次。

这就是“顺序表插入删除时间复杂度为O(n)”这句结论的完整来源。理解这个推导比背结论重要，因为在分析扩容均摊成本、选择数据结构时，你会反复用到这套“移动次数求和”的思路。

2.3 复杂度结论：顺序表是“重读轻写”的结构

把常用操作的时间复杂度归个总：

这里有个容易忽略的点：如果使用动态分配方式，尾部插入遇到容量不足时需要扩容，单次操作可能达到O(n)。但把多次插入放在一起看，扩容成本会被摊还到每次插入上，均摊复杂度仍然是O(1)。这个摊还分析我放在后面扩章节专门讲，因为它是理解动态数组性能的关键。

3. 手写一个可用的动态顺序表：完整实现与关键细节

3.1 结构体设计：容量、长度、数据区三件套

静态顺序表直接用一个定长数组，代码简单但很不实用，因为无法预知数据规模。工程上更常用动态顺序表，结构体里需要三个字段：

• data：指向堆内存的指针，数据区就在这块连续内存上
• length：当前实际存储的元素个数
• capacity：当前分配的容量，即最多能容纳多少元素而不触发扩容

注意区分length和capacity，这是初学者最容易搞混的一对概念。length是逻辑意义上的“表长”，capacity是物理意义上的“容量”。判断表空看length，判断是否需要扩容则比较length和capacity。

3.2 常用操作的实现套路

初始化时分配初始容量，比如8个元素的空间。插入的核心逻辑是：先校验位置合法性，再检查容量，不够就扩容，然后从后往前搬移元素，最后写入新值并把length加一。搬移必须从后往前，否则前面的元素会被覆盖掉。

删除相对简单：校验位置合法性，从被删位置的下一个元素开始，依次往前覆盖，最后把length减一。这里不需要真正把最后一个元素清空，只要length不包含它，逻辑上它就不存在了。

查找分为按下标取值和按值找位置。按下标取值要先做越界检查，按值查找是顺序遍历，返回第一个匹配元素的下标（或位序），找不到返回一个约定的失败值。

3.3 一个可以直接跑的最小示例

用C语言写一个完整可运行的动态顺序表，核心操作都包含在内：

#include <stdio.h> #include <stdlib.h> typedef struct { int *data; int length; int capacity; } SeqList; // 初始化：分配初始容量 int initList(SeqList *list, int cap) { list->data = (int *)malloc(sizeof(int) * cap); if (list->data == NULL) { return 0; } list->length = 0; list->capacity = cap; return 1; } // 扩容：容量翻倍 int expandList(SeqList *list) { int newCap = list->capacity * 2; int *newData = (int *)malloc(sizeof(int) * newCap); if (newData == NULL) { return 0; } for (int i = 0; i < list->length; i++) { newData[i] = list->data[i]; } free(list->data); list->data = newData; list->capacity = newCap; return 1; } // 在位序pos插入，pos从1开始 int insertList(SeqList *list, int pos, int value) { if (pos < 1 || pos > list->length + 1) { return 0; } if (list->length == list->capacity) { if (!expandList(list)) { return 0; } } for (int i = list->length; i >= pos; i--) { list->data[i] = list->data[i - 1]; } list->data[pos - 1] = value; list->length++; return 1; } // 删除位序pos的元素 int deleteList(SeqList *list, int pos) { if (pos < 1 || pos > list->length) { return 0; } for (int i = pos; i < list->length; i++) { list->data[i - 1] = list->data[i]; } list->length--; return 1; } // 按下标访问，下标从0开始 int getElem(SeqList *list, int index, int *value) { if (index < 0 || index >= list->length) { return 0; } *value = list->data[index]; return 1; } // 按值查找，返回位序，找不到返回-1 int findElem(SeqList *list, int value) { for (int i = 0; i < list->length; i++) { if (list->data[i] == value) { return i + 1; } } return -1; } // 销毁：释放内存并重置字段 void destroyList(SeqList *list) { free(list->data); list->data = NULL; list->length = 0; list->capacity = 0; } int main() { SeqList list; initList(&list, 4); insertList(&list, 1, 10); insertList(&list, 2, 20); insertList(&list, 3, 30); insertList(&list, 4, 40); insertList(&list, 2, 15); // 扩容触发点 for (int i = 0; i < list.length; i++) { printf("%d ", list.data[i]); } printf("\n"); deleteList(&list, 1); for (int i = 0; i < list.length; i++) { printf("%d ", list.data[i]); } printf("\n"); destroyList(&list); return 0; }

这段代码里我最想提醒的是insertList中的搬移循环：for (int i = list->length; i >= pos; i--)。它从最后一个元素开始，逐个往右挪，保证前面的元素在搬移过程中不被覆盖。如果把方向写反，从前往后挪，后面的数据会被逐步覆盖，结果一定错。

另外一个容易被忽略的地方是销毁操作。很多人会忘记把data置为NULL、把length和capacity归零，导致重复销毁或误用已释放内存。虽然例子程序小看不出问题，在长期运行的服务里，悬空指针是很危险的。

4. 扩容到底做了什么，为什么偶尔会“卡一下”

4.1 动态扩容的本质是“搬家”

当length到达capacity时，再插入元素就必须扩容。扩容在底层做的事可以拆成三步：申请一块更大的连续内存，把旧数据逐项复制过去，释放旧内存。如果你的顺序表存的是成百上千个大结构体，这个复制过程就会很耗时间，表现就是程序在某个插入操作上明显卡顿一下。

C语言里常用realloc做这件事，但realloc的行为分两种：如果原空间后面恰好有空闲区域，它可能原地扩大并直接返回原指针；否则就会重新分配并搬运数据。作为库的使用者，我们无法假定一定是原地扩展，所以必须把扩容当成一次完整的数据迁移来设计。这也是为什么扩容后，之前任何一个指向data区域内部的指针都可能失效——地址变了，旧地址指向的是已经释放的内存。

4.2 扩容倍数为什么通常选2倍

这是顺序表设计里很经典的问题。如果每次扩容只固定多分配一个元素的空间，那么插入n个元素的过程中，几乎每次插入都要搬移全部数据，总搬移量是1+2+3+...+n，复杂度退化为O(n^2)。如果每次把容量翻倍，搬移总次数变成：

cap0 + 2cap0 + 4cap0 + ... + n ≈ 2n

也就是说，插入n个元素累计复制的元素总量是O(n)，平摊到每次插入上是O(1)。这个“倍增摊还”的思路是动态数组性能的基石，也是为什么几乎所有语言标准库里的动态数组都采用倍增策略。

选2倍还是1.5倍，工程上有讨论。2倍扩容代码简单、均摊代价清晰，但容量增长速度太猛，如果只插入了n+1个元素，可能浪费接近一半空间。1.5倍扩容增长稍缓，内存复用率在某些分配器下更好，但均摊常数略高。实践里的建议是：普通场景先用2倍，如果实测内存占用过高再调倍数或换分配策略。

4.3 缩容、内存碎片和容量管理

有扩容就该有缩容。但缩容不能太激进，否则会出现反复扩容缩容的抖动。常见的做法是在length远小于capacity时才触发，比如当capacity大于某个阈值且length小于capacity的四分之一，才把容量缩小到原来的一半。缩容频率控制住了，性能抖动也就控制住了。

还要提一下内存碎片。顺序表要求连续内存，大块数据的反复扩容搬移，在空闲内存碎片化的情况下可能找不到足够大的连续区域。这就是为什么存储大对象的场景，如果对象大小固定且数量不多，有人宁愿在初始化时一次性分配足够大的容量，而不是反复扩容。空间和时间的权衡，到具体业务里就得你来拿主意。

5. 顺序表到底用在哪儿：从工程视角看它的价值

5.1 三个最适合顺序表的场景

顺序表不是只在教科书里存在，实际工程里它出现的频率远高于链表。第一个典型场景是按下标高频访问的集合，比如保存配置项的列表、索引数组、矩阵的行/列存储。地址计算公式保证了访问任何位置的代价一致，这在循环密集的算法里非常重要。

第二个场景是尾部持续增长的缓冲区。日志收集、消息队列的底层、网络收发缓冲，数据到达顺序和存储顺序一致，用顺序表最合适。尾插不搬移元素，capacity设计得宽裕一些，整个写入过程就是不断往尾部放数据。

第三个场景是内存缓存友好型遍历。向量数据、邻接表里的边集合、图像像素存储，凡是需要顺序扫描全部元素的，连续内存都能吃到缓存局部性的红利。这也是为什么图算法里用“数组存邻接表”往往比“链表存邻接表”跑得快的核心原因。

5.2 顺序表 vs 链表的选型对比

面试和课程设计里最常问的，就是什么时候用顺序表、什么时候用链表。我把关键差异整理成了表：

从这个表能看出，链表真正的优势只集中在两点：一是已知位置的任意插入删除，二是元素本身很大或结构不固定时可以避免搬移。如果你的操作大部分是“按下标访问”或“尾部增长”，顺序表是更优解。

5.3 面试变体和课堂常考的实现细节

面试手撕顺序表时，经常会在基础实现上加几个限制条件，比如不允许使用额外数组来实现循环右移、要求原地合并两个有序顺序表、要求不借助库函数完成扩容。这些变体本质上还是考察你对“连续存储+元素搬移”这两个核心点的掌握程度。

还有一类常见问题是“如果元素不是int而是结构体，该怎么办”。多数语言里的动态数组用值语义，复制时会逐个拷贝结构体；如果结构体里面还有指针、资源句柄，简单的值拷贝会带来深层拷贝和资源释放问题。顺序表对这类元素并不友好，这也是为什么存储大对象时很多人宁可存指针的数组，让每个元素是一个固定大小的指针而不是庞大的结构体本体。

6. 实战场上最容易翻车的细节与调试经验

6.1 扩容失效和越界不报错的假象

自己实现顺序表时，最隐蔽的bug就是扩容后没有更新外部持有的指针。比如你在一开始取了一个指向data内部元素的指针，扩容发生了，旧内存被free，那个指针就成了悬空指针，再访问时数据看起来“莫名其妙变了”。调试这种问题最好的方法，是在扩容后打印data地址，对比外部指针的地址，基本立刻就能锁定问题。

越界访问又是另一类麻烦。C语言的数组越界不会像Java、Python那样抛异常，你访问a[length]的时候，很可能读到的是一块相邻内存的残留数据，程序既不崩溃也不会报错，但结果就是不对。这种问题只能用工具辅助，比如编译时加调试选项、运行时用检测工具，或者在自己的代码里多写assert，每次操作前后都检查length是否在有效范围内，尽早暴露问题。

6.2 capacity和length混淆，以及realloc的正确用法

我见过很多次这样的代码：初始化后length是0，但打印结果时却按capacity去遍历，结果把分配区里未初始化的垃圾值全打出来了。length和capacity的概念要刻在脑子里，遍历、查找、打印一律看length，只有扩容和分配内存时才看capacity。

realloc还有一个经典错误是直接把返回值赋给原指针：

// 错误示范 list->data = (int *)realloc(list->data, newCap * sizeof(int));

如果realloc失败，它会返回NULL并保留原内存，但这一步执行后list->data已经变成了NULL，原内存地址丢失，造成内存泄漏，数据也全没了。正确做法是先用临时变量接收返回值，判空成功后再更新：

// 正确做法 int *newData = (int *)realloc(list->data, newCap * sizeof(int)); if (newData == NULL) { // 处理失败，原data仍然有效 return 0; } list->data = newData; list->capacity = newCap;

6.3 我自己踩过的坑和排查路径

一次做模拟项目时，我用顺序表保存一组带有索引的对象，为了方便，在外部缓存了几个元素的指针。触发器是数据量涨到一定规模后，某个缓存的指针指向的数据变成了别的值。排查过程花了不少时间：先怀疑是业务逻辑写错，后来打印了元素的地址和data区的地址，才发现data的地址在扩容后变了，而外部缓存的指针还停在老地址上。

从那以后我养成了一个习惯：只要动态数组可能出现扩容，外部就不要保存内部元素的地址，而是按下标访问，每次使用时从data里现取。这样多一次地址计算，换来的是可靠得多。另外，我在结构体里总是把capacity和length打出来看，尤其是出问题时，先确认这两个值是否符合预期，再往下查业务逻辑。

顺序表实现起来不难，但“连续存储”这个约束像一条暗线，贯穿了操作设计、性能分析和工程选择的全过程。只要你时刻记住“逻辑相邻物理相邻”这八个字，插入删除时想清楚搬移方向，扩容时想清楚内存生命周期，很多看似玄学的bug其实都能从原理上直接推断出来。我自己这些年越用越觉得，基本功这东西，值得反复打磨。