线性表（顺序表与链表）

靳夏萱 · 2026-2-11 16:55:07

一、线性表

线性表（linear list）是n个具有相同特性的数据元素的有限序列。线性表是⼀种在实际中⼴泛使⽤的数据结构，常⻅的线性表：顺序表、链表、栈、队列、字符串...

线性表在逻辑上是线性结构，也就说是连续的⼀条直线。但是在物理结构上并不⼀定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。

所有的逻辑都是人为定义与解释的的，所谓的线性有时候也让人迷惑，所以更加纯粹的是物理结构，只有掌握了能使用的物理结构，才能从中开始抽象出线性。经过查找与分析，线性结构的存储方式 实际上就两种：数组和链表，其余的各种衍生不过是二者的结合。

1.链表（纯指针查找思想，指针链接）
2.数组（纯连续存放数据，线性索引）
3.指针数组+链表（链表与数组混合使用，如下表）

术语	存储结构	逻辑结构	思想
静态链表	指针数组	每个结点的下标连接	用数组实现链表
间接寻址	指针数组	索引+解引用	数组思想，但元素分散
块状链表	数组块+指针	块内数组+块间链表	数组+链表混合
内存池	大数组	链表管理	数组存储+链表逻辑
文件存储	文件（字节数组）	偏移量索引或连接	数组思想或链表思想

追究线性表数据结构其根源在于怎么样储存多个单位的数据，在我们学习C时有提到大小端，结构体字段，内存对齐（数组与结构体）的思想，其产生了链表，数组的基础结构，随着深入发掘，进而产生了数据结构。————————继续挖掘ing
二、顺序表

2.1概念：

顺序表是⽤⼀段物理地址连续的存储单元依次存储数据元素的线性结构，⼀般情况下采⽤数组存储（底层逻辑，线性体现在随机索引上（线性索引））。

2.2顺序表的底层结构

顺序表的底层结构是数组，对数组的封装，实现了常⽤的增删改查等接⼝
图解：

2.3静态顺序表

概念：使⽤定⻓数组存储元素
静态顺序表缺陷：空间给少了不够⽤，给多了造成空间浪费
定义：

typedef int SLDataType;//便于修改线性表数据类型#define SIZE 4//便于修改线性表大小typedef struct SeqList{ SLDataType arr[SIZE]; int size;}SL;

复制代码

2.4动态顺序表

概念：使⽤动态数组存储元素
定义：

typedef int SLDataType;//便于修改线性表数据类型typedef struct SeqList{ SLDataType* arr; int capacity;//可用容量 int size;//已用大小}SL;

复制代码

2.5顺序表的增删查及其提供的思想

1.增删改查代码

查看代码

