前往小程序，Get更优阅读体验！
立即前往
文档建议反馈控制台
首页
学习
活动
专区
工具
TVP
最新优惠活动
文章/答案/技术大牛
发布
首页
学习
活动
专区
工具
TVP最新优惠活动
返回腾讯云官网
社区首页 >专栏 >【海贼王的数据航海】链表—双向链表

【海贼王的数据航海】链表—双向链表

作者头像
枫叶丹
发布于 2024-06-04 12:20:42
760
发布于 2024-06-04 12:20:42
举报
文章被收录于专栏：C++

往期

链表-单链表

1 -> 带头+双向+循环链表(双链表)

1.1 -> 接口声明

代码语言：javascript
复制
#pragma once

#define  _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>

// 带头+双向+循环链表增删查改实现
typedef int LTDataType;

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

// 双向链表初始化
LTNode* LTInit();

// 动态申请一个结点
LTNode* BuyLTNode(LTDataType x);

// 双向链表销毁
void LTDestory(LTNode* phead);

// 双向链表打印
void LTPrint(LTNode* phead);

// 双向链表判空
bool LTEmpty(LTNode* phead);

// 双向链表尾插
void LTPushBack(LTNode* phead, LTDataType x);

// 双向链表尾删
void LTPopBack(LTNode* phead);

// 双向链表头插
void LTPushFront(LTNode* phead, LTDataType x);

// 双向链表头删
void LTPopFront(LTNode* phead);

// 双向链表查找
LTNode* LTFind(LTNode* phead, LTDataType x);

// 双向链表在pos的前面进行插入
void LTInsert(LTNode* pos, LTDataType x);

// 双向链表删除pos位置的节点
void LTErase(LTNode* pos);

1.2 -> 接口实现

