C语言详解如何实现带头双向循环链表

Radinka ·

更新时间:2024-11-14

· 1606 次阅读

创建链表存储结构

创建结点

链表的初始化

双向链表的打印

双向链表尾插

双向链表尾删

双向链表头插

双向链表头删

双向链表查找

双向链表pos前插入结点

双向链表删除pos位置的结点

双向链表的销毁

顺序表和链表的区别

创建链表存储结构

我们需要创建一个结构体来存储一个链表结点的相关信息。

typedef int ListDataType;//将ListDataType先定义为int类型，根据需要可以改为不同的类型
//创建一个链表的结构体
typedef struct ListNode
{
ListDataType data;//存储数据
struct ListNode* next;//存储下一个结点的地址的指针
struct ListNode* prev;//存储上一个结点的地址的指针
}ListNode;

创建结点

我们每次增加数据都要创建一个新的结点，但每次都创建就会非常的麻烦。所以我们考虑把创建一个结点这个功能封装成一个函数，每次要使用只要调用一下就可以了。

ListNode* BuyListNode(ListDataType x)
{
ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));//向内存申请一个新的结点
if (newnode == NULL)
{
printf("BuyListNode::%s\n", strerror(errno));//打印结点空间申请失败的原因
exit(-1);//终止程序
}
newnode->data = x;//将x放入申请的结点数据区
newnode->next = NULL;//让新结点的next指向空
newnode->prev = NULL;//让新结点的prev指向空
return newnode;//返回新结点的地址
}

链表的初始化

带头双向循环链表我们对其初始化就是申请一个带哨兵位的头结点。接下来我们看初始化的两种方法。

void ListInit(ListNode** pphead)//这里我们需要对头结点进行改变，所以传二级指针
{
assert(pphead);//检测传过来的pphead的地址是否为空
*pphead = BuyListNode(0);//创建一个新的哨兵位头结点
(*pphead)->next = *pphead;//让这个结点指向自己
(*pphead)->prev = *pphead;
}

ListNode* ListInit()
{
ListNode* phead = BuyListNode(0);//创建一个新的哨兵位头结点
phead->next = phead;//让这个结点的next指向自己
phead->prev = phead;//让prev指向自己
return phead;//返回哨兵位头结点的地址
}

双向链表的打印

我们才用遍历链表的方式来打印链表中的数据。

void ListPrint(ListNode* phead)
{
assert(phead);
ListNode* cur = phead->next;//让cur指向哨兵位的下一个结点
while (cur != phead)//链表打印是否结束的条件判断
{
printf("%d ", cur->data);
cur = cur->next;
}
printf("\n");
}

双向链表尾插

双向循环链表结构比较优，所以很方便找到尾结点。尾结点就是哨兵位结点prev指向的结点。

void ListPushBack(ListNode* phead, ListDataType x)
{
assert(phead);//检查传过来的头结点是否为空
ListNode* tail = phead->prev;//找到链表的尾结点
ListNode* newnode = BuyListNode(x);//创建一个新的结点
tail->next = newnode;//让尾结点的next指向新的结点
newnode->prev = tail;//让新结点的prev指向之前的尾结点
newnode->next = phead;//让新的结点的next指向头结点
phead->prev = newnode;//让头结点指向新的尾结点
}

双向链表尾删

void ListPopBack(ListNode* phead)
{
assert(phead);
if (phead->next == phead)//如果链表只有哨兵位结点的情况，就不能继续删除了
return;
ListNode* tail = phead->prev;//找到尾结点
ListNode* tailPrev = tail->prev;//定义尾结点的前一个结点
free(tail);//释放要删除的结点
tailPrev->next = phead;//让前一个结点指向哨兵位结点
phead->prev = tailPrev;//让哨兵位结点指向新的尾结点
}

双向链表头插

双向链表的头插就是在哨兵位结点的下一个位置插入一个新的数据。

注意：这一种方法种的指向关系不能随意颠倒，否则就会出错。

void ListPushFront(ListNode* phead, ListDataType x)
{
assert(phead);
ListNode* newnode = BuyListNode(x);//创建一个新结点
newnode->next = phead->next;//新结点的next指向头结点的下一个结点
phead->next->prev = newnode;//头结点的下一个结点指向新结点
phead->next = newnode;//头结点指向新结点
newnode->prev = phead;//新结点prev指向头结点
}