//sl.h#pragma once#define _CRT_SECURE_NO_WARNINGS#include #include#include#include#define INIT_CAPACITY 4typedef int SLDataType;//便于修改线性表数据类型typedef struct SeqList{ SLDataType* arr; int capacity;//可用容量 int size;//已用大小} SeqList;// 对数据的管理:增删查改 void SeqListInit(SeqList* ps);void SeqListAdd(SeqList* ps);void SeqListDestroy(SeqList* ps);void SeqListPrint(const SeqList* ps);void SeqListPushBack(SeqList* ps, const SLDataType x);void SeqListPushFront(SeqList* ps, const SLDataType x);void SeqListPopFront(SeqList* ps);void SeqListPopBack(SeqList* ps);// 顺序表查找int SeqListFind(const SeqList* ps, const SLDataType x);// 顺序表在pos位置插入xvoid SeqListInsert(SeqList* ps, const int pos, const SLDataType x);// 顺序表删除pos位置的值void SeqListErase(SeqList* ps,const int pos);//sl实现.c#include"sl.h"//初始化void SeqListInit( SeqList* ps){ assert(ps);//排除传入空指针的错误情况 ps->arr = NULL; ps->size = 0; ps->capacity = 0;}//打印void SeqListPrint(const SeqList* ps){ assert(ps);//排除传入空指针的错误情况 for (int i = 0; i < ps->size; i++) { printf("%d ", ps->arr[i]); } printf(" ", plist->data); plist = plist->next; } printf("NULL\n");}void SListPushBack(SListNode** pplist,const SLTDateType x){ assert(pplist);//防止传入空指针 //处理链表为空的情况 if (!*pplist) { *pplist = BuySListNode(x); return; } //处理链表非空的情况 SListNode* tail = *pplist; while (tail->next) { tail = tail->next; } tail->next = BuySListNode(x);}void SListPushFront(SListNode** pplist,const SLTDateType x){ assert(pplist); //处理链表为空的情况 if (!*pplist) { *pplist = BuySListNode(x); return; } //处理链表非空的情况 SListNode* temp = BuySListNode(x); temp->next = *pplist; *pplist = temp;}void SListPopBack(SListNode** pplist){ assert(pplist);//防止传入空指针 //处理链表为空的情况 if (!*pplist) { return; } //处理链表非空的情况 SListNode* pre = *pplist; SListNode* tail = (*pplist)->next; //处理一个元素的情况 if (!tail) { *pplist = NULL; } //处理链表非一个元素的情况 else { while (tail->next) { tail = tail->next; pre = pre->next; } pre->next = NULL; } free(tail); tail = NULL;}void SListPopFront(SListNode** pplist){ assert(pplist);//防止传入空指针 //处理链表为空的情况 if (!*pplist) { return; } //处理链表非空的情况 SListNode* temp = (*pplist)->next; *pplist = (*pplist)->next; free(temp); temp = NULL;}SListNode* SListFind(const SListNode* plist,const SLTDateType x){ if (!plist) { printf("未找到！\n"); return plist; } SListNode* temp = plist; while (temp&&temp->data!=x) { temp = temp->next; } if(!temp) printf("未找到！\n"); else printf("找到了！\n"); return temp;}void SListInsertAfter(SListNode* pos,const SLTDateType x){ if (!pos) { printf("传入空指针，插入失败!\n"); return; }//排除空链表，设计使然无法在空链表中插入一个节点 SListNode* temp = BuySListNode(x); temp->next = pos->next; pos->next = temp;}void SListEraseAfter(SListNode* pos){ if ((!pos)||(pos->next==NULL))//排除空链表和Pos为尾结点的情况 { printf("传入空链表或尾结点，删除失败!\n"); return; } SListNode* temp = pos->next; pos->next = pos->next->next; free(temp); temp = NULL;}void SListInsert(SListNode** pphead, const SListNode* pos,const SLTDateType x){ if (!pphead || !pos) { printf("传入空指针或者无此结点，插入失败！\n"); return; } //处理pos是首结点的情况 SListNode* temp = BuySListNode(x); if (pos == *pphead) { temp->next = *pphead; *pphead = temp; return; } //处理pos后续情况 SListNode* pre = *pphead; while (pre->next != pos) { pre = pre->next; } temp->next = pre->next; pre->next = temp;}void SListErase(SListNode** pphead,const SListNode* pos){ if (!pphead || !pos) { printf("传入空指针或者无此结点，删除失败！\n"); return; } //处理pos是首结点的情况 if (pos == *pphead) { SListNode* temp = *pphead; *pphead = (*pphead)->next; free(temp); temp = NULL; return; } //处理pos后续情况 SListNode* pre = *pphead; while (pre->next != pos) { pre = pre->next; } pre->next=pos->next; free(pos); pos = NULL; return;}void SListDestroy(SListNode** pphead){ assert(pphead);//传入空指针 if (!*pphead)//处理空链表 { return; } while ((*pphead)->next) { SListNode* del = (*pphead)->next; (*pphead)->next = (*pphead)->next->next; free(del); } free(*pphead); *pphead = NULL;}

复制代码

