【双向链表的实现】

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

前言

1. 双向链表的结构

2. 双向链表的实现

2.1 头文件 ——双向链表的创建及功能函数的定义

2.2 源文件 ——双向链表的功能函数的实现

2.3 源文件 ——双向链表功能的测试

4.双向链表的操作示意图

3.顺序表和双向链表的优缺点分析

总结

前言

世上有两种耀眼的光芒，一种是正在升起的太阳，一种是正在努力学习编程的你!一个爱学编程的人。各位看官，我衷心的希望这篇博客能对你们有所帮助，同时也希望各位看官能对我的文章给与点评，希望我们能够携手共同促进进步，在编程的道路上越走越远!

提示：以下是本篇文章正文内容，下面案例可供参考

1. 双向链表的结构

注意：这里的“带头”跟前面我们说的“头节点”是两个概念，实际前面的在单链表阶段称呼不严谨，但是为了同学们更好的理解就直接称为单链表的头节点。

带头链表里的头节点，实际为“哨兵位”，哨兵位节点不存储任何有效元素，只是站在这里“放哨的”

“哨兵位”存在的意义：遍历循环链表避免死循环。

2. 双向链表的实现

2.1 头文件 ——双向链表的创建及功能函数的定义

List.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>//定义双向链表的节点的结构
typedef int STDataType;typedef struct ListNode
{STDataType data;struct ListNode* next;//保存下一个节点的地址struct ListNode* prev;//保存前一个节点的地址
}LTNode;//链表的初始化
//void LTInit(LTNode** pphead);//前提：我们要传入一个头节点//我们更倾向于第二种初始化的方法
//因为双向链表为空（只有一个哨兵位：哨兵位节点是不能被操作的，即不能被改变）
LTNode* LTInit();//不需要传入参数，调用该方法之后给我们返回一个头节点//在双向链表中不会改变哨兵位，所以可以传一级指针
//尾插入操作
void LTPushBack(LTNode* phead, STDataType x);//头插
void LTPushFront(LTNode* phead, STDataType x);//链表的打印
void LTPrint(LTNode* phead);//尾删
void LTPopBack(LTNode* phead);
//头删
void LTPopFront(LTNode* phead);//在pos位置之后插入的数据
void LTInsert(LTNode* pos, STDataType x);
//删除pos位置的节点
void LTErase(LTNode* pos);
LTNode* LTFind(LTNode* phead, STDataType x);//链表的销毁
void LTDestroy(LTNode* phead);

2.2 源文件 ——双向链表的功能函数的实现

List.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "List.h"//链表的初始化
//前提：我们要传入一个头节点
//void LTInit(LTNode** pphead)
//{
//	*pphead = (LTNode*)malloc(sizeof(LTNode));
//	if (*pphead == NULL)
//	{
//		perror("malloc");
//		return;
//	}
//	//节点有三部分内容：数据 前驱指针 后继指针
//	(*pphead)->data = -1;//哨兵位
//	(*pphead)->next = (*pphead)->prev = *pphead;
//}//链表初始化
//不需要传入参数，调用该方法之后给我们返回一个头节点
LTNode* LTInit()
{LTNode* phead = (LTNode*)malloc(sizeof(LTNode));if (phead == NULL){perror("malloc");return;}phead->data = -1;phead->next = phead->prev = phead;return phead;
}//申请一个新的节点
LTNode* ListBuyNode(STDataType x)
{LTNode* node = (LTNode*)malloc(sizeof(LTNode));node->data = x;node->next = node->prev = NULL;return node;
}//链表的打印
void LTPrint(LTNode* phead)
{LTNode* cur = phead->next;while (cur != phead){printf("%d->", cur->data);cur = cur->next;}printf("\n");
}//尾插入操作
void LTPushBack(LTNode* phead, STDataType x)
{assert(phead);LTNode* node = ListBuyNode(x);//先处理新节点node的前驱和后继指针node->prev = phead->prev;node->next = phead;//在处理phead->prev（之前的尾节点）和pheadphead->prev->next = node;phead->prev = node;
}//头插
void LTPushFront(LTNode* phead, STDataType x)
{assert(phead);LTNode* node = ListBuyNode(x);//node的节点 next prevnode->prev = phead;node->next = phead->next;//处理phead phead->nextphead->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;//处理pheadphead->prev = del->prev;free(del);del = NULL;
}
//头删
void LTPopFront(LTNode* phead)
{assert(phead&& phead->next != phead);LTNode* del = phead->next;//phead del->nextdel->next->prev = phead;phead->next = del->next;free(del);del = NULL;
}//在pos位置之后插入的数据
void LTInsert(LTNode* pos, STDataType x)
{assert(pos);LTNode* node = ListBuyNode(x);//node的prev 和 nextnode->next = pos->next;node->prev = pos;//pos的next 和 pos->next的prevpos->next = node;node->next->prev = node;
}
//删除pos位置的节点
void LTErase(LTNode* pos)
{assert(pos);//pos->prev:next pos pos->next:prevpos->next->prev = pos->prev;pos->prev->next = pos->next;free(pos);pos = NULL;
}
//查找数据
LTNode* LTFind(LTNode* phead, STDataType x)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){if (cur->data == x){return cur;}cur = cur->next;}return 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;//我们将phead指向的空间释放掉，plist实参的空间也被释放掉了，phead置为空//但是此时plist实参为野指针，还需要我们手动置为空
}

2.3 源文件 ——双向链表功能的测试

test.c

#define _CRT_SECURE_NO_WARNINGS 1#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);//打印LTPrint(plist);头插//LTPushFront(plist, 5);//LTPushFront(plist, 6);//LTPushFront(plist, 7);//LTPrint(plist);//尾删//LTPopBack(plist);//头删/*LTPopFront(plist);LTPopFront(plist);*///测试指定位置之后插入//LTNode* find = LTFind(plist, 1);//LTInsert(find, 11);/*LTErase(find);LTPrint(plist);*///销毁链表LTDestroy(plist);//传一级指针的要手动将plist置为空plist = NULL;
}
int main()
{ListTest();return 0;
}