数据结构——链表
本文详细的介绍了链表的概念与结构，并且手撕了两种常见的主要的链表基本逻辑和代码实现，希望能让大家更好的学习链表这种数据结构。
·
一、链表的概念
链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。就如同一列火车，每节车厢是独立的，靠车厢之间的挂钩连接在一起。链表中，那个“挂钩”就是指针，“车厢”存储数据，被称作结点，我们用一个个指针，访问链表中的节点，从而访问数据。
链表有几种性质：
1.链式机构在逻辑上是连续的，在物理结构上不⼀定连续
2.结点⼀般是从堆上申请的
3.从堆上申请来的空间，是按照⼀定策略分配出来的，每次申请的空间可能连续，可能不连续
- 链表的分类：
链表有几种特征作为分类依据：带头与不带头、单向与双向、循环与不循环。
根据这几种特征，链表一共有8种。
特征的说明：
- 带头与不带头：所谓“头”，其实应该叫做“哨兵位”，独立于链表，始终指向链表的第一个结点，但他本身并不是有效的结点，也不存储数据，只存储相应结点的地址，让我们能够找到链表的“头”
- 单向与双向：链表存在方向，如果单向，那么链表的每一个结点都只存储有该结点的下一个结点的地址，所以也只能访问下一个节点；如果是双向，那么每一个结点会存有该节点的上一个结点和下一个结点的指针，从而可以访问上下两个结点。因为链表的特性，链表只能按顺序一个一个访问，所以存在单向和双向的概念
- 循环与不循环：链表是通过指针连接所有的结点，如果某一个结点存储的指针指向了链表中已经访问过的结点，使得访问构成闭环，或者说每一个结点的指针都不为空，均指向链表的结点，这样就出现了循环，也就是链表中的某一些结点一起构成了访问闭环。
链表虽然有这么多的结构，但我们要知道的是，最常见的链表还是 “单链表” 和 “双链表” 两种：
- 单链表：结构最简单，一般不是单独来使用存储数据，而是最为其他数据结构的子结构或者辅助实现其他的复杂的数据结构，但它很是经典，我们还是要对它非常熟悉的。
- 双链表：其实全名是 带头双向循环链表 ，它的结构是最复杂的，一般使用链表都是用这种来单独存储数据，实际中的使用，一般也是用这种链表。它的结构复杂，但这样的结构反而能带来许多使用上的便利，甚至实现也会简单一点。
二、单链表
单链表作为最简单的结构，其全名为不带头单向不循环链表，本身就是一条数据链，一个个结点单向的链接起来，最后的一个结点指向空指针，代表链表到达了尾部。其结构体的模板是这样的：
typedef int SLTDatatype;//还是一样，方便修改数据类型
typedef struct SlistNode
{
SLTDatatype data;
struct SlistNode* next;
}SLTNode;//我自己修改的名字，后续写代码方便一些
作为数据结构，其实离不开那些基本的 “增删查改” 以及遍历等等那么下面我们直接手撕一下链表的基本操作：
-
申请新节点
每一次我们在链表中存储数据，都需要额外的新节点来存储，所以说链表的空间利用效率是很高的，有多少数据，链表就有多大空间。那么我们申请新结点都是一个独立的操作，也是申请一个同样的结构体作为结点，于是我们额外用一个函数来完成操作。SLTNode* BuylistNode(SLTDatatype x) { SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode)); if(newnode == NULL) { perror("malloc fail!"); exit(1); } newnode->data = 0;//申请结点的同时初始化 newnode->next = NULL; return newnode; } -
尾插
将新链表结点插入在尾部，因为我们不知道尾结点在哪，所以需要遍历链表先找到尾结点。同时这里还有一个重点，我们需要传递二级指针，而不是正常的传递一级指针从而通过这个指向结构体的指针。因为我们可能会传递空链表，也就是我们可能本身没有先创建一个结构体作为头结点，这时候我们是需要改变头结点的指向的，也就是让头结点从空指向非空的结点，也就是用二级指针改变一级指针的内容。void SLTPsuhBack(SLTNode** pphead,SLTDatatype x) { assert(phead); SLTNode* newnode = BuylistNode(x); if(*pphead == NULL) { *pphead = newnode;//将新节点作为头结点，改变了一级指针，这是唯一需要二级指针的地方 } else { SLTNode* ptail = (*pphead)->next; while(ptail) { ptail = ptail->next; } pcur->next = newnode; } } -
头插
往链表的头部插入数据，这里很显然是要改变头结点的指向，让新节点成为头结点，所以也需要传二级指针，头插相比于尾插是更简单的：void SLTPushFront(SLTNode** pphead,SLTDatatype x) { assert(pphead); SLTNode* newnode = BuylistNode(x); newnode->next = *pphead; *pphead = newnode;//改变了头结点指向 } -
尾删
首先找到尾，只需要将尾节点的上一个结点的next指针指向空就相当于改变了尾节点了，但是要记得用free返还空间，因为我们的结点是动态申请的。void SLTPopBack(SLTNode** pphead) { assert(pphead && (*pphead));//链表的头结点也不能为空，至少要有一个结点，删除操作才有效 if((*pphead)->next == NULL)//只有一个结点，是头也是尾 { free(*pphead); *pphead = NULL; } else { SLTNode* ptail = *pphead; SLTNode* prev = NULL; while(ptail->next) { prev = ptail; ptail = ptail->next; } prev->next = NULL; free(ptail); ptail = NULL; } } -
头删
我们直接有了头结点，所以这是在直接改变头结点，传二级指针，删除，返还空间。void SLTPopFront(SLTNode** pphead) { assert(pphead && (*pphead));//还是至少要有一个结点 if((*pphead)->next == NULL) { free(*pphead); *pphead = NULL; } else { SLTNode* pcur = *pphead; *pphead = (*pphead)->next;//改变指向 free(pcur);//返还空间 pcur = NULL; } } -
链表查找
单链表只能单向的去遍历链表，一一查找，找到了返回该数据对应位置的指针，我们就找到了这个数据存储在哪里。如果没找到就返回空指针SLTNode* SLTFind(SLTNode* phead,SLTDatatype x) { assert(ps); SLTNode* pcur = phead; while(pcur->next) { if(pucr->data == x) { return pcur; } pcur = pcur->next; } } -
在指定位置之后插入数据
因为链表是物理结构不连续的，在指定的位置插入数据也有所不同，这里要注意，因为是指定位置之后插入，所以不会改变头结点，也就没必要用到二级指针。void SLTInsertAfter(SLTNode* pos,SLTDatatype x)//pos是指定位置的地址 { assert(pos); SLTNode* newnode = BuylistNode(x); newnode->next = pos->next; pos->next = newnode;//一定要注意顺序，不然会丢失指针信息 } -
删除指定位置之后的数据
同理，无需改变头结点这个指针void SLTEraseAfter(SLTNode* pos) { assert(pos); SLTNode* pcur = pos->next; pos->next = pcur->next; free(pcur); pcur = NULL; } -
在指定位置插入数据
在指定位置插入数据，相当于在这个位置之前插入数据，假设我们在头结点位置插入数据，那么就成了头插，这是会改变头结点指针的，所以要额外把整个链表传过去，方便我们修改链表void SLTInsert(SLTNode** pphead,SLTNode* pos,SLTDatatype x) { assert(pos &&(*pphead));//至少存在数据 SLTNode* newnode = BuylistNode(x); if(pos == *pphead)//这就是头插 { SLTPushFront(pphead,x);//可以直接调用之前写过的头插函数 } else { SLTNode* newnode = BuylistNode(x); SLTNode* prev; prev = *pphead; while(prev->next != pos)//要找到这个位置的上一个结点 { prev = prev->next; } prev->next = newnode; newnode->next = pos->next; free(pos);//不要忘了释放空间 pos = NULL; } -
删除指定位置的数据
同样的找到该位置的上一个结点，直接改变结点的指向，如果位置与头结点重合，那么就可以直接调用头删函数来完成，与尾部重合也是同理。同样的，要用上二级指针void SLTErase(SLTNode** pphead,SLTNode* pos) { assert(pos && *pphead);//至少有数据 if(pos == *pphead) { SLTPopFront(pphead); } else if(pos->next == NULL) { SLTPopBack(pphead); } else { SLTNode* prev = *pphead; while(prev->next != pos) { prev = prev->next; } prev->next = pos->next; free(pos); pos = NULL; } } -
链表的销毁
链表的创建是动态内存申请的空间，空间的申请和释放随着数据的增或删而变化。最后我们仍然需要对整个链表做一个销毁。这里额外说一下：我们在创建链表时，需要直接创建链表结构体的指针作为头结点，然后再利用这个头结点来一步步地操作得到单链表。这里的销毁要将结点地址等都销毁，所以还是用二级指针。void SLTDestroy(SLTNode** pphead) { SLTNode* pcur = *pphead; while(pcur) { SLTNode* next = pcur->next;//提前存储防止找不到下一个结点 free(pcur); pcur = next; } *pphead = NULL; }
- 以上是对单链表的分解，下面我把完整的代码拿上来，分成了两份：一个是声明一个是定义。
"SList.h"
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<assert.h>
typedef int SLTdatatype;
typedef struct SlistNode
{
SLTdatatype x;
struct SlistNode* next;
}SLTNode;
SLTNode* buylistnode(SLTdatatype x);
SLTNode* SLTprint(SLTNode* phead);
void SLTpushback(SLTNode** pphead, SLTdatatype x);//尾插
void SLTpushfront(SLTNode** pphead, SLTdatatype x);//头插
void SLTpopback(SLTNode** pphead);//尾删
void SLTpopfront(SLTNode** pphead);//头删
SLTNode* Slistfind(SLTNode* phead,SLTdatatype x);//查找
void SLTInsertAfter(SLTNode* pos, SLTdatatype x);//pos之后插
void SLTEraseAfter(SLTNode* pos);//pos后删
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTdatatype x);//pos前插
void SLTErase(SLTNode** pphead, SLTNode* pos);//删pos
void SLTdestroy(SLTNode** pphead);//销毁
"Slist.c"
#include"Slist.h"
SLTNode* buylistnode(SLTdatatype x)
{
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
if (newnode == NULL)
{
perror("malloc");
exit(1);
}
newnode->x = x;
newnode->next = NULL;
return newnode;
}
SLTNode* SLTprint(SLTNode* phead)
{
SLTNode* pcur = phead;
while (pcur)
{
printf("%d -> ", pcur->x);
pcur = pcur->next;
}
printf("NULL\n");
}
void SLTpushback(SLTNode** pphead, SLTdatatype x)
{
assert(pphead);
SLTNode* newnode = buylistnode(x);
if (*pphead == NULL)
{
*pphead = newnode;
}
else
{
SLTNode* ptail = *pphead;
while (ptail -> next)
{
ptail = ptail->next;
}
ptail->next = newnode;
}
}
void SLTpushfront(SLTNode** pphead, SLTdatatype x)
{
assert(pphead);
SLTNode* newnode = buylistnode(x);
newnode->next = *pphead;
*pphead = newnode;
}
void SLTpopback(SLTNode** pphead)
{
assert(pphead && (*pphead));
if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
}
else
{
SLTNode* ptail;
SLTNode* prev;
prev = NULL;
ptail = *pphead;
while (ptail->next)
{
prev = ptail;
ptail = ptail->next;
}
prev->next = NULL;
free(ptail);
ptail = NULL;
}
}
void SLTpopfront(SLTNode** pphead)
{
assert(pphead && *pphead);
if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
}
else
{
SLTNode* pcur = *pphead;
*pphead = (*pphead)->next;
free(pcur);
pcur = NULL;
}
}
SLTNode* Slistfind(SLTNode* phead, SLTdatatype x)
{
assert(phead);
SLTNode* pcur = phead;
while (pcur)
{
if (pcur->x == x)
{
return pcur;
}
pcur = pcur->next;
}
return NULL;
}
void SLTInsertAfter(SLTNode* pos, SLTdatatype x)
{
assert(pos);
SLTNode* newnode = buylistnode(x);
newnode->next = pos->next;
pos->next = newnode;
}
void SLTEraseAfter(SLTNode* pos)
{
assert(pos&&pos->next);
SLTNode* pcur;
pcur = pos->next;
pos->next = pcur->next;
free(pcur);
pcur = NULL;
}
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTdatatype x)
{
assert(*pphead && pos);
if (pos == *pphead)
{
SLTpushfront(pphead, x);
}
else
{
SLTNode* newnode = buylistnode(x);
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
prev->next = newnode;
newnode->next = pos;
}
}
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
assert(*pphead && pos);
if (pos == *pphead)
{
SLTpopfront(pphead);
}
else if (pos->next == NULL)
{
SLTpopback(pphead);
}
else
{
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
prev->next = pos->next;
free(pos);
pos = NULL;
}
}
void SLTdestroy(SLTNode** pphead)
{
SLTNode* pcur = *pphead;
while (pcur)
{
SLTNode* next = pcur->next;
free(pcur);
pcur = next;
}
*pphead = NULL;
}
三、双链表
上文呢我们实现了一个不带头单向不循环链表，想必大家对于单链表已经有一定的了解了，对于链表这种结构也已经熟悉了。那么接下来我们就来实现一下最复杂的链表结构：带头双向循环链表。为了更清晰的看懂这种数据结构，下图是一张示意图：
这里的头是哨兵位，不存储数据，同时也是一直存在的，就相当于一直在那里“放哨”，这也是跟单链表所谓头结点的不同之处，要注意区分：单链表的头结点不算带头，它就是链表的第一个结点，被成为头结点而已；而双向链表里面这个“头”是哨兵位，是整个链表的逻辑起点，它指向链表第一个有效结点，是上图的“head”，尾结点也指向它而构成循环。
它也算是一个虚拟的结点，结构是完全一样的，但是无效。
重要的是，单链表为空，那么它的头——第一个结点就为空，也就不存在；而双链表为空时，这个哨兵位仍存在，而它指向的结点均为空。
这是双向链表的结构体定义
typedef int LTdatatype;
typedef struct LTNode
{
LTdatatype data;
struct LTNode* prev;//指向上一结点
struct LTNode* next;//指向下一结点
}LTNode;
前文有提到过，双链表的结构虽然是复杂的，但是它具有相当大的优势，这里我们直接剖析代码来展现：
-
结点的申请
链表总是离不开申请结点，只不过申请的方式不一样，这里我们再包装一个函数：LTNode* LTBuyNode(LTDatatype x) { LTNode* newnode = (LTNode*)malloc(sizeof(LTNode)); if(newnode == NULL) { perror("malloc fail!"); exit(1); } newnode->prev = newnode->next = newnode;//自己指向自己，使得本身先构成一个小的双链表 newnode->data = x; } -
初始化
我们知道，双链表有哨兵位，我们的初始化就是围绕哨兵位来进行的。有了哨兵位，就能够定位到整个链表，从而进行下一步的操作。LTNode* LTinit(LTNode* phead) { LTNode* phead = LTBuyNode(-1);//申请一个哨兵位，给无效数据 return phead; } -
判断链表是否为空
哨兵位的存在，让我们不能直接通过NULL来判断链表是不是为空，这就需要一个额外的函数判断bool LTempty(LTNode* phead) { assert(phead); return phead->next == phead;//哨兵指向自己为真即为空，反之为假不为空。 } -
尾插
经典的尾插，但是其操作实现更见简单了，因为我们可以通过哨兵位来直接找到当前的尾结点。void LTPushBack(LTNode* phead,LTDatatype x) { assert(phead); LTNode* newnode = LTBuyNode(x); phead->prev->next =newnode;//总共要修改四个指向 newnode->prev = phead->prev; newnode->next = phead; phead->prev = newnode; } -
头插
头插就变成了在哨兵位的下一个位置插入了。void LTPushFront(LTNode* phead,LTDatatype x) { assert(phead); LTNode* newnode = LTBuyNode(x); newnode->next = phead->next; newnode->prev = phead; phead->next->prev = newnode; phead->next = newnode; } -
尾删
尾删也是依靠哨兵位直接去找到尾结点，但需要判空，确保链表不为空void LTPopBack(LTNode* phead) { assert(!LTempty(phead));//直接断言非空 LTNode* pcur = phead->prev; phead->prev = pcur->prev; pcur->prev->next = pcur->next; free(pcur); pcur = NULL; } -
头删
头删也依靠哨兵位，并且不会改变“头结点”，所以都不需要二级指针void LTPopFront(LTNode* phead) { assert(!LTempty(phead));//先判空 LTNode* pcur = phead->next; phead->next = pcur->next; pcur->next->prev = phead; free(pcur); pcur = NULL; } -
查找
存储了数据就离不开查找。查找还是依靠遍历。LTNode* LTfind(LTNode* phead, LTdatatype x) { assert(phead); LTNode* pcur = phead->next; while (pcur != phead) { if (pcur->x == x) { return pcur; } pcur = pcur->next; } return NULL; } -
任意位置之前插入
依旧是利用双向的特性直接找到对应的结点操作。这里甚至不需要哨兵位参与，利用给的位置就能直接找到前后节点void LTInsertFront(LTNode* pos,LTdatatype x) { assert(pos); LTNode* newnode = LTBuyNode(x); newnode->next = pos; newnode->prev = pos->prev; pos->prev->next = newnode; pos->prev = newnode; } -
任意位置之后插入
同理，只需要这个位置的指针void LTInsert(LTNode* pos,LTdatatype x) { assert(pos); LTNode* newnode = LTBuyNode(x); newnode->next = pos->next; newnode->prev = pos; pos->next->prev = newnode;//顺序不要错哦！ pos->next = newnode; } -
删除任意位置结点
还是只需要这个结点的指针就行了void LTErase(LTNode* pos) { assert(pos); pos->prev->next = pos->next; pos->next->prev = pos->prev; free(pos); pos = NULL; } -
链表的销毁
整个链表的操作完成之后，对于动态申请的链表还是需要销毁。我们依旧利用遍历来操作void LTDestroy(LTNode* phead) { LTNode* pcur = phead->next; while(pcur != phead) { LTNode* next = pcur->next; free(pcur); pcur = next; } free(phead); phead = NULL; }
- 以上就是双链表的基本的操作了，其实我们可以发现，在双链表的这些操作中，我们利用双链表能够找到上下结点的特性，减少了代码量，操作也更简单了一些，在我们理解了逻辑之后，双链表反而在对应的操作上更简单了。而且效率也有所提升。
那么接下来，还是把完整的代码拿上来：
"List.h"
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
typedef int LTdatatype;
typedef struct LTNode
{
LTdatatype x;
struct LTNode* prev;
struct LTNode* next;
}LTNode;
LTNode* LTinit();
void LTpushback(LTNode* phead, LTdatatype x);
void LTpushfront(LTNode* phead, LTdatatype x);
void LTpopback(LTNode* phead);//尾删
void LTpopfront(LTNode* phead);//头删
LTNode* LTfind(LTNode* phead, LTdatatype x);
void LTinsert(LTNode* pos, LTdatatype x);//在pos位置之后插入
void LTinsertfront(LTNode* pos, LTdatatype x);//在pos位置之前插入
void LTerase(LTNode* pos);//删除pos结点
void LTdestroy(LTNode* phead);
"List.c"
#include"List.h"
LTNode* LTbuynode(LTdatatype x)
{
LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
if (newnode == NULL)
{
perror("malloc");
exit(1);
}
newnode->x = x;
newnode->next = newnode->prev = newnode;
return newnode;
}
LTNode* LTinit()
{
LTNode* phead = LTbuynode(-1);
return phead;
}
bool LTEmpty(LTNode* phead)
{
assert(phead);
return phead->next == phead;
}
void LTprint(LTNode* phead)
{
LTNode* pcur = phead->next;
while (pcur != phead)
{
printf("%d-> ", pcur->x);
pcur = pcur->next;
}
printf("\n");
}
void LTpushback(LTNode* phead, LTdatatype x)
{
assert(phead);
LTNode* newnode = LTbuynode(x);
newnode->next = phead;
newnode->prev = phead->prev;
phead->prev->next = newnode;
phead->prev = newnode;
}
void LTpushfront(LTNode* phead, LTdatatype x)
{
assert(phead);
LTNode* newnode = LTbuynode(x);
newnode->next = phead->next;
newnode->prev = phead;
phead->next->prev = newnode;
phead->next = newnode;
}
void LTpopback(LTNode* phead)
{
assert(!LTEmpty(phead));
LTNode* del = phead->prev;
del->prev->next = del->next;
phead->prev = del->prev;
free(del);
del = NULL;
}
void LTpopfront(LTNode* phead)
{
assert(!LTEmpty(phead));
LTNode* del = phead->next;
phead->next = del->next;
del->next->prev = phead;
free(del);
del = NULL;
}
LTNode* LTfind(LTNode* phead, LTdatatype x)
{
assert(phead);
LTNode* pcur = phead->next;
while (pcur != phead)
{
if (pcur->x == x)
{
return pcur;
}
pcur = pcur->next;
}
return NULL;
}
void LTinsert(LTNode* pos, LTdatatype x)
{
assert(pos);
LTNode* newnode = LTbuynode(x);
newnode->next = pos->next;
newnode->prev = pos;
pos->next->prev = newnode;
pos->next = newnode;
}
void LTerase(LTNode* pos)
{
assert(pos);
LTNode* del = pos;
pos->prev->next = pos->next;
del->next->prev = del->prev;
free(del);
del = NULL;
}
void LTinsertfront(LTNode* pos, LTdatatype x)
{
assert(pos);
LTNode* newnode = LTbuynode(x);
newnode->next = pos;
newnode->prev = pos->prev;
pos->prev->next = newnode;
pos->prev = newnode;
}
void LTdestroy(LTNode* phead)
{
LTNode* pcur = phead->next;
while (pcur != phead)
{
LTNode* next = pcur->next;
free(pcur);
pcur = next;
}
free(phead);
phead = NULL;
}
总结
本文详细的介绍了链表的概念与结构，并且手撕了两种常见的主要的链表基本逻辑和代码实现，希望能让大家更好的学习链表这种数据结构。
魔乐社区（Modelers.cn) 是一个中立、公益的人工智能社区，提供人工智能工具、模型、数据的托管、展示与应用协同服务，为人工智能开发及爱好者搭建开放的学习交流平台。社区通过理事会方式运作，由全产业链共同建设、共同运营、共同享有，推动国产AI生态繁荣发展。
更多推荐
21
0- 0
已为社区贡献1条内容
所有评论(0)