2.复杂度及其思路

增：
头插：时间O（1）
尾插：时间O（N），需要找到尾节点，分类处理空链表情况。

指定位置前插入数据：时间O（N），需要查找指定位置前元素（O（N））进行修改，同时分情况，是否为首元素，涉及头节点更改
指定位置后插入数据：时间O（1）

思想：将新节点先进行前后结点的相连，再对原链表进行修订
分类依据：前插与后插操作不同（不支持随机访问导致）

分析思考为什么不在pos位置之前插入？

1.单链表单向性
单链表每个节点只有指向下一个节点的指针，没有指向前一个节点的指针。如果要在 pos 之前插入，必须知道 pos 的前驱节点，而单链表无法从 pos 直接得到前驱节点。

2.要找到前驱节点需要从头遍历,除非我们额外维护一个指向 pos 前驱的指针，否则需要从头节点开始遍历，直到某个节点的 next 等于 pos，时间复杂度 O(n)。

3.边界情况：pos 是头节点
在 pos 之前插入意味着新节点要成为新的头节点，需要修改链表的外部头指针（调用者需要更新头指针），这会使接口复杂。

删：
头删：时间O（1）
尾删：时间O（N），需要查找前一个元素进行修改

指定位置前删除：时间O（N），需要查找指定位置前元素（O（N））进行修改，同时分情况，是否为首元素，涉及头节点更改
指定位置后删除数据：时间O（N），需要查找指定位置前元素（O（N））进行修改。

销毁：O(N)依次遍历后进行依次释放

查：
遍历查询:O(N)

总结其特点：头插，尾插，删除的效率很高。

3.5链表数据结构应用

1.移除链表元素
https://leetcode.cn/problems/remove-linked-list-elements/description/

2.查找中间结点，查看链表是否带环（快慢指针应用）

https://leetcode.cn/problems/middle-of-the-linked-list/description/
https://leetcode.cn/problems/linked-list-cycle-ii/description/

3.合并两个有序链表（链表创建的便利性，哨兵位作用，尾插使用）
https://leetcode.cn/problems/merge-two-sorted-lists/description/

4.深度拷贝（链表的插入与创建的便利性，链表的复制）
https://leetcode.cn/problems/copy-list-with-random-pointer/description/

5.链表排序（链表创建的便利性）
https://www.nowcoder.com/practice/0e27e0b064de4eacac178676ef9c9d70?tpId=8&&tqId=11004&rp=2&ru=/activity/oj&qru=/ta/cracking-the-coding-interview/question-ranking

术语介绍：深度拷贝与浅拷贝

在软件开发中，数据复制是常见的操作场景。无论是处理用户输入、缓存中间结果，还是实现对象克隆，开发者都需要明确选择浅拷贝（Shallow Copy）还是深拷贝（Deep Copy）。这两种拷贝方式的核心差异在于对嵌套对象结构的处理方式，理解这一差异对避免程序中的意外行为至关重要。
浅拷贝是指创建一个新对象，并将原对象中所有字段的值复制到新对象中。对于基本数据类型（如Number、String、Boolean），会直接复制值；对于引用数据类型（嵌入的）（如Object、Array），则仅复制引用地址，新旧对象共享同一内存空间。
深拷贝不仅复制基本类型值，还会递归复制所有嵌套的引用类型，生成完全独立的新对象。新旧对象在内存中不存在任何共享部分。

持续更新ing———————————————》》》》》》》》》》》》》

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！

钱艷芳 · 7 天前

鼓励转贴优秀软件安全工具和文档！

简千叶 · 6 天前

谢谢分享，试用一下

愤血冒 · 3 天前

yyds。多谢分享

账号		自动登录	找回密码
密码			立即注册

线性表（顺序表与链表）

相关帖子

回复

浏览过的版块

签约作者

线性表（顺序表与链表）

相关帖子

相关推荐

回复

浏览过的版块

签约作者