1.2.1 -> 双向链表初始化
代码语言：javascript
复制
// 双向链表初始化
LTNode* LTInit()
{
	LTNode* phead = BuyLTNode(-1);

	phead->next = phead;
	phead->prev = phead;

	return phead;
}
1.2.2 -> 动态申请一个结点
代码语言：javascript
复制
// 动态申请一个结点
LTNode* BuyLTNode(LTDataType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return NULL;
	}

	newnode->data = x;
	newnode->next = NULL;
	newnode->prev = NULL;

	return newnode;
}
1.2.3 -> 双向链表销毁
代码语言：javascript
复制
// 双向链表销毁
void LTDestory(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		LTNode* next = cur->next;
		free(cur);
		cur = next;
	}

	free(phead);
}
1.2.4 -> 双向链表打印
代码语言：javascript
复制
// 双向链表打印
void LTPrint(LTNode* phead)
{
	assert(phead);

	printf("guard<==>");
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		printf("%d<==>", cur->data);
		cur = cur->next;
	}
	printf("\n");
}
1.2.5 -> 双向链表判空
代码语言：javascript
复制
// 双向链表判空
bool LTEmpty(LTNode* phead)
{
	assert(phead);

	return phead->next == phead;
}
1.2.6 -> 双向链表尾插
代码语言：javascript
复制
// 双向链表尾插
void LTPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);

	LTNode* tail = phead->prev;
	LTNode* newnode = BuyLTNode(x);

	tail->next = newnode;
	newnode->prev = tail;
	newnode->next = phead;
	phead->prev = newnode;

	// 复用
	// LTInsert(phead, x);
}
代码语言：javascript
复制
// 尾插测试
void Test1()
{
	LTNode* plist = LTInit();

	LTPushBack(plist, 1);
	LTPushBack(plist, 2);
	LTPushBack(plist, 3);
	LTPushBack(plist, 4);
	LTPushBack(plist, 5);

	LTPrint(plist);

	LTDestory(plist);
	plist = NULL;
}
1.2.7 -> 双向链表尾删
代码语言：javascript
复制
// 双向链表尾删
void LTPopBack(LTNode* phead)
{
	assert(phead);
	assert(!LTEmpty(phead));

	LTNode* tail = phead->prev;
	LTNode* tailPrev = tail->prev;

	free(tail);
	tailPrev->next = phead;
	phead->prev = tailPrev;

	// 复用
	// LTErase(phead->prev);
}
代码语言：javascript
复制
// 尾删测试
void Test2()
{
	LTNode* plist = LTInit();

	LTPushBack(plist, 1);
	LTPushBack(plist, 2);
	LTPushBack(plist, 3);
	LTPushBack(plist, 4);
	LTPushBack(plist, 5);

	LTPrint(plist);

	LTPopBack(plist);
	LTPrint(plist);
	LTPopBack(plist);
	LTPrint(plist);
	LTPopBack(plist);
	LTPrint(plist);
	LTPopBack(plist);
	LTPrint(plist);
	LTPopBack(plist);
	LTPrint(plist);

	LTDestory(plist);
	plist = NULL;
}
1.2.8 -> 双向链表头插
代码语言：javascript
复制
// 双向链表头插
void LTPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newnode = BuyLTNode(x);

	newnode->next = phead->next;
	phead->next->prev = newnode;
	phead->next = newnode;
	newnode->prev = phead;

	// 复用
	// LTInsert(phead->next, x);
}
代码语言：javascript
复制
// 头插测试
void Test3()
{
	LTNode* plist = LTInit();

	LTPushFront(plist, 1);
	LTPushFront(plist, 2);
	LTPushFront(plist, 3);
	LTPushFront(plist, 4);
	LTPushFront(plist, 5);

	LTPrint(plist);

	LTDestory(plist);
	plist = NULL;
}
1.2.9 -> 双向链表头删
代码语言：javascript
复制
// 双向链表头删
void LTPopFront(LTNode* phead)
{
	assert(phead);
	assert(!LTEmpty(phead));
	LTNode* first = phead->next;
	LTNode* second = first->next;

	phead->next = second;
	second->prev = phead;

	free(first);

	// 复用
	// LTErase(phead->next);
}
代码语言：javascript
复制
// 头删测试
void Test4()
{
	LTNode* plist = LTInit();

	LTPushBack(plist, 1);
	LTPushBack(plist, 2);
	LTPushBack(plist, 3);
	LTPushBack(plist, 4);
	LTPushBack(plist, 5);

	LTPrint(plist);

	LTPopFront(plist);
	LTPrint(plist);
	LTPopFront(plist);
	LTPrint(plist);
	LTPopFront(plist);
	LTPrint(plist);
	LTPopFront(plist);
	LTPrint(plist);
	LTPopFront(plist);
	LTPrint(plist);

	LTDestory(plist);
	plist = NULL;
}
1.2.10 -> 双向链表查找
代码语言：javascript
复制
// 双向链表查找
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;
}
1.2.11 -> 双向链表在pos的前面进行插入
代码语言：javascript
复制
// 双向链表在pos的前面进行插入
void LTInsert(LTNode* pos, LTDataType x)
{
	assert(pos);

	LTNode* prev = pos->prev;
	LTNode* newnode = BuyLTNode(x);

	prev->next = newnode;
	newnode->prev = prev;
	newnode->next = pos;
	pos->prev = newnode;
}
代码语言：javascript
复制
// 查找插入测试
void Test5()
{
	LTNode* plist = LTInit();

	LTPushBack(plist, 1);
	LTPushBack(plist, 2);
	LTPushBack(plist, 3);
	LTPushBack(plist, 4);
	LTPushBack(plist, 5);

	LTPrint(plist);

	LTNode* pos = LTFind(plist, 3);
	if (pos)
		LTInsert(pos, 99);
	LTPrint(plist);

	LTDestory(plist);
	plist = NULL;
}
1.2.12 -> 双向链表删除pos位置的节点
代码语言：javascript
复制
// 双向链表删除pos位置的节点
void LTErase(LTNode* pos)
{
	assert(pos);

	LTNode* posPrev = pos->prev;
	LTNode* posNext = pos->next;

	posPrev->next = posNext;
	posNext->prev = posPrev;

	free(pos);
}

2 -> 顺序表和链表的区别

不同点

顺序表

链表

存储空间上

物理上一定连续

逻辑上连续，但物理上不一定连续

随机访问

支持O(1)

不支持:O(N)

任意位置插入或者删除元素

可能需要搬移元素，效率低O(N)

只需修改指针指向

插入

动态顺序表，空间不够时需要扩容

没有容量的概念

应用场景

元素高效存储+频繁访问

任意位置插入和删除频繁

缓存利用率

高

低

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

3 -> 完整代码

3.1 -> List.c

代码语言：javascript
复制
#include "List.h"

