数据结构:链表详解(单链表、双链表、循环链表)
系统讲解了数据结构中链表的各类实现与操作。涵盖单链表的初始化、判空、查找、插入、删除及建表方法;双链表的节点插入、删除与销毁;循环链表与静态链表的特性;并对比了顺序表与链表在存取方式、逻辑物理结构、操作复杂度及空间分配上的差异。内容适合计算机专业学生及开发者复习链表核心知识点。

系统讲解了数据结构中链表的各类实现与操作。涵盖单链表的初始化、判空、查找、插入、删除及建表方法;双链表的节点插入、删除与销毁;循环链表与静态链表的特性;并对比了顺序表与链表在存取方式、逻辑物理结构、操作复杂度及空间分配上的差异。内容适合计算机专业学生及开发者复习链表核心知识点。

它的实现逻辑是,通过一组任意的存储单元来存储线性表中的数据元素。
为建立数据元素之间的关系,对于每个结点内,除了要存放自身元素信息之外,还要存放一个指向其后继的指针。单链表结点结构图示如下:
其中 data 为数据域,用于存放数据元素;next 为指针域,用于存放后继结点的地址。
单链表中的结点声明如下:
typedef struct LNode { //定义单链表结点类型
ElemType data; //数据域
struct LNode* next; //指针域
}LNode, *LinkList;
注意:代码使用 LNode 时,强调这是一个结点;代码使用 LinkList 时,强调这是一个单链表。*
单链表的元素并非连续存放在存储空间中,而是离散分布,所以其存储结构是顺序存取而非随机存取。所以在查找特定元素时,需要从表头开始遍历,依次查找,效率较低。
头节点和头指针的关系:无论是否有头节点,头指针始终指向链表的第一个结点,而头结点是带头链表的第一个结点,该结点内通常不存储信息。
引入头结点的优点:
这是带头结点的单链表初始化函数,先申请一块内存当这个头结点,再把它的 next 指针设成空,代表现在链表还没存任何有效数据,最后返回初始化成功的结果。
bool InitList(LinkList& L) //带头结点的单链表初始化
{
L = (LNode*)malloc(sizeof(LNode)); //创建头结点
L->next = NULL; //头结点之后暂时没有元素节点
return true;
}
这是不带头结点的单链表初始化,逻辑更简单,直接把链表的头指针设成 NULL,就代表这个链表现在是空的,初始化就完成了,最后返回成功的状态。
bool InitList(LinkList& L)
{
L = NULL;
return true;
}
这是带头结点单链表的判空函数,给它传链表的头指针,它就帮你检查这个链表有没有存有效数据的节点,要是链表啥数据都没有,就返回 true,有数据的话就返回 false。
bool Empty(LinkList L)
{
if (L->next == NULL) //如果 L->next 为 NULL,说明链表没有任何有效数据节点,是空链表
return true;
else
return false;
}
这函数是用来算链表长度的,也就是数链表里有多少个存数据的节点。它会顺着链表一个一个往下走,每数到一个节点就给计数器加 1,直到走到链表的末尾,最后把数出来的总个数返回给你。
int Length(LinkList L)
{
int len = 0; //定义计数器 len,初始值为 0,用来统计数据节点的个数
LNode* p = L; //定义遍历用的指针 p,初始指向链表的头结点
while (p->next != NULL) //只要当前节点的下一个节点不为空,说明还有未统计的数据节点,继续遍历
{
p = p->next; //指针向后移动,走到下一个数据节点
len++; //每遍历到一个数据节点,计数器加 1
}
return len; //遍历结束,返回统计好的链表长度
}
这是按序号找节点的函数,给他要查的链表、还有要找的是第几个节点,它就顺着链表挨个往下找,找到对应节点就把这个节点的地址返回给你;要是你给的序号不对、或者链表没这么长,就返回 NULL,告诉你没找到对应的节点。
LNode* GetElem(LinkList L, int i)
{
LNode* p = L; //定义遍历用的指针 p,初始指向链表的头结点
int j = 0; //定义计数器 j,记录当前指针指向的节点序号,初始值 0 对应头结点
while (p != NULL && j < i) //只要指针没走到链表末尾,且还没到达目标序号 i,就继续遍历查找
{
p = p->next; //指针向后移动,走到下一个节点
j++; //计数器加 1,更新当前节点的序号
}
return p; //遍历结束,返回找到的节点地址(没找到对应节点则返回 NULL)
}
这是按值找节点的函数,给它要查的链表、还有要找的目标数值,它就顺着链表挨个节点看,找到第一个存了这个数值的节点,就把节点的地址返回给你;要是整个链表都找完了都没这个数,就返回 NULL,告诉你查找失败了。
LNode* LocateElem(LinkList L, ElemType e)
{
LNode* p = L->next; //定义遍历用的指针 p,初始指向第一个数据节点(跳过不存数据的头结点)
while (p != NULL && p->data != e) //只要指针没走到链表末尾,且当前节点的数据不等于目标值 e,就继续向后查找
p = p->next; //指针向后移动,检查下一个节点
return p; //遍历结束,返回找到的匹配节点地址(没找到对应节点则返回 NULL)
}
这是带头结点链表的按位置插入函数,给它要操作的链表、要在第几个位置插、还有要插入的数,它会先检查你给的位置是否合法,然后找到要插的位置的前一个节点,把新节点插进去,插成功了就返回 true,位置不对就返回 false。
bool ListInsert(LinkList& L, int i, ElemType e)
{
if (i < 1) //检查位序合法性
return false;
LNode* p = L; //定义遍历指针 p,初始指向链表的头结点
int j = 0; //定义计数器 j,记录当前 p 指向的节点序号,初始 0 对应头结点
while (p != NULL && j < i - 1) //循环找到第 i-1 个前驱节点:只要 p 不为空,且还没到第 i-1 个节点,就继续遍历
{
p = p->next; //指针向后移动,走到下一个节点
j++; //计数器加 1,更新当前节点的序号
}
if (p == NULL) //如果 p 为空,说明 i 超过了链表的长度,位置不合法,返回 false
return false;
LNode* s = (LNode*)malloc(sizeof(LNode)); //申请内存,创建一个新的节点 s
s->data = e; //给新节点的 data 域赋值,存入要插入的元素 e
s->next = p->next; //新节点的 next 指向 p 原来的下一个节点,把链表后续的节点接在新节点后面
p->next = s; //p 的 next 指向新节点,把新节点接在 p 的后面,完成插入
return true; //插入成功,返回 true
}
这是不带头结点链表的按位置插入函数,和带头的不一样,插第一个位置的时候要单独处理,因为要修改链表的头指针;其他位置的话,也是先找到要插的位置的前一个节点,再把新节点插进去,插成功了返回 true,位置不合法就返回 false。
bool ListInsert(LinkList& L, int i, ElemType e)
{
if (i == 1) //单独处理插入第 1 个位置的情况(不带头结点的链表,插第一个位置要修改头指针)
{
LNode* s = (LNode*)malloc(sizeof(LNode)); //申请内存,创建新节点 s
s->data = e; //给新节点赋值元素 e
s->next = L; //新节点的 next 指向原来的头节点,把原来的链表接在新节点后面
L = s; //头指针 L 指向新节点,新节点成为新的头节点
return true;
}
int j = 1; //处理插入位置不是第 1 位的情况:定义计数器 j,初始 1 对应第一个节点的序号
LNode* p = L; //定义遍历指针 p,初始指向链表的第一个节点(头指针 L)
while (p != NULL && j < i - 1) //循环找到第 i-1 个前驱节点:只要 p 不为空,且还没到第 i-1 个节点,就继续遍历
{
p = p->next; //指针向后移动,走到下一个节点
j++; //计数器加 1,更新当前节点的序号
}
if (p == NULL) //如果 p 为空,说明 i 超过了链表的长度,位置不合法,返回 false
return false;
LNode* s = (LNode*)malloc(sizeof(LNode)); //申请内存,创建新节点 s
s->data = e; //给新节点赋值元素 e
s->next = p->next; //新节点的 next 指向 p 原来的下一个节点,接好后续链表
p->next = s; //p 的 next 指向新节点,完成插入
return true;
}
这是给已知节点前插元素的函数,传入已知的节点指针 p,有要插入的数 e,它就能直接在 p 的前面插入新节点,不用从头遍历链表。操作成功就返回 true,要是你给的 p 是空的,就返回 false。
bool InsertPriorNode(LNode* p, ElemType e)
{
if (p == NULL) //如果节点 p 为空,位置不合法,直接返回 false
return false;
LNode* s = (LNode*)malloc(sizeof(LNode)); //申请内存,创建新节点 s
s->next = p->next; //新节点的 next 指向 p 的下一个节点,把新节点插在 p 的后面
p->next = s;
s->data = p->data; //把 p 原来的数据复制到新节点 s 里
p->data = e; //把要插入的元素 e 存入 p 节点,相当于 p 变成了新插入的节点,s 变成了原来的 p 节点,实现前插效果
return true;
}
这是给已知节点后插元素的函数,传入已知节点的指针 p、要插入的元素 e,函数会在节点 p 的后面插入新元素 e。不用从头遍历链表,直接修改节点的指针即可完成插入,操作成功返回 true,若节点 p 为空则返回 false。
bool InsertNextNode(LNode* p, ElemType e)
{
if (p == NULL) //如果传入的节点 p 为空,位置不合法,直接返回 false,终止操作
return false;
LNode* s = (LNode*)malloc(sizeof(LNode)); //申请内存,创建一个新的节点 s,用来存放要插入的元素
s->data = e; //给新节点的 data 域赋值,存入要插入的元素 e
s->next = p->next; //新节点 s 的 next 指向 p 原来的下一个节点,把 p 后续的链表接在新节点后面
p->next = s; //把 p 的 next 指向新节点 s,将新节点接在 p 的后面,完成后插操作
return true;
}
入链表头指针 L、要删除的位置 i、用来接收被删除元素的变量 e,函数会检查删除位置的合法性,找到第 i-1 个前驱节点,删除第 i 个节点并释放内存,删除成功返回 true,位置不合法返回 false。
bool ListDelete(LinkList& L , int i, ElemType& e)
{
LNode* p = L; //定义遍历指针 p,初始指向链表的头结点
int j = 0; //定义计数器 j,记录当前 p 指向的节点序号,初始 0 对应头结点
while (p->next != NULL && j < i - 1) //循环找到第 i-1 个前驱节点:只要 p 的下一个节点不为空,且还没到第 i-1 个节点,就继续遍历
{
p = p->next; //指针向后移动,走到下一个节点
j++; //计数器加 1,更新当前节点的序号
}
if (p->next == NULL || j > i - 1) //校验位置合法性:如果 p 的下一个节点为空(要删除的节点不存在),或者 j 超过了 i-1(位置非法),返回 false
return false;
LNode* q = p->next; //用指针 q 指向要删除的第 i 个节点(p 的下一个节点)
e = q->data; //把被删除节点的元素值赋值给 e,带出去给调用者
p->next = q->next; //把 p 的 next 指向 q 的下一个节点,跳过要删除的节点,把链表接好
free(q); //释放 q 节点的内存,避免内存泄漏
return true;
}
传入链表头指针 L,函数会初始化带头结点的空链表,循环读取用户输入的整数,每读一个数就把它作为新节点插到链表头结点的后,直到输入 9999 停止,最终返回建立好的链表头指针。
LinkList List_HeadInsert(LinkList& L)
{
LNode* s; //定义新节点指针 s,和用来接收用户输入的变量 x
int x;
L = (LNode*)malloc(sizeof(LNode)); //申请内存,创建链表的头结点
L->next = NULL; //头结点的 next 置为 NULL,初始化空链表
scanf("%d", &x); //读取用户输入的第一个整数,存入 x
while (x != 9999) //循环:只要输入的 x 不是 9999,就继续插入节点
{
s = (LNode*)malloc(sizeof(LNode)); //申请内存,创建新节点 s
s->data = x; //给新节点赋值,存入用户输入的 x
s->next = L->next; //新节点的 next 指向头结点原来的下一个节点,接好链表的后续部分
L->next = s; //头结点的 next 指向新节点,把新节点插到链表头部
scanf("%d", &x); //读取下一个用户输入的整数,继续循环
}
return L;
}
传入链表头指针 L,函数会初始化带头结点的空链表,用尾指针 r 记录链表的最后一个节点,循环读取用户输入的整数,每读一个数就把它作为新节点插到链表的尾部,直到输入 9999 停止,最终返回建立好的链表头指针。
LinkList List_TailInsert(LinkList& L)
{
int x; //定义用来接收用户输入的变量 x
L = (LNode*)malloc(sizeof(LNode)); //申请内存,创建链表的头结点
LNode* s, * r = L; //定义新节点指针 s,和尾指针 r,初始 r 指向头结点(空链表的尾部就是头结点)
scanf("%d", &x); //读取用户输入的第一个整数,存入 x
while (x != 9999) //循环:只要输入的 x 不是 9999,就继续插入节点
{
s = (LNode*)malloc(sizeof(LNode)); //申请内存,创建新节点 s
s->data = x; //给新节点赋值,存入用户输入的 x
r->next = s; //尾指针 r 的 next 指向新节点,把新节点接到链表的尾部
r = s; //尾指针 r 移动到新节点,更新为新的链表尾部
scanf("%d", &x); //读取下一个用户输入的整数,继续循环
}
r->next = NULL; //循环结束,把链表最后一个节点的 next 置为 NULL,标记链表结束
return L; //链表建立完成,返回链表的头指针
}
单链表中只有一个指向后继结点的指针,这导致其在执行查找、插入和删除等操作的时候只能从头开始遍历,时间复杂度为 O(n) 。所以双链表的产生就是为了解决这种问题,其拥有 prior 指针和 next 指针,分别指向其直接前驱和直接后继。双链表结点结构图示如下:

