数据结构--双链表

平凡之路.

发布于 2024-10-09 15:07:32

590

发布于 2024-10-09 15:07:32

文章被收录于专栏：学习

一、引言

双链表是一种在节点之间通过两个指针进行连接的数据结构，每个节点都有两个指针：一个指向前一个节点，另一个指向下一个节点。带头节点的双链表在实际应用中非常常见，本文将详细介绍其实现方法，并提供完整的 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;//前后指针都指向自己，使得链表循环起来
}

2.初始化

//初始化
void ListInit(LN** pphead)
{
	*pphead = ListBuyNode(-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;//新节点prev指向原来的尾节点
	newnode->next = phead;//新节点next指向头节点
	phead->prev->next = newnode;//原来的尾节点next指向newnode
	phead->prev = newnode;//头节点的prev指向newnode
	//上面两行代码位置不能交换
}

5.头删

//头删
void ListPopFront(LN* phead)
{
	assert(phead && phead->next != phead);//链表必须有效且链表不为空
	LN* del = phead->next;
	del->next->prev = phead;
	phead->next = del->next;
	//删除del节点
	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;
	//删除del节点
	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;//没有找到 
}

9.插入节点

//插入，pos节点后插入
void ListInsert(LN* pos, DataType x)
{
	assert(pos);
	LN* newnode = ListBuyNode(x);
	newnode->next = pos->next;
	newnode->prev = pos;
	pos->next->prev = newnode;
	pos->next = newnode;
}

10.删除节点

//删除
void ListErase(LN* pos)//这里不传二级指针，是为了保持接口一致性
{
	assert(pos);
	pos->next->prev = pos->prev;
	pos->prev->next = pos->next;
	free(pos);
	pos = NULL;
}

11.销毁链表

//销毁链表
void ListDestory(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 ListDestory(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;//前后指针都指向自己，使得链表循环起来
}
//初始化
void ListInit(LN** pphead)
{
	*pphead = ListBuyNode(-1);//头节点，随便给一个值（用不到）
}
//尾插
void ListPushBack(LN* phead, DataType x)
{
	assert(phead);
	LN* newnode = ListBuyNode(x);
	newnode->prev = phead->prev;//新节点prev指向原来的尾节点
	newnode->next = phead;//新节点next指向头节点
	phead->prev->next = newnode;//原来的尾节点next指向newnode
	phead->prev = newnode;//头节点的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;
	//删除del节点
	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;
	//删除del节点
	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;//没有找到 
}
//插入，pos节点后插入
void ListInsert(LN* pos, DataType x)
{
	assert(pos);
	LN* newnode = ListBuyNode(x);
	newnode->next = pos->next;
	newnode->prev = pos;
	pos->next->prev = newnode;
	pos->next = newnode;
}
//删除
void ListErase(LN* pos)//这里不传二级指针，是为了保持接口一致性
{
	assert(pos);
	pos->next->prev = pos->prev;
	pos->prev->next = pos->next;
	free(pos);
	pos = NULL;
}
//销毁链表
void ListDestory(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);
	ListDestory(plist);
	plist = NULL;

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

六、总结

带头节点的双链表在进行节点的插入和删除操作时具有较好的灵活性。头节点的存在简化了链表操作的边界条件，减少了对空链表和链表边界的特殊处理。通过本文的实现和示例代码，你应该能掌握双链表的基本操作，并能够将其应用于实际的编程任务中。希望这个博客对你有帮助！如果你有任何问题或者需要进一步的解释，欢迎在评论区留言。

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

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

数据结构

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

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

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

登录后参与评论

0 条评论

热度