您现在的位置是:首页 >技术交流 >线性表之双向链表(详解)网站首页技术交流
线性表之双向链表(详解)
简介线性表之双向链表(详解)
?博客主页:️自信不孤单
?文章专栏:数据结构与算法
?代码仓库:破浪晓梦
?欢迎关注:欢迎大家点赞收藏+关注
文章目录
?前言
在前面我们已经学习了链表中的单链表,今天我们再来学习另一个常用的链表结构:带头双向循环链表。
?双向链表
1. 带头双向循环链表的结构
2. 带头双向循环链表的实现
首先来创建两个文件来实现单链表:
- List.h(节点的声明、接口函数声明、头文件的包含)
- 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) 只需修改指针指向 插入 动态顺序表,空间不够时需要扩容 没有容量的概念 应用场景 元素高效存储+频繁访问 任意位置插入和删除频繁 缓存利用率 高 低 备注:缓存利用率参考存储体系结构 以及局部原理性。
风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。