【数据结构】带头双向链表的实现

👑个人主页：啊Q闻

🎇收录专栏：《数据结构》

🎉道阻且长，行则将至

前言

带头双向链表是链表的一种，相较于单链表的实现，其更为简单

一.初识带头双向循环链表

带头双向循环链表结构：

带头双向循环链表的理解:

1.“带头”是指该链表的头节点，这里的头节点，实际上是哨兵位，哨兵位节点不存储任何有效元素。哨兵位存在的意义：遍历循环链表避免死循环。

2.“双向”是指链表中每个节点都有前驱节点和后继节点。

3.“循环”是指链表的首尾是相接的，可以实现一个循环的结构。

二.带头双向循环链表的实现

节点结构的定义：

带头双向循环链表的实现我们创建三个文件：

一个头文件list.h用于定义链表的结构，链表要实现的接口。

一个源文件list.c用于具体实现链表里定义的接口。

一个源文件test.c用于测试链表。

list.h

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
typedef int LTDataType;
typedef struct ListNode
{struct ListNode* next;struct ListNode* prev;LTDataType data;
}LTNode;
void LTInit(LTNode**pphead);//初始化
void LTDestroy(LTNode** pphead);//销毁
void LTPrint(LTNode* phead);//打印
void LTPushBack(LTNode* phead,LTDataType x);//后插
void LTPopBack(LTNode* phead);//后删
void LTPushFront(LTNode* phead,LTDataType x);//前插
void LTPopFront(LTNode* phead);//前删
void LTInsert(LTNode* pos,LTDataType x);//在指定位置插入
void LTErase(LTNode* pos);//在指定位置删除
LTNode* LTFind(LTNode* phead, LTDataType x);//查找

list.c

#include"list.h"
void LTInit(LTNode** pphead)//初始化
{*pphead = (LTNode*)malloc(sizeof(LTNode));if (*pphead == NULL){perror("malloc fail");exit(1);}(*pphead)->data = -1;(*pphead)->next = (*pphead)->prev = *pphead;
}
LTNode* LTBuyNode(LTDataType x)
{LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));if (newnode == NULL){perror("malloc fail");exit(1);}newnode->data = x;newnode->next = newnode->prev = newnode;
}
void LTPrint(LTNode* phead)//打印
{assert(phead);LTNode* pcur = phead->next;while (pcur != phead){printf("%d->", pcur->data);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 LTPopBack(LTNode* phead)//后删
{assert(phead);assert(phead->next!=phead);LTNode* del = phead->prev;LTNode* prev = del->prev;prev->next = phead;phead->prev = prev;free(del);del = NULL;
}
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 LTPopFront(LTNode* phead)//前删
{assert(phead);assert(phead->next!=phead);LTNode* del = phead->next;LTNode* next = del->next;next->prev = phead;phead->next = next;free(del);del = NULL;}
LTNode* LTFind(LTNode* phead, LTDataType x)//查找
{assert(phead);LTNode* pcur = phead->next;while (pcur != phead){if (pcur->data == 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);pos->next->prev = pos->prev;pos->prev->next = pos->next;free(pos);pos = NULL;
}
void LTDestroy(LTNode** pphead)//销毁
{assert(pphead);assert(*pphead);LTNode* pcur = (*pphead)->next;while (pcur != *pphead){LTNode* next = pcur->next;free(pcur);pcur = next;}free(*pphead);*pphead = NULL;
}

详解：

初始化：

创建新节点：

打印：

后插:

后插运行结果：

后删：

后删结果：

前插（所谓前插，是指在哨兵位后边插入）：

前插结果：

前删：

前删结果：

查找（查找的函数在后续指定位置删除增加会调用）：

在指定位置后插入：

在指定位置后插入结果：

删除指定节点：

删除指定节点运行结果：

销毁链表：

test.c

#include"list.h"
void LTTest01()
{LTNode* plist = NULL;LTInit(&plist);LTPushBack(plist,1);LTPushBack(plist, 2);LTPushBack(plist, 3);//LTPopBack(plist);/*LTPushFront(plist, 4);LTPushFront(plist, 5);LTPopFront(plist);*/LTNode* pcur = LTFind(plist, 2);//LTInsert(pcur,88);LTErase(pcur);//LTDestroy(&plist);LTPrint(plist);//LTDestroy(&plist);}
int main()
{LTTest01();return 0;
}