1. AI技术聚合首页
  2. IT

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

青葱年少 • • IT • 阅读 30

目录

往期

链表-单链表

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

1.1 -> 接口声明

#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 -> 双向链表初始化

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

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

	return phead;
}

1.2.2 -> 动态申请一个结点

// 动态申请一个结点
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 -> 双向链表销毁

// 双向链表销毁
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 -> 双向链表打印

// 双向链表打印
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 -> 双向链表判空

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

	return phead->next == phead;
}

1.2.6 -> 双向链表尾插

// 双向链表尾插
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 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 -> 双向链表尾删

// 双向链表尾删
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 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 -> 双向链表头插

// 双向链表头插
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 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 -> 双向链表头删

// 双向链表头删
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);
}
// 头删测试
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 -> 双向链表查找

// 双向链表查找
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的前面进行插入

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

// 查找插入测试
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位置的节点

// 双向链表删除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

#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

#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

#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;
}

感谢大佬们支持！！！

互三啦！！！

版权声明：本文为博主作者：枫叶丹4原创文章，版权归属原作者，如果侵权，请联系我们删除！

原文链接：https://blog.csdn.net/weixin_74809706/article/details/136461337

共计人评分，平均分

到目前为止还没有投票！成为第一位评论此文章。

赞 (0)
青葱年少的头像青葱年少普通用户
0
上一篇 2024年4月1日
下一篇 2024年4月1日

相关推荐