单链表中的结点声明如下:
typedef struct DNode { //定义双链表结点类型
ElemType data; //数据域
struct DNode* prior, * next; //前驱指针和后驱指针
}DNode, *DLinklist;
注意:代码使用 DNode 时,强调这是一个结点;代码使用 DLinkList 时,强调这是一个双链表。*
双链表的按值查找和按位查找时间复杂度与单链表持同,因为其都为顺序存取结构;但是其插入与操作快于单链表,因为双链表拥有前驱指针,可以很容易地找到前一结点,时间复杂度为 O(1) 。
这是带头结点的双链表初始化函数,说白了就是给双链表建一个头结点,先申请一块内存当这个头结点,要是内存申请失败就返回 false;申请成功的话,就把头结点的前驱指针 prior 和后继指针 next 都设成 NULL,代表现在链表是空的,最后返回初始化成功的 true。
bool InitDLinklist(DLinklist& L)
{
L = (DNode*)malloc(sizeof(DNode)); //申请一块内存,大小是一个 DNode 节点的大小,把申请到的地址赋值给头指针 L,也就是创建头结点
if (L == NULL) //如果 L 是 NULL,说明刚才申请内存失败了,直接返回 false
return false;
L->prior = NULL; //把头结点的前驱指针 prior 设为 NULL,头结点前面没有节点
L->next = NULL; //把头结点的后继指针 next 设为 NULL,头结点后面也没有节点,现在链表是空的
return true;
}
这是双链表的节点后插函数,给它一个已知的节点 p,还有要插入的新节点 s,它就能把 s 插到 p 的后面。因为双链表有前后两个指针,所以要把新节点和前后的节点的指针都接好,要是 p 或者 s 是空的,就直接返回 false,操作成功就返回 true。
bool InsertNextDNode(DNode* p, DNode* s)
{
if (p == NULL || s == NULL) //如果 p 是空的,或者 s 是空的,位置不合法,直接返回 false
return false;
s->next = p->next; //让新节点 s 的后继指针,指向 p 原来的下一个节点,先把 p 后面的链表接在 s 的后面
if (p->next != NULL) //如果 p 原来的下一个节点不是空的
p->next->prior = s; //让 p 原来的后继节点的前驱指针,指向新节点 s,把后面节点的前向指针接好
s->prior = p; //让新节点 s 的前驱指针,指向节点 p,把 s 和 p 的前向关系接好
p->next = s; //让 p 的后继指针,指向新节点 s,把 p 和 s 的后向关系接好,完成插入
return true;
}
这是双链表的节点删除函数,作用是删掉节点 p 后面的那个节点。它会先检查 p 是不是空的,还有 p 后面有没有节点可以删,要是没的删就返回 false;有的话就把链表的前后指针重新接好,跳过要删的节点,再释放掉这个节点的内存,避免内存泄漏,删成功了就返回 true。
bool DeleteNextNode(DNode* p)
{
if (p == NULL) //如果 p 是空的,位置不合法,直接返回 false
return false;
DNode* q = p->next; //用指针 q 指向 p 的后继节点,也就是我们要删掉的节点
if (q == NULL) //如果 q 是空的,说明 p 后面没有节点,没的可删,返回 false
return false;
p->next = q->next; //让 p 的后继指针,直接指向 q 的下一个节点,跳过要删的 q 节点,把链表的后向接好
if (q->next != NULL) //如果 q 的下一个节点不是空的(也就是 q 不是链表最后一个节点)
q->next->prior = p; //让 q 的后继节点的前驱指针,指向 p,把链表的前向接好
free(q); //释放掉 q 节点的内存,把要删的节点彻底清掉,避免内存泄漏
return true;
}
这是销毁整个双链表的函数,说白了就是把整个链表的所有节点都删掉,释放所有占用的内存,避免内存泄漏。它会循环调用刚才的删除函数,一直删掉头结点后面的所有节点,最后把头结点也释放掉,再把头指针设成 NULL,整个链表就彻底销毁了。
void DestroyList(DLinklist& L)
{
while (L->next != NULL) //循环:只要头结点的后面还有节点,就继续删
DeleteNextNode(L); //调用删除函数,删掉头结点后面的第一个节点,循环执行直到所有数据节点都被删掉
free(L); //所有数据节点都删完了,现在释放头结点的内存
L = NULL; //把头指针 L 设为 NULL,避免变成野指针
return;
}
循环单链表与单链表的区别就是,原来表尾指针指向 NULL 的,现在改为指向头结点。
循环单链表结点结构图示如下:

因此循环单链表中不会出现指针域指向 NULL 的结点,因此判空条件从是否头结点指向 NULL 改为是否等于头指针 L。
**判空:*L->next == L;
**判 p 是否为尾:*p->next == L;
循环双链表相比循环单链表增加了头结点的 prior 指针也将指向表尾结点这一点。
循环双链表结点结构图示如下:

同理,循环双链表的判空条件是头结点的 prior 指针和 next 指针是否都指向头指针 L。
**判空:*L->next == L; L->prior == L;
**判 p 是否为尾:*p->next == L;
静态链表说白了就是用数组来实现线性表的链式存储结构,结点同样也分为用来存我们要放的实际数据的数据域 data 和指针域 next。不过这里的'指针'不是真正的内存地址,而是下一个节点在数组里的下标(也叫游标)。
**注意:**静态链表的数组大小是我们提前定好的,所以它能存的节点数量有固定上限,不能像动态链表那样随便加节点。
静态链表结点结构图示如下:

静态链表中的结点声明如下:
#define MaxSize 50 //宏定义一个静态链表的最大长度
typedef struct { //静态链表结构类型的定义
ElemType data; //存储数据元素
int next; //下一个元素的数组下标
}SLinkList[MaxSize];
静态链表以 next == -1 作为结束标志,因为数组的下标都是 ≥0 的正数,-1 就代表'这个节点后面没有其他节点了',作用和动态链表最后一个节点的 next=NULL 是一模一样的。
其余操作与动态链表几乎相同,比如插入、删除节点,都只需要修改 next 指针,不用移动其他元素。唯一的小区别是,静态链表不用手动申请、释放节点的内存,而是从我们提前开好的数组里找空闲的位置来用,动态链表则是需要的时候才申请内存。
顺序表:支持随机存取和顺序存取。
顺序表的本质是数组,只要给出元素的下标,就可以直接通过内存地址计算一步找到对应元素,时间复杂度为 O(1) 。比如我们要找顺序表的第 5 个元素,直接访问 data[4] 就能拿到,不需要遍历前面的元素。
链表:仅支持顺序存取。
链表的节点在内存中是分散的,要找到第 i 个元素,必须从链表的头结点开始,顺着指针一个一个遍历到目标位置,无法直接跳转到对应节点,时间复杂度为 O(n) 。比如要找链表的第 5 个元素,必须从第 1 个开始,依次往后数 4 次才能找到。
顺序表:采用顺序存储。逻辑上相邻,物理存储位置也相邻。
链表:采用链式存储。逻辑上相邻,物理存储位置不一定相邻。
**按序查找:**顺序表的随机存取结构使得时间复杂度为 O(1) ;链表必须从头开始遍历查找,所以时间复杂度为 O(n) 。
**按值查找:**如果表内元素是无序的,则顺序表和链表都必须从头开始找,时间复杂度均为 O(n) ;如果表内元素是有序的,则顺序表可以用二分法查找,时间复杂度为 O(nlog2n) ,而链表时间复杂度依旧为 O(n) 。
顺序表:分为静态分配顺序表和动态分配顺序表。
对于静态分配顺序表,数组大小在初始化的时候就已经定死了,若分配量过小,元素量超出存储空间上限就会溢出导致运行崩溃;若分配量过大,会使得空间闲置浪费。
而动态分配顺序表,虽然可以在存储空间不够用时随时扩容,但是它的扩容是开一个新空间,然后把旧空间装不下的内容全部复制到新空间中,操作量大,效率极低。并且还可能因为找不到足够大的连续内存而扩容失败.
**链表:**其结点内存是在插入时才申请、删除时就释放的,不需要提前确定链表的最大长度,只要系统还有可用内存,就可以继续添加结点;同时结点可以利用内存中零散的空闲空间,不会出现大块内存闲置的问题,唯一的空间开销是每个结点需要额外的内存来存放指针。

微信公众号「极客日志」,在微信中扫描左侧二维码关注。展示文案:极客日志 zeeklog
使用加密算法(如AES、TripleDES、Rabbit或RC4)加密和解密文本明文。 在线工具,加密/解密文本在线工具,online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具,Base64 字符串编码/解码在线工具,online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具,Base64 文件转换器在线工具,online
将 Markdown(GFM)转为 HTML 片段,浏览器内 marked 解析;与 HTML 转 Markdown 互为补充。 在线工具,Markdown 转 HTML在线工具,online
将 HTML 片段转为 GitHub Flavored Markdown,支持标题、列表、链接、代码块与表格等;浏览器内处理,可链接预填。 在线工具,HTML 转 Markdown在线工具,online
通过删除不必要的空白来缩小和压缩JSON。 在线工具,JSON 压缩在线工具,online