// 双向链表初始化
LTNode* LTInit()
{
	LTNode* phead = BuyLTNode(-1);

	phead->next = phead;
	phead->prev = phead;

	return phead;
}

// 动态申请一个结点
LTNode* BuyLTNode(LTDataType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return NULL;
	}

	newnode->data = x;
	newnode->next = NULL;
	newnode->prev = NULL;

	return newnode;
}

// 双向链表销毁
void LTDestory(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		LTNode* next = cur->next;
		free(cur);
		cur = next;
	}

	free(phead);
}

// 双向链表打印
void LTPrint(LTNode* phead)
{
	assert(phead);

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

// 双向链表判空
bool LTEmpty(LTNode* phead)
{
	assert(phead);

	return phead->next == phead;
}

// 双向链表尾插
void LTPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);

	LTNode* tail = phead->prev;
	LTNode* newnode = BuyLTNode(x);

	tail->next = newnode;
	newnode->prev = tail;
	newnode->next = phead;
	phead->prev = newnode;

	// 复用
	// LTInsert(phead, x);
}

// 双向链表尾删
void LTPopBack(LTNode* phead)
{
	assert(phead);
	assert(!LTEmpty(phead));

	LTNode* tail = phead->prev;
	LTNode* tailPrev = tail->prev;

	free(tail);
	tailPrev->next = phead;
	phead->prev = tailPrev;

	// 复用
	// LTErase(phead->prev);
}

// 双向链表头插
void LTPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newnode = BuyLTNode(x);

	newnode->next = phead->next;
	phead->next->prev = newnode;
	phead->next = newnode;
	newnode->prev = phead;

	// 复用
	// LTInsert(phead->next, x);
}

// 双向链表头删
void LTPopFront(LTNode* phead)
{
	assert(phead);
	assert(!LTEmpty(phead));
	LTNode* first = phead->next;
	LTNode* second = first->next;

	phead->next = second;
	second->prev = phead;

	free(first);

	// 复用
	// LTErase(phead->next);
}

// 双向链表查找
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;
}

// 双向链表在pos的前面进行插入
void LTInsert(LTNode* pos, LTDataType x)
{
	assert(pos);

	LTNode* prev = pos->prev;
	LTNode* newnode = BuyLTNode(x);

	prev->next = newnode;
	newnode->prev = prev;
	newnode->next = pos;
	pos->prev = newnode;
}

// 双向链表删除pos位置的节点
void LTErase(LTNode* pos)
{
	assert(pos);

	LTNode* posPrev = pos->prev;
	LTNode* posNext = pos->next;

	posPrev->next = posNext;
	posNext->prev = posPrev;

	free(pos);
}

3.2 -> List.h

代码语言：javascript
复制
#pragma once

#define  _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>

// 带头+双向+循环链表增删查改实现
typedef int LTDataType;

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

// 双向链表初始化
LTNode* LTInit();

// 动态申请一个结点
LTNode* BuyLTNode(LTDataType x);

// 双向链表销毁
void LTDestory(LTNode* phead);

// 双向链表打印
void LTPrint(LTNode* phead);

// 双向链表判空
bool LTEmpty(LTNode* phead);

// 双向链表尾插
void LTPushBack(LTNode* phead, LTDataType x);

// 双向链表尾删
void LTPopBack(LTNode* phead);

// 双向链表头插
void LTPushFront(LTNode* phead, LTDataType x);

// 双向链表头删
void LTPopFront(LTNode* phead);

// 双向链表查找
LTNode* LTFind(LTNode* phead, LTDataType x);

// 双向链表在pos的前面进行插入
void LTInsert(LTNode* pos, LTDataType x);

// 双向链表删除pos位置的节点
void LTErase(LTNode* pos);

3.3 -> Test.c

代码语言：javascript
复制
#include "List.h"

// 尾插测试
void Test1()
{
	LTNode* plist = LTInit();

	LTPushBack(plist, 1);
	LTPushBack(plist, 2);
	LTPushBack(plist, 3);
	LTPushBack(plist, 4);
	LTPushBack(plist, 5);

	LTPrint(plist);

	LTDestory(plist);
	plist = NULL;
}

