双向链表：穿梭数据的双向桥梁

平凡之路.

发布于 2025-06-02 12:22:42

14200

代码可运行

文章被收录于专栏：学习学习

运行总次数：0

代码可运行

一、引言

双链表是一种在节点之间通过两个指针进行连接的数据结构，每个节点都有两个指针：一个指向前一个节点，另一个指向下一个节点。带头节点的双链表在实际应用中非常常见，本文将详细介绍其实现方法，并提供完整的 C 语言代码示例。

二、链表的分类

链表的结构⾮常多样，以下情况组合起来就有8种（2 x 2 x 2）链表结构：

1.单向或双向

单向链表:
- 每个节点包含一个指向下一个节点的指针。
- 只能从头到尾单向遍历。
- 插入和删除操作较简单，但需要从头开始查找节点。
双向链表:
- 每个节点包含两个指针，一个指向下一个节点，一个指向前一个节点。
- 可以从头到尾或尾到头双向遍历。
- 插入和删除操作更灵活，但每个节点占用更多内存。

2.带头或不带头

带头节点:
- 链表有一个额外的头节点，它不存储实际数据，只作为链表的起始点。
- 操作如插入和删除更简单，因为头节点简化了边界条件处理。
不带头节点:
- 链表从第一个实际数据节点开始，没有额外的头节点。
- 需要特别处理空链表和边界情况。

3.循环或不循环

循环链表:
- 链表的尾节点指向头节点，形成一个循环结构。
- 遍历时可以从任何节点开始，不会遇到“末尾”问题。
非循环链表:
- 链表的尾节点指向 NULL，表示链表的结束。
- 遍历时需要检查是否到达链表末尾。

虽然有这么多的链表的结构，但是我们实际中最常⽤还是两种结构：单链表和双向带头循环链表 1. ⽆头单向⾮循环链表：结构简单，⼀般不会单独⽤来存数据。实际中更多是作为其他数据结构的⼦结构，如哈希桶、图的邻接表等等。另外这种结构在笔试⾯试中出现很多。 2. 带头双向循环链表：结构最复杂，⼀般⽤在单独存储数据。实际中使⽤的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使⽤代码实现以后会发现结构会带来很多优势，实现反⽽简单了，后⾯我们代码实现了就知道了。

本节我们所讲的双链表即为双向带头循环链表。

三、双链表的概念与基本结构

1.概念

双链表简介 双链表是一种链表变体，每个节点都包含三个部分：存储的数据。指向前一个节点的指针（prev）。指向下一个节点的指针（next）。带头节点的双链表有一个特殊的节点称为头节点，它不存储有效数据，只是作为链表的一个起始辅助节点存在。头节点的 prev 指针指向自己，next 指针指向链表的第一个有效节点。

2.基本结构

双链表的基本结构如下：

typedef struct ListNode
{
	DataType data;//数据域
	struct ListNode* prev;//指针域，指向前一个节点
	struct ListNode* next;//指针域，指向后一个节点
}LN;

三、双链表的常见操作

1.创建节点

// 创建一个新节点
LN* ListBuyNode(DataType x)
{
	LN* node = (LN*)malloc(sizeof(LN));
	if (node == NULL)
	{
		perror("malloc fail!");
		exit(1);
	}
	node->data = x;
	node->prev = node->next = node; // 前后指针都指向自己，形成循环链表
	return node;
}

2.初始化

// 初始化链表
void ListInit(LN** pphead)
{
	*pphead = ListBuyNode(-1); // 创建头节点，值为-1（不会被使用）
}

3.头插

// 头部插入节点
void ListPushFront(LN* phead, DataType x)
{
	assert(phead);
	LN* newnode = ListBuyNode(x);
	newnode->next = phead->next; // 新节点的后继指向头节点的后继节点
	newnode->prev = phead; // 新节点的前驱指向头节点
	phead->next->prev = newnode; // 原头节点的后继节点的前驱指向新节点
	phead->next = newnode; // 头节点的后继指向新节点
}

4.尾插

// 尾部插入节点
void ListPushBack(LN* phead, DataType x)
{
	assert(phead);
	LN* newnode = ListBuyNode(x);
	newnode->prev = phead->prev; // 新节点的前驱指向原来的尾节点
	newnode->next = phead; // 新节点的后继指向头节点
	phead->prev->next = newnode; // 原尾节点的后继指向新节点
	phead->prev = newnode; // 头节点的前驱指向新节点
}

5.头删

// 删除头部节点
void ListPopFront(LN* phead)
{
	assert(phead && phead->next != phead); // 确保链表不为空
	LN* del = phead->next;
	del->next->prev = phead; // 删除节点的后继节点的前驱指向头节点
	phead->next = del->next; // 头节点的后继指向删除节点的后继
	free(del); // 释放删除节点的内存
	del = NULL;
}

6.尾删

// 删除尾部节点
void ListPopBack(LN* phead)
{
	assert(phead && phead->next != phead); // 确保链表不为空
	LN* del = phead->prev;
	del->prev->next = phead; // 删除节点前驱的后继指向头节点
	phead->prev = del->prev; // 头节点的前驱指向删除节点的前驱
	free(del); // 释放删除节点的内存
	del = NULL;
}

7.打印

// 打印链表
void ListPrint(LN* phead)
{
	LN* pcur = phead->next;
	while (pcur != phead)
	{
		printf("%d->", pcur->data); // 打印当前节点的数据
		pcur = pcur->next;
	}
	printf("NULL\n"); // 打印链表结束标志
}

8.查找

// 查找链表中的节点
LN* ListFind(LN* phead, DataType x)
{
	LN* pcur = phead->next;
	while (pcur != phead)
	{
		if (pcur->data == x)
		{
			return pcur; // 找到匹配的节点并返回
		}
		pcur = pcur->next;
	}
	return NULL; // 未找到匹配节点，返回 NULL
}

9.插入节点

// 在指定位置后插入节点
void ListInsert(LN* pos, DataType x)
{
	assert(pos);
	LN* newnode = ListBuyNode(x);
	newnode->next = pos->next; // 新节点的后继指向 pos 的后继节点
	newnode->prev = pos; // 新节点的前驱指向 pos
	pos->next->prev = newnode; // pos 的后继节点的前驱指向新节点
	pos->next = newnode; // pos 的后继指向新节点
}

10.删除节点

// 删除指定位置的节点
void ListErase(LN* pos)
{
	assert(pos);
	pos->next->prev = pos->prev; // 删除节点的后继节点的前驱指向删除节点的前驱
	pos->prev->next = pos->next; // 删除节点的前驱节点的后继指向删除节点的后继
	free(pos); // 释放删除节点的内存
	pos = NULL;
}

11.销毁链表

// 销毁链表
void ListDestroy(LN* phead)
{
	assert(phead);
	LN* pcur = phead->next;
	while (pcur != phead)
	{
		LN* next = pcur->next;
		free(pcur); // 释放当前节点的内存
		pcur = next;
	}
	free(phead); // 释放头节点的内存
	phead = NULL;
}

注： LTErase和LTDestroy参数理论上要传一级，因为我们需要让形参的改变影响到实参，但是为了保持接口一致性才传的一级。传一级存在的问题是，当形参phead置为NULL后，实参plist不会被修改为NULL，因此解决办法是:调用完方法后手动将实参置为NULL~

五、完整代码

1.List.h

该部分放顺序表结构定义、函数的声明

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int DataType;
typedef struct ListNode
{
	DataType data;//数据域
	struct ListNode* prev;//指针域，指向前一个节点
	struct ListNode* next;//指针域，指向后一个节点
}LN;
//初始化
void ListInit(LN** pphead);
//尾插
void ListPushBack(LN*phead,DataType x);
//头插
void ListPushFront(LN*phead,DataType x);
//打印
void ListPrint(LN* phead);
//尾删
void ListPopBack(LN* phead);
//头删
void ListPopFront(LN* phead);
//查找
LN* ListFind(LN* phead, DataType x);
//插入，pos节点后插入
void ListInsert(LN* pos, DataType x);
//删除
void ListErase(LN* pos);
//销毁链表
void ListDestroy(LN* phead);

2.List.c

该部分是函数功能的实现

#define _CRT_SECURE_NO_WARNINGS
#include"List.h"

// 创建一个新节点
LN* ListBuyNode(DataType x)
{
	LN* node = (LN*)malloc(sizeof(LN));
	if (node == NULL)
	{
		perror("malloc fail!");
		exit(1);
	}
	node->data = x;
	node->prev = node->next = node; // 前后指针都指向自己，形成循环链表
	return node;
}

// 初始化链表
void ListInit(LN** pphead)
{
	*pphead = ListBuyNode(-1); // 创建头节点，值为-1（不会被使用）
}

// 尾部插入节点
void ListPushBack(LN* phead, DataType x)
{
	assert(phead);
	LN* newnode = ListBuyNode(x);
	newnode->prev = phead->prev; // 新节点的前驱指向原来的尾节点
	newnode->next = phead; // 新节点的后继指向头节点
	phead->prev->next = newnode; // 原尾节点的后继指向新节点
	phead->prev = newnode; // 头节点的前驱指向新节点
}

// 头部插入节点
void ListPushFront(LN* phead, DataType x)
{
	assert(phead);
	LN* newnode = ListBuyNode(x);
	newnode->next = phead->next; // 新节点的后继指向头节点的后继节点
	newnode->prev = phead; // 新节点的前驱指向头节点
	phead->next->prev = newnode; // 原头节点的后继节点的前驱指向新节点
	phead->next = newnode; // 头节点的后继指向新节点
}

// 删除尾部节点
void ListPopBack(LN* phead)
{
	assert(phead && phead->next != phead); // 确保链表不为空
	LN* del = phead->prev;
	del->prev->next = phead; // 删除节点前驱的后继指向头节点
	phead->prev = del->prev; // 头节点的前驱指向删除节点的前驱
	free(del); // 释放删除节点的内存
	del = NULL;
}

// 删除头部节点
void ListPopFront(LN* phead)
{
	assert(phead && phead->next != phead); // 确保链表不为空
	LN* del = phead->next;
	del->next->prev = phead; // 删除节点的后继节点的前驱指向头节点
	phead->next = del->next; // 头节点的后继指向删除节点的后继
	free(del); // 释放删除节点的内存
	del = NULL;
}

// 打印链表
void ListPrint(LN* phead)
{
	LN* pcur = phead->next;
	while (pcur != phead)
	{
		printf("%d->", pcur->data); // 打印当前节点的数据
		pcur = pcur->next;
	}
	printf("NULL\n"); // 打印链表结束标志
}

// 查找链表中的节点
LN* ListFind(LN* phead, DataType x)
{
	LN* pcur = phead->next;
	while (pcur != phead)
	{
		if (pcur->data == x)
		{
			return pcur; // 找到匹配的节点并返回
		}
		pcur = pcur->next;
	}
	return NULL; // 未找到匹配节点，返回 NULL
}

// 在指定位置后插入节点
void ListInsert(LN* pos, DataType x)
{
	assert(pos);
	LN* newnode = ListBuyNode(x);
	newnode->next = pos->next; // 新节点的后继指向 pos 的后继节点
	newnode->prev = pos; // 新节点的前驱指向 pos
	pos->next->prev = newnode; // pos 的后继节点的前驱指向新节点
	pos->next = newnode; // pos 的后继指向新节点
}

// 删除指定位置的节点
void ListErase(LN* pos)
{
	assert(pos);
	pos->next->prev = pos->prev; // 删除节点的后继节点的前驱指向删除节点的前驱
	pos->prev->next = pos->next; // 删除节点的前驱节点的后继指向删除节点的后继
	free(pos); // 释放删除节点的内存
	pos = NULL;
}

// 销毁链表
void ListDestroy(LN* phead)
{
	assert(phead);
	LN* pcur = phead->next;
	while (pcur != phead)
	{
		LN* next = pcur->next;
		free(pcur); // 释放当前节点的内存
		pcur = next;
	}
	free(phead); // 释放头节点的内存
	phead = NULL;
}

3.test.c

测试，函数的调用

#define _CRT_SECURE_NO_WARNINGS
#include"List.h"
void test01()
{
	LN* plist = NULL;
	ListInit(&plist);
	/*ListPushBack(plist, 3);
	ListPushBack(plist, 2);
	ListPushBack(plist, 1);
	ListPushBack(plist, 0);*/
	ListPushFront(plist, 1);
	ListPushFront(plist, 2);
	ListPushFront(plist, 3);
	ListPushFront(plist, 4);
	// ListPopBack(plist);
	//ListPopFront(plist);
	LN* find = ListFind(plist, 3);
	//if (find == NULL)
	//	printf("没找到\n");
	//else
	//	printf("找到了\n");
	ListInsert(find, 99);
	ListErase(find);
	find = NULL;
	ListPrint(plist);
	ListDestroy(plist);
	plist = NULL;

}
int main()
{
	test01();
	return 0;
}

六、总结

带头节点的双链表在进行节点的插入和删除操作时具有较好的灵活性。头节点的存在简化了链表操作的边界条件，减少了对空链表和链表边界的特殊处理。通过本文的实现和示例代码，你应该能掌握双链表的基本操作，并能够将其应用于实际的编程任务中。

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2024-10-16，如有侵权请联系 cloudcommunity@tencent.com 删除

链表

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

登录后参与评论

0 条评论

热度