C语言数据结构（5）双向链表

发布于：2025-08-03 ⋅ 阅读:(11) ⋅ 点赞:(0)

1. 双向链表的结构

哨兵位不存储有效数据。

当链表中只有哨兵位节点的时候，我们称该链表为空链表，即哨兵位是不能删除的。

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

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

“哨兵位”存在的意义：

遍历循环链表避免死循环。

2. 双向链表的实现

哨兵位：非有效结点。

首结点：第一个有效结点。

尾结点：最后一个有效结点。

2.1 头文件

typedef int LTDataType;
//链表中结点的结构
typedef struct ListNode
{
    struct ListNode* next; //指针保存下⼀个节点的地址——后继结点指针
    struct ListNode* prev; //指针保存前⼀个节点的地址——前驱结点指针
    LTDataType data;
}LTNode;

//注意：双向链表是带有哨兵位的，插入数据之前链表中必须要先初始化一个哨兵位(单向链表可以直接插入数据)
//注意：当链表中删到只有哨兵位时，称为空链表（不可再删）
//注意：哨兵位是不能删除也不能修改的，即不能对哨兵位进行任何操作，但是可以改变哨兵位的指向（头插：指插入到哨兵位之后，头节点之前，成为新的头节点）

//传入参数-改变参数式的初始化方式
//void LTInit(LTNode** pphead);
//接受返回值式的初始化
LTNode* LTInit();


void LTDesTroy(LTNode** pphead);
void LTdesTroy(LTNode* phead);   //推荐一级（优：保持接口一致性；缺：调用完后phead需手动置空）

void LTPrint(LTNode* phead);

//不需要改变哨兵位（的位置），则不需要传二级指针
//需要改变哨兵位（的内容val、next），则不需要传二级指针
//如果需要修改哨兵位（的位置）的话（phead->next），则传二级指针××××××××
//注意：改变phead->next只需要*phead，改变哨兵位需要*pphead
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);
//指定删除
void LTErase(LTNode* pos);

2.2 实现代码、测试代码

（1）初始化

函数声明
//List.h
//传入参数-改变参数式的初始化方式
//void LTInit(LTNode** pphead);
//接受返回值式的初始化
LTNode* LTInit();
函数实现
//List.c
//双链表
#include "Double_Linked_List.h"
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;

	return newnode;
}
//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* LTInit() {
	LTNode* phead = LTBuyNode(-1);
	return phead;
}
函数测试

（2）打印

函数声明
void LTPrint(LTNode* phead);
函数实现
void LTPrint(LTNode* phead) {
	//phead不能为空
	assert(phead);
    //先走到首结点
	LTNode* pcur = phead->next;    //phead->next 不会为空，至少也是自己（哨兵位）
    //循环条件：没到下一个哨兵位
	while (pcur != phead)
	{
		printf("%d->", pcur->data);
		pcur = pcur->next;
	}
	printf("\n");
}

（3）头插、尾插

函数声明
//头插、尾插
void LTPushBack(LTNode* phead, LTDataType x);
void LTPushFront(LTNode* phead, LTDataType x);

双链表同样是通过一个结点指针来维护，这个结点指针永远指向头结点——哨兵位，永远不会改变其指向，则不需要传二级指针。

逻辑演示

头插是在第一个有效结点之前插入，而不是在哨兵位之前插入——这是尾插。

函数实现
//List.c
//双链表

//尾插——在最后一个有效节点之后、哨兵位之前插入节点
void LTPushBack(LTNode* phead, LTDataType x) {
	assert(phead);
	LTNode* newnode = LTBuyNode(x);
	//phead phead->prev(ptail)  newnode
	//生成两条链——修改新结点的指向
	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);
	//phead newnode phead->next
	//生成两条链——修改新结点的指向
	newnode->next = phead->next;
	newnode->prev = phead;
	//重连两条链——修改首结点、哨兵位的指向
	phead->next->prev = newnode;
	phead->next = newnode;
}
函数测试

（4）头删、尾删

函数声明
//头删、尾删
void LTPopBack(LTNode* phead);
void LTPopFront(LTNode* phead);

双链表同样是通过一个结点指针来维护，这个结点指针永远指向头结点——哨兵位，永远不会改变其指向，则不需要传二级指针。

逻辑演示

函数实现
//List.c
//双链表

//尾删
void LTPopBack(LTNode* phead) {
	assert(phead);
	//链表为空：只有一个哨兵位节点
	assert(phead->next != phead);//或者phead->prev != phead
	
    //找到待删节点
	LTNode* tail = phead->prev;
	//找到待删节点的前驱节点
	LTNode* tailprev = tail->prev;

	//互指
	tailprev->next = phead;
	phead->prev = tailprev;

	free(tail);
	tail = NULL;
}

//头删
void LTPopFront(LTNode* phead) {
	assert(phead);
	assert(phead->next != phead);
	//找到待删节点
	LTNode* del = phead->next;
	//找到待删节点的后继节点
	LTNode* next = del->next;

	//phead del next
	next->prev = phead;
	phead->next = next;

	free(del);
	del = NULL;
}
函数测试

（5）查找pos位置

函数声明
//查找
LTNode* LTFind(LTNode* phead, LTDataType x);
函数实现

思路：遍历查找。

//List.c
//双链表

//查找pos位置
LTNode* LTFind(LTNode* phead, LTDataType x) {
	assert(phead);
    //遍历之前，先走到首结点
	LTNode* pcur = phead->next;
    //遍历结束条件：来的第2个哨兵位
	while (pcur != phead)
	{
		if (pcur->data == x) {
			return pcur;
		}
		pcur = pcur->next;
	}
	return NULL;
}
函数测试

（6）在pos位置之后插入

函数声明
//指定插入（之后）
void LTInsert(LTNode* pos, LTDataType x);

双链表同样是通过一个结点指针来维护，这个结点指针永远指向头结点——哨兵位，永远不会改变其指向，则不需要传二级指针。

逻辑演示

函数实现
//List.c
//双链表

//在pos位置之后插入数据
void LTInsert(LTNode* pos, LTDataType x) {
	assert(pos);
	LTNode* newnode = LTBuyNode(x);
	//pos newnode pos->next
	//生成两条链
	newnode->next = pos->next;
	newnode->prev = pos;
	//重连两条链——注意先后顺序
	pos->next->prev = newnode;    //先
	pos->next = newnode;          //后
}
函数测试

（7）删除pos位置的数据

函数声明
//指定删除
void LTErase(LTNode* pos);

双链表同样是通过一个结点指针来维护，这个结点指针永远指向头结点——哨兵位，永远不会改变其指向，则不需要传二级指针。

逻辑演示

函数实现
//List.c
//双链表

//删除pos位置的数据
void LTErase(LTNode* pos) {
	assert(pos);

	//pos->prev pos  pos->next
	//重连两条链——指出去的两条链不用管，只需修改指进来的两条链
	pos->next->prev = pos->prev;
	pos->prev->next = pos->next;

	free(pos);
	pos = NULL;
}
函数测试

（8）销毁

函数声明
//销毁
void LTDesTroy(LTNode** pphead);
void LTdesTroy(LTNode* phead);   
//推荐一级——
//优：保持接口一致性；
//缺：调用完后phead需手动置空
函数实现
//List.c
//双链表

//销毁
//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;
//}
void LTdesTroy(LTNode* phead) {
	//哨兵位不能为空
	assert(phead);

	LTNode* pcur = phead->next;
	while (pcur != phead)
	{
		LTNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	//此时链表中，只剩一个哨兵位
	free(phead);
	phead = NULL;
}
函数测试

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

完

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布