一.双向链表的结构
注意：这里的“带头”跟前面我们说的“头节点”是两个概念，实际前面的在单链表阶段称呼不严
谨，但是为了同学们更好的理解就直接称为单链表的头节点。
带头链表里的头节点，实际为“哨兵位”，哨兵位节点不存储任何有效元素，只是站在这里“放哨
的”
“哨兵位”存在的意义：
遍历循环链表避免死循环。
二. 双向链表的实现
2.1 头文件 ——双向链表的创建及功能函数的定义
List.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int LTDatatype;
//链表的结构创建
typedef struct ListNode
{
LTDatatype data;
struct ListNode* next;
struct ListNode* prev;
}LTNode;
//打印
void LTPrint(LTNode* phead);
//双链表的初始化//销毁
//void LTInit(LTNode** pphead);
LTNode* LTInit();
//销毁
//void LTDestroy(LTNode** pphead);
void LTDestroy(LTNode* phead);
//头部/尾部/插入/删除
//尾插
void LTPushBack(LTNode* phead, LTDatatype x);
//头插
void LTPushFront(LTNode* phead, LTDatatype x);
//尾删
void LTPopBack(LTNode* phead);
//头删
void LTPopFront(LTNode* phead);
//再pos位置之后插入/删除
void LTInsrt(LTNode* pos, LTDatatype x);
void LTErase(LTNode* pos);
//查找pos
LTNode* LTFind(LTNode* phead, LTDatatype x);
2.2 源文件 ——双向链表的功能函数的实现
List.c
#include"List.h"
//初始化
//二级指针初始化
//前提是我们需要传入一个头节点
//void LTInit(LTNode** pphead)
//{
// *pphead = (LTNode*)malloc(sizeof(LTNode));
// if (*pphead == NULL)
// {
// perror("malloc error");
// return;
// }
// (*pphead)->data = -1;//哨兵位
// (*pphead)->next = (*pphead)->prev = *pphead;
//
//}
//一级指针初始化
//不需要传参，只需要返回一个地址即可
LTNode* LTInit()
{
LTNode* phead = (LTNode*)malloc(sizeof(LTNode));
if (phead == NULL)
{
perror("malloc error");
return;
}
phead->data = -1;
phead->next = phead->prev = phead;
return phead;
}
//链表的销毁
//参数是二级指针
//void LTDestroy(LTNode** pphead)
//{
// assert(pphead && *pphead);
// LTNode* cur = (*pphead)->next;
// while(cur!=(*pphead))
// {
// LTNode* next = cur->next;
// free(cur);
// cur = next;
// }
// free(*pphead);
// *pphead = NULL;
//}
//参数是一级指针
void LTDestroy(LTNode* phead)
{
assert(phead);
LTNode* cur = phead->next;
while (cur != phead)
{
LTNode* next = cur->next;
free(cur);
cur = next;
}
free(phead);
phead = NULL;
}
void LTPrint(LTNode* phead)
{
assert(phead);
LTNode* cur = phead->next;
while (cur != phead)
{
printf("%d->", cur->data);
cur = cur->next;
}
printf("\n");
}
LTNode* LTBuyNode(LTDatatype x)
{
LTNode* node = (LTNode*)malloc(sizeof(LTNode));
node->data = x;
node->next = node->prev = NULL;
return node;
}
//尾插
void LTPushBack(LTNode* phead, LTDatatype x)
{
LTNode* node = LTBuyNode(x);
//先处理插入的节点的前驱和后继指针
node->next = phead;
node->prev = phead->prev;
//然后考虑哨兵位的前驱和尾节点的后继指针
phead->prev->next = node;
phead->prev = node;
}
//头插
void LTPushFront(LTNode* phead, LTDatatype x)
{
assert(phead);
LTNode* node = LTBuyNode(x);
//先处理插入节点的前驱和后继的指针
node->next = phead->next;
node->prev = phead;
//然后处理phead,phead->next
phead->next->prev = node;
phead->next = node;
}
//尾删
void LTPopBack(LTNode* phead)
{
assert(phead);
//链表不能为空，链表中只有一个哨兵位节点
assert(phead->next != phead);
LTNode* del = phead->prev;
//先处理 del->prev
del->prev->next = phead;
//接着处理phead
phead->prev = del->prev;
free(del);
del = NULL;
}
//头删
void LTPopFront(LTNode* phead)
{
assert(phead && phead->next != phead);
LTNode* del = phead->next;
//先处理del->next
del->next->prev = phead;
//接着处理phead
phead->next = del->next;
free(del);
del = NULL;
}
//在pos位置之后插入
void LTInsrt(LTNode* pos, LTDatatype x)
{
LTNode* node = LTBuyNode(x);
//先处理node的前驱和后继
node->next = pos->next;
node->prev = pos;
//接着处理pos->next,pos->next->prev
pos->next = node;
pos->next->prev = node;
}
//删除pos位置的数据
void LTErase(LTNode* pos)
{
assert(pos);
pos->next->prev = pos->prev;
pos->prev->next = pos->next;
free(pos);
pos = NULL;
}
//查找pos
LTNode* LTFind(LTNode* phead, LTDatatype x)
{
assert(phead);
LTNode* cur = phead->next;
while (cur != phead)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
2.3 源文件 ——双向链表功能的测试
test.c
#include"List.h"
void ListTest()
{
/*LTNode* plist = NULL;
LTInit(&plist);*/
//初始化
LTNode* plist = LTInit();
//尾插
LTPushBack(plist, 1);
LTPushBack(plist, 2);
LTPushBack(plist, 3);
LTPushBack(plist, 4);
//头插
/*LTPushFront(plist, 1);
LTPushFront(plist, 2);
LTPushFront(plist, 3);
LTPushFront(plist, 4);*/
//尾删
/*LTPopBack(plist);
LTPopBack(plist);*/
//头删
/*LTPopFront(plist);
LTPopFront(plist);*/
LTNode* find = LTFind(plist, 4);
//在pos位置之后插入
/*LTInsrt(find, 5);*/
//删除pos位置的数据
LTErase(find);
LTPrint(plist);
//销毁链表
//LTDestroy(&plist);
//一级指针销毁需要手动将plist置空
LTDestroy(plist);
plist = NULL;
}
int main()
{
ListTest();
return 0;
}
2.4 双向链表各项功能测试运行展示
2.4.1 双向链表的初始化 ——（以调试窗口展示）
//初始化
LTNode* plist = LTInit();
2.4.2 双向链表的尾插 ——（以打印展示）
//尾插
LTPushBack(plist, 1);
LTPushBack(plist, 2);
LTPushBack(plist, 3);
LTPushBack(plist, 4);
2.4.3 双向链表的头插 ——（以打印展示）
//头插
LTPushFront(plist, 1);
LTPushFront(plist, 2);
LTPushFront(plist, 3);
LTPushFront(plist, 4);
2.4.4 双向链表的尾删 ——（以打印展示）
//尾删
LTPopBack(plist);
LTPopBack(plist);
2.4.5 双向链表的头删 ——（以打印展示）
//头删
LTPopFront(plist);
LTPopFront(plist);
2.4.6 双向链表的查找指定位置及在指定位置之后插入 ——（以打印展示）
//查找指定位置pos
LTNode* find = LTFind(plist, 4);
//在pos位置之后插入
LTInsrt(find, 5);
2.4.7 双向链表的查找指定位置及删除指定位置的数据 ——（以打印展示）
// //查找指定位置pos
LTNode* find = LTFind(plist, 4);
//删除pos位置的数据
LTErase(find);
2.4.8 双向链表的销毁 ——（以调试窗口展示）
//销毁链表
//LTDestroy(&plist);
//一级指针销毁需要手动将plist置空
LTDestroy(plist);
plist = NULL;
文章来源：https://www.toymoban.com/news/detail-737114.html
三.顺序表和双向链表的优缺点分析
文章来源地址https://www.toymoban.com/news/detail-737114.html
到了这里，关于【（数据结构）— 双向链表的实现】的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