我们可以对上一种情况进行优化，定义一个next记录头结点的下一个结点的地址。这样我们就可以不用在意指向顺序的问题，可以减少出错的概率。

void ListPushFront(ListNode* phead, ListDataType x)
{
assert(phead);
ListNode* newnode = BuyListNode(x);//创建一个新结点
ListNode* next = phead->next;//定义next记录头节点的下一个结点的位置
phead->next = newnode;//头结点next指向新结点
newnode->prev = phead;//新结点的prev指向头结点
next->prev = newnode;//头结点的下一个结点的prev指向新阶段
newnode->next = next;//新结点的next指向原头结点的下一个结点
}

双向链表头删

我们先找到头结点的下一个结点，然后在把它释放掉。这里需要注意的是如果链表为空，只有哨兵位头结点的情况，我们需要对其进行特殊的处理。

void ListPopFront(ListNode* phead)
{
assert(phead);
if (phead->next == NULL)//只有哨兵位头结点的情况
return;
ListNode* next = phead->next->next;//定义next指向要删除结点的下一个结点
free(phead->next);//释放要删除的结点
phead->next = next;//让哨兵位头结点指向要删除的下一个结点
next->prev = phead;//让要删除的下一个结点的prev指向toujied
}

双向链表查找

若我们想要对指定的位置的结点进行相应的改变就得先找到对应的结点，所以我们将查找指定数据封装成一个函数。方便后续调用。

ListNode* ListFind(ListNode* phead, ListDataType x)
{
assert(phead);
ListNode* cur = phead->next;//让cur指向哨兵位头结点的下一个结点
while (cur != phead)//链表循环是否结束的判断条件
{
if (cur->data == x)
return cur;
cur = cur->next;
}
return NULL;//找不到对于的结点
}

双向链表pos前插入结点

推荐使用第二种方法，不容易出错。

void ListInsert(ListNode* pos, ListDataType x)
{
assert(pos);
ListNode* newnode = BuyListNode(x);//创建一个新的结点
pos->prev->next = newnode;//pos的前一个结点的next指向新结点
newnode->prev = pos->prev;//新结点的prev指向pos的前一个结点
newnode->next = pos;//新结点的next指向pos结点
pos->prev = newnode;//pos的prev指向新结点
}

void ListInsert(ListNode* pos, ListDataType x)
{
assert(pos);
ListNode* newnode = BuyListNode(x);//创建一个新的结点
ListNode* posPrev = pos->prev;//定义pos的前一个结点
posPrev->next = newnode;//让pos的pos前一个结点的next指向新结点
newnode->prev = posPrev;//新结点的prev指向pos的前一个结点
newnode->next = pos;//新结点的next指向pos
pos->prev = newnode;//pos的prev指向新结点
}

双向链表删除pos位置的结点

void ListErase(ListNode* pos)
{
assert(pos);
ListNode* prev = pos->prev;//prev为pos的前一个结点
ListNode* next = pos->next;//next为pos的后一个结点
free(pos);//释放posjied
prev->next = next;
next->prev = prev;
}

双向链表的销毁

void ListDestroy(ListNode* phead)
{
assert(phead);
ListNode* cur = phead->next;//指向哨兵位结点的下一个结点
while (cur != phead)//依次循环找链表的每一个结点
{
ListNode* next = cur->next;//记录cur的下一个结点位置
free(cur);//释放cur位置的结点
cur = next;//指向下一个结点
}
free(phead);//释放哨兵位头结点
}

注意：在写双向链表的头插，头删，尾插，尾删时我们可以复用双向链表的任意位置插入和任意位置删除那两个函数。那两个函数就可以完成头插，头删，尾插，尾删这几个功能。

顺序表和链表的区别

顺序表优点：

1.物理空间是连续的，方便用下标随机访问。

2.CPU高速缓存命中率会更高。

顺序表缺点：

1.由于需要物理空间连续，空间不够需要扩容。扩容本身有一定消耗。其次扩容机制还存在一定的空间浪费。

2.头部或者中部插入删除，挪动数据，效率低。O（N)

链表优点：

1.任意位置插入删除数据效率高。O(1)

2.按需申请和释放空间

链表缺点：