// 尾删测试
void Test2()
{
	LTNode* plist = LTInit();

	LTPushBack(plist, 1);
	LTPushBack(plist, 2);
	LTPushBack(plist, 3);
	LTPushBack(plist, 4);
	LTPushBack(plist, 5);

	LTPrint(plist);

	LTPopBack(plist);
	LTPrint(plist);
	LTPopBack(plist);
	LTPrint(plist);
	LTPopBack(plist);
	LTPrint(plist);
	LTPopBack(plist);
	LTPrint(plist);
	LTPopBack(plist);
	LTPrint(plist);

	LTDestory(plist);
	plist = NULL;
}

// 头插测试
void Test3()
{
	LTNode* plist = LTInit();

	LTPushFront(plist, 1);
	LTPushFront(plist, 2);
	LTPushFront(plist, 3);
	LTPushFront(plist, 4);
	LTPushFront(plist, 5);

	LTPrint(plist);

	LTDestory(plist);
	plist = NULL;
}

// 头删测试
void Test4()
{
	LTNode* plist = LTInit();

	LTPushBack(plist, 1);
	LTPushBack(plist, 2);
	LTPushBack(plist, 3);
	LTPushBack(plist, 4);
	LTPushBack(plist, 5);

	LTPrint(plist);

	LTPopFront(plist);
	LTPrint(plist);
	LTPopFront(plist);
	LTPrint(plist);
	LTPopFront(plist);
	LTPrint(plist);
	LTPopFront(plist);
	LTPrint(plist);
	LTPopFront(plist);
	LTPrint(plist);

	LTDestory(plist);
	plist = NULL;
}

// 查找插入测试
void Test5()
{
	LTNode* plist = LTInit();

	LTPushBack(plist, 1);
	LTPushBack(plist, 2);
	LTPushBack(plist, 3);
	LTPushBack(plist, 4);
	LTPushBack(plist, 5);

	LTPrint(plist);

	LTNode* pos = LTFind(plist, 3);
	if (pos)
		LTInsert(pos, 99);
	LTPrint(plist);

	LTDestory(plist);
	plist = NULL;
}

int main()
{


	return 0;
}

感谢大佬们支持！！！

互三啦！！！

本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2024-03-13，如有侵权请联系 cloudcommunity@tencent.com 删除
链表
数据
plist
void
测试

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

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

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

链表
数据
plist
void
测试
评论
登录后参与评论
0 条评论
热度
最新
登录 后参与评论
推荐阅读
LV.
文章
0
获赞
0
目录
  • 往期
  • 1 -> 带头+双向+循环链表(双链表)
    • 1.1 -> 接口声明
      • 1.2 -> 接口实现
        • 1.2.1 -> 双向链表初始化
        • 1.2.2 -> 动态申请一个结点
        • 1.2.3 -> 双向链表销毁
        • 1.2.4 -> 双向链表打印
        • 1.2.5 -> 双向链表判空
        • 1.2.6 -> 双向链表尾插
        • 1.2.7 -> 双向链表尾删
        • 1.2.8 -> 双向链表头插
        • 1.2.9 -> 双向链表头删
        • 1.2.10 -> 双向链表查找
        • 1.2.11 -> 双向链表在pos的前面进行插入
        • 1.2.12 -> 双向链表删除pos位置的节点
    • 2 -> 顺序表和链表的区别
    • 3 -> 完整代码
      • 3.1 -> List.c
        • 3.2 -> List.h
          • 3.3 -> Test.c
          相关产品与服务
          腾讯云服务器利旧
          云服务器（Cloud Virtual Machine，CVM）提供安全可靠的弹性计算服务。 您可以实时扩展或缩减计算资源，适应变化的业务需求，并只需按实际使用的资源计费。使用 CVM 可以极大降低您的软硬件采购成本，简化 IT 运维工作。
          产品介绍
          11.11 上云拼团GO
          领券

          腾讯云开发者

          扫码关注腾讯云开发者

          扫码关注腾讯云开发者

          领取腾讯云代金券

          热门产品

          热门推荐

          更多推荐

          Copyright © 2013 - 2024 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有 

          深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 深公网安备号 44030502008569

          腾讯云计算（北京）有限责任公司 京ICP证150476号 |  京ICP备11018762号 | 京公网安备号11010802020287

          问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档

          Copyright © 2013 - 2024 Tencent Cloud.

          All Rights Reserved. 腾讯云 版权所有

          登录 后参与评论