您现在的位置是:首页 >技术交流 >线性表之双向链表(详解)网站首页技术交流

线性表之双向链表(详解)

自信不孤单 2024-06-17 10:19:56
简介线性表之双向链表(详解)

?博客主页:️自信不孤单

?文章专栏:数据结构与算法

?代码仓库:破浪晓梦

?欢迎关注:欢迎大家点赞收藏+关注


?前言

在前面我们已经学习了链表中的单链表,今天我们再来学习另一个常用的链表结构:带头双向循环链表

?双向链表

1. 带头双向循环链表的结构

在这里插入图片描述

2. 带头双向循环链表的实现

首先来创建两个文件来实现单链表:

  1. List.h(节点的声明、接口函数声明、头文件的包含)
  2. List.c(双向链表接口函数的实现)

接着创建 test.c 文件来测试各个接口
如图:

在这里插入图片描述

List.h 文件内容如下:

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>

typedef int LTDataType;
typedef struct ListNode
{
	struct ListNode* next;
	struct ListNode* prev;
	LTDataType data;
}LTNode;

// 链表的初始化
LTNode* LTInit();
// 链表的打印
void LTPrint(LTNode* phead);
// 判断链表是否为空,为空返回真,否则返回假
bool LTEmpty(LTNode* phead);
// 链表尾插
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);
// 在pos之前插入
void LTInsert(LTNode* pos, LTDataType x);
// 删除pos位置的值
void LTErase(LTNode* pos);
// 链表的销毁
void LTDestroy(LTNode* phead);

接下来,我们在 List.c 文件中实现各个接口函数。

2.1 动态申请一个节点

在堆上申请一个节点结构体大小的空间,并用该节点存放数据 x,节点的 prev 指针和 next 指针指向 NULL,返回节点的地址。

LTNode* BuyLTNode(LTDataType x)
{
	LTNode* new = (LTNode*)malloc(sizeof(LTNode));
	if (new == NULL)
	{
		perror("malloc fail");
		return NULL;
	}
	new->data = x;
	new->prev = NULL;
	new->prev = NULL;
	return new;
}

2.2 初始化链表

开辟一个哨兵卫的头节点,其 prev 指针和 next 指针指向它自己,返回节点地址。

LTNode* LTInit()
{
	LTNode* phead = BuyLTNode(-1);
	phead->prev = phead;
	phead->next = phead;
	return phead;
}

2.3 打印链表

遍历打印,当 cur 指针等于头节点指针时停止打印。

void LTPrint(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead->next;
	printf("guard<=>");
	while (cur != phead)
	{
		printf("%d<=>", cur->data);
		cur = cur->next;
	}
	printf("
");
}

2.4 双向链表尾插

void LTPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* new = BuyLTNode(x);
	LTNode* tail = phead->prev;
	new->prev = tail;
	new->next = phead;
	tail->next = new;
	phead->prev = new;
}

2.5 双向链表头插

void LTPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* new = BuyLTNode(x);
	LTNode* first = phead->next;
	new->prev = phead;
	new->next = first;
	first->prev = new;
	phead->next = new;
}

2.6 判断链表是否为空

当链表中只有哨兵卫的头结点时链表为空。链表为空返回真,否则返回假。

bool LTEmpty(LTNode* phead)
{
	assert(phead);
	return (phead == phead->next);
}

2.7 双向链表尾删

void LTPopBack(LTNode* phead)
{
	assert(phead);
	assert(!LTEmpty(phead));
	LTNode* tail = phead->prev;
	phead->prev = tail->prev;
	tail->prev->next = phead;
	free(tail);
}

2.8 双向链表头删

void LTPopFront(LTNode* phead)
{
	assert(phead);
	assert(!LTEmpty(phead));
	LTNode* first = phead->next;
	phead->next = first->next;
	first->next->prev = phead;
	free(first);
}

2.9 双向链表查找

返回所找到节点的指针,没找到则返回 NULL。

注:查找函数可以配合指定位置操作函数来使用。

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.10 在指定位置前插入数据

void LTInsert(LTNode* pos, LTDataType x)
{
	assert(pos);
	LTNode* new = BuyLTNode(x);
	LTNode* prev = pos->prev;
	new->prev = prev;
	new->next = pos;
	prev->next = new;
	pos->prev = new;
}

2.11 删除指定位置的数据

void LTErase(LTNode* pos)
{
	assert(pos);
	LTNode* prev = pos->prev;
	LTNode* next = pos->next;
	prev->next = next;
	next->prev = prev;
	free(pos);
}

2.12 双向链表的销毁

void LTDestroy(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		LTNode* next = cur->next;
		free(cur);
		cur = next;
	}
	free(phead);
}

注:在每个接口函数中一定要合理地使用assert函数断言防止对空指针的引用。

3.接口测试

test.c 文件内容如下:

#include "List.h"

void Test()
{
	LTNode* phead = LTInit();
	
	LTPushBack(phead, 10);
	LTPushBack(phead, 20);
	LTPushBack(phead, 30);
	LTPrint(phead);
	
	LTPushFront(phead, 0);
	LTPushFront(phead, -20);
	LTPushFront(phead, -30);
	LTPrint(phead);
	
	LTNode* insert = LTFind(phead, 0);
	LTInsert(insert, -10);
	LTPrint(phead);
	
	LTPopBack(phead);
	LTPrint(phead);
	
	LTPopFront(phead);
	LTPrint(phead);
	
	LTNode* del = LTFind(phead, 10);
	LTErase(del);
	LTPrint(phead);

	LTDestroy(phead);
	phead = NULL;
}

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

注意:销毁链表后,记得将 phead 手动置空哦!

运行结果:

在这里插入图片描述

学完带头双向链表,下面我们来对之前学到的顺序表和链表做一下区分和总结。

?顺序表和链表的区别

不同点顺序表链表
存储空间上物理上一定连续逻辑上连续,但物理上不一定连续
随机访问支持O(1)不支持:O(N)
任意位置插入或者删除元素可能需要搬移元素,效率低 O(N)只需修改指针指向
插入动态顺序表,空间不够时需要扩容没有容量的概念
应用场景元素高效存储+频繁访问任意位置插入和删除频繁
缓存利用率

备注:缓存利用率参考存储体系结构 以及局部原理性。

在这里插入图片描述

风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。