大学数据结构《线性表》课程讲义课件

2026数据结构·线性表顺序表·链表·存储结构·时间复杂度课程导览01线性表初识从排队到抽象定义02顺序表连续存储与基本操作03单链表离散存储与指针链接04对比与选型核心差异与选表原则05实战与应用场景落地与课程小结01线性表初识从排队买票到数据结构的基石排队场景里的共同规律抓住“一对一”的先后关系，抽象定义就水到渠成排队买票每个人前后是谁，一眼看清购物清单要买的东西一行行按序写下播放列表歌曲一首接一首排列共同点：元素按顺序排列，除第一个和最后一个外，每个元素有且仅有一个直接前驱和一个直接后继。排队的前一位是前驱、后一位是后继；清单里“第二项”前面是第一项、后面是第三项。线性表的严格定义线性表是由n（n≥0）个具有相同数据类型的数据元素构成的有限序列。有限序列：n≥0个数据元素类型相同·个数有限·次序严格——三个关键词，缺一不可记作L=(a1，a2，…，an)，a1

为表头元素，an

为表尾元素关键词①类型相同元素全是同一类，要么全是整数，要么全是学生结构体，不能int和char混着来。关键词②有限n是有限数；n=0时为空表，不存在“无限多个元素”的线性表。关键词③序列元素有严格先后顺序，第1个、第2个……第n个，位置有讲究，不是无序集合。前驱与后继的唯一性“唯一前驱、唯一后继，让线性结构清晰可循。”“一对一，数据才可预测、可控制。”前驱与后继前驱除第一个元素外，每个元素有且仅有一个直接前驱。后继除最后一个元素外，每个元素有且仅有一个直接后继。三处特殊的元素表头a1：无前驱。表尾an：无后继。中间ai：前驱a(i-1)，后继a(i+1)。为什么“一对一”如此重要？一对一关系让遍历与查找简单高效。按时间顺序记录事件时，每个事件都能明确找到前后相邻事件，梳理过程毫不费力。逻辑连续不等于物理连续“逻辑连续是共性，物理是否连续决定落地方式。”逻辑结构元素之间"连续成线"的关系——第i个元素的前驱与后继唯一。物理结构元素在内存中的实际存放位置，不必然连续。两类实现顺序表：元素挨个放入一整块连续内存，底层用数组

链表：元素散落各处，用指针串成锁链

逻辑连续是共性，物理是否连续决定落地方式。看结构，更要看存储！02顺序表连续内存里的有序座位顺序表用连续内存存数据连续存储实现物理地址连续用一段物理地址连续的存储单元依次存放数据元素，逻辑相邻即物理相邻，一般以数组为底层。顺序表≠数组封装与升级顺序表在数组之上做了一层封装，提供增、删、改、查接口，并自动管理容量。数组vs顺序表：一个生活化类比数组：毛坯地，自己决定怎么盖顺序表：精装房，水电门禁已装好，直接调用现成接口随机访问O(1)直接定位，无需遍历数据集中连续存放，换来顺序表最大的优势——随机访问O(1)连续存储静态与动态顺序表动态结构用一次

O(n)

的扩容，换来了全程的空间弹性。一句话总结：一次

O(n)

的扩容，换来全程空间弹性，这笔交易很划算。静态顺序表定长数组，容量编译期固定。空间给少不够用，给多则浪费，实际开发中很少使用。动态顺序表动态数组，容量随元素增减扩展，通常扩容为原容量的1.5倍或2倍。动态结构三要素存储空间首地址（指针）已用元素个数

size当前可用容量

capacity扩容三步申请更大新连续空间拷贝原有元素释放旧空间，时间代价

O(n)随机访问让取值快到常数级按索引频繁查询的场景下，顺序表表现极佳，这是它对比链表最大的底气。核心机制目标元素地址=首元素地址+元素下标

×

单个元素占用字节数。计算只依赖首地址与下标，一步定位，不经过任何中间元素。生活类比房间号连续排列时，知道1号房位置即可直接推出50号房位置，无需从1号逐间找过去。复杂度结论按位访问为

O(1)；初始化分配空间、求表长、按下标修改元素同为

O(1)。应用判断按索引频繁查询的场景下，顺序表表现极佳，这是它对比链表最大的底气。按值查找要逐个比较01问题1按下标访问是

O(1)，直接命中02问题2按值查找需逐位比较，无捷径查按值查找的复杂度推演平均比较次数各位置等概率，平均

(n+1)/2

次结论舍去小项与系数，按值查找时间复杂度为

O(n)按值修改同样要先找到再改，因此也是

O(n)按下标是直达，按值是排查。顺序表插入要移动元素排队中间插一人：插入位置越靠前，后面挪动的人越多牵一发而动全身，正是顺序表动态操作的软肋最好情况表尾插到表尾，移动

0

次复杂度O(1)，一步到位最坏情况表头插到表头，移动

n

次复杂度O(n)，全员后移平均情况等概率n+1

种插入位置平均移动

n/2

次整体O(n)，约一半元素后移顺序表删除同样代价高至此顺序表操作复杂度齐全：按位访问极快，插入与删除在非尾部位置都要付出线性移动代价。求长度O(1)直接读元素个数清空O(1)只把个数置0删删除的时间代价同构与插入一致：删第i个元素后，其后所有元素都要前移补位。最好删表尾，移动

0

次，O(1)最坏删表头，移动

n−1

次，O(n)平均等概率删除，移动

(n−1)/2

次，复杂度

O(n)03单链表一节节车厢靠指针连起来链表节点由数据和指针组成节点各自独立，指针串成逻辑上的链节点=数据域+指针域数据域+指针域两个部分组成数据域存放数据本身指针域存放下一个节点的地址离散存储，靠指针成链节点分散在内存任意位置，像珍珠各自独立、用线串起；不再一次申请整块大内存，用多少申请多少。离散按需分配代价：失去随机访问找任意节点必须从头节点沿指针逐个后移；实际实现常设不存数据的头节点，简化空表与首元素操作。顺序查找头节点头插法每次插到链表最前新来的排最前，最终链表顺序与输入顺序恰好相反头插法建表三要点两步插入：新节点指针指向原第一个节点，头节点指针指向新节点建表成本：n个节点逐个插入，时间复杂度O(n)实现优势：代码简单，无需维护尾指针，是建链表最常用方式之一两步插入新节点指针指向原第一个节点头节点指针指向新节点建表成本n个节点逐个插入，时间复杂度

O(n)实现优势代码简单、无需维护尾指针，是建链表最常用方式之一尾插法保持输入顺序⇋1读入新数据新建节点并接入›2尾指针指向它›3尾指针更新为新节点输入a1、a2、a3→生成a1→a2→a3，顺序与输入一致两者建表均需逐个插入n个节点时间复杂度同为

O(n)头插法每次插到头部，链表顺序与输入顺序完全相反。尾插法每次把新节点接到链表末尾，额外维护一个尾指针始终指向当前最后一个节点。两种建表方式取舍头插法无需维护尾指针，代码更简洁尾插法保留数据自然顺序，需要链表顺序与输入一致时选用按位查找只能逐个向后走“顺序表靠‘算地址’，链表只能‘往前走’。”—时间复杂度：O(n)顺序表就像一排固定座位的电影院，每个人都知道自己的座位号——靠下标算地址，一步到位。链表像寻宝游戏：每个盒子里只有一张字条，告诉你下一个盒子在哪里。节点分散，无法直接定位，只能从头沿

next

逐个后移。1找第1个节点从头开始只需比较

1

次，一步到位2找第2个节点多走一步需要比较

2

次，逐个后移n找第n个节点一直往前走需要比较

n

次，一直走到头按值查找同样是线性扫描问题→对策顺序查找的代价

现状按值查找无法跳过遍历，必须从首节点起逐个比较数据域。

代价量化最好：目标在首节点，比较

1次最坏：目标在末节点，比较

n次平均：等概率下

(n+1)/2次，复杂度

O(n)

启示按位、按值都绕不开“从头走到目标位置”这趟线性扫描——这是链表换灵活插入删除的核心代价，也是查询频繁场景不选链表的依据。链表插入只需改两个指针

核心底气只改指针、不动元素，是链表在频繁增删场景下的底气。核心动作在第

i

位插入，先找到第

i−1

个节点，新节点指向原第i个节点，第i−1个节点指向新节点代价与边界插入动作本身

O(1)，不移动任何元素；但从头找第i−1个节点仍是

O(n)生活类比队伍中间加新人，只需前后两人牵手，其他人原地不动链表删除同样是顺手改指针1删除节点先找到前驱第

i−1

个，让它的指针直接跳过被删节点、指向第

i+1

个，动作本身

O(1)。2摘链环把一环摘下来，只需把前后两环连上，其余环节纹丝不动。空间代价int占

4字节，64位系统指针占

8字节，一个节点共

12字节真正存数据的只有

4字节，存储密度仅约33%顺序表只存数据本身，存储密度可达100%链表按需分配顺序表可能预分配浪费高效增删，是用空间换来的。04对比与选型读多选顺序，写多选链表连续与离散决定访问方式顺序表与链表在存储与访问上的核心差异连续内存换随机访问，指针连接换灵活插入连续指针存储结构第一层·数据怎么摆顺序表集中存放在连续内存，元素物理相邻链表分散各处，节点靠指针相连记忆口诀：顺序表=一排连号的宿舍房间；链表=胡同里靠指路牌串起的各家访问方式第二层·怎么找到元素顺序表：首地址+偏移量直接定位，按下标取值

O(1)，支持随机访问链表：从头节点逐个遍历，时间复杂度

O(n)，无随机访问能力记忆口诀：顺序表=图书馆编号书架，报号即取；链表=寻宝游戏，必须一站站问下去遍历效率第三层·运行时谁更快顺序表：连续地址利于CPU预取后续元素链表：指针跳转导致反复访问内存记忆口诀：顺序表=高铁直达；链表=每站停靠的慢车增删效率是两者的分水岭同一存储结构，读与写是两副面孔。读操作顺序表赢，写操作链表赢——频繁增删的场景，链表几乎是不二之选。顺序表写操作代价高表尾插入或删除末元素：无需移动，O(1)其他位置：需整体后移或前移大量元素最坏情况：在第一个位置前插入，n个元素全部后移，O(n)队伍中间插一人→后面所有人整体后挪一位链表写操作轻量找到位置后，插入和删除只需修改一两个指针不动任何其他元素，动作本身

O(1)新人只需和前后两人重新牵一下手结论读操作顺序表赢，写操作链表赢——频繁增删的场景，链表几乎是不二之选。VS空间利用与缓存各有得失空间与缓存，顺序表占优；内存灵活性，链表占优。空间与缓存，顺序表占优；内存灵活性，链表占优。顺序表存储密度：只存数据，无指针开销，密度高内存灵活性：静态容量固定易浪费；动态扩容申请连续大块，内存碎片多时可能失败缓存友好性：数据连续存放，符合空间局部性原理，缓存命中率高链表存储密度：每节点额外存指针，单节点开销大内存灵活性：按需申请、用多少要多少，无预分配、无溢出缓存友好性：节点离散、指针跳转，缓存命中率低即使遍历复杂度同为

O(n)，顺序表实际执行效率也略高于链表。VS读多写少的选表原则一条原则定选型读多写少选顺序表，写多读少选链表。读多写少→顺序表频繁按索引访问、查询多、增删少典型场景：成绩排名查询、商品列表展示关键支撑：随机访问

O(1)，查询又快又省写多读少→链表数据频繁增减、插入删除多、查询少典型场景：顾客排队管理、消息队列关键支撑：增删只改指针，不牵一发动全身一个判断例子超市或咖啡店顾客来来往往，不断有人加入、有人离开，本质是持续的插入和删除——该用链表。选型本质选数据结构的本质，是根据业务操作频率，选择更能扬长避短的那一种。05实战与应用把知识用到真实项目