1. Toy模板网首页
  2. > Toy博客

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

6月前 作者：枫叶丹4 分类：Toy博客 阅读(32) 违法举报

这篇具有很好参考价值的文章主要介绍了【海贼王的数据航海】链表—双向链表。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

目录

往期

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

【海贼王的数据航海】链表—双向链表,数据结构,链表,数据结构,c语言,开发语言,visualstudio,后端

往期

链表-单链表

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

 【海贼王的数据航海】链表—双向链表,数据结构,链表,数据结构,c语言,开发语言,visualstudio,后端

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

【海贼王的数据航海】链表—双向链表,数据结构,链表,数据结构,c语言,开发语言,visualstudio,后端

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

【海贼王的数据航海】链表—双向链表,数据结构,链表,数据结构,c语言,开发语言,visualstudio,后端

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

【海贼王的数据航海】链表—双向链表,数据结构,链表,数据结构,c语言,开发语言,visualstudio,后端

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

【海贼王的数据航海】链表—双向链表,数据结构,链表,数据结构,c语言,开发语言,visualstudio,后端

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) 只需修改指针指向
插入 动态顺序表，空间不够时需要扩容 没有容量的概念
应用场景 元素高效存储+频繁访问 任意位置插入和删除频繁
缓存利用率 高 低

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

【海贼王的数据航海】链表—双向链表,数据结构,链表,数据结构,c语言,开发语言,visualstudio,后端

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

感谢大佬们支持！！！

互三啦！！！文章来源地址https://www.toymoban.com/news/detail-839755.html

到了这里，关于【海贼王的数据航海】链表—双向链表的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 【海贼王的数据航海】排序——直接选择排序|堆排序

    【海贼王的数据航海】排序——直接选择排序|堆排序

    目录 1 - 选择排序 1.1 - 基本思想 1.2 - 直接选择排序 1.2.1 - 代码实现 1.3 - 堆排序 1.3.1 - 代码实现 每一次从待排序的数据元素中选出最小(或最大)的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。 在元素集合arr[i] -- arr[n - 1]中选择关键码最大(或最小)的数据

    2024年03月19日
    浏览(23)
  • 【海贼王的数据航海】排序——概念|直接插入排序|希尔排序

    【海贼王的数据航海】排序——概念|直接插入排序|希尔排序

    目录 1 - 排序的概念及其运用 1.1 - 排序的概念 1.2 - 常见的排序算法 2 - 插入排序 2.1 - 基本思想 2.2 - 直接插入排序 2.2.1 - 代码实现 2.3 - 希尔排序(缩小增量排序) 2.3.1 - 代码实现 排序 ：所谓排序，就是使一串记录，按照其中的某个或某些的大小，递增或递减的排列起来的

    2024年03月25日
    浏览(29)
  • 【海贼王的数据航海】时间复杂度 | 空间复杂度

    【海贼王的数据航海】时间复杂度 | 空间复杂度

    目录 1 - 算法效率 1.1 - 如何衡量一个算法的好坏？ 1.2 - 算法的复杂度 2 - 时间复杂度 2.1 - 时间复杂度的概念 2.2 - 大O的渐进表示法 2.3 - 常见时间复杂度计算 3 - 空间复杂度 4 - 常见复杂度对比 对于以下斐波那契数列： 用递归实现斐波那契数列，看上去代码十分简洁，但简洁一

    2024年03月14日
    浏览(33)
  • 大学生bootstrap框架网页作业成品 web前端大作业期末源码 航海王html+jquery+bootstrap响应式网页制作模板 学生海贼王动漫bootstrap框架网站作品

    大学生bootstrap框架网页作业成品 web前端大作业期末源码 航海王html+jquery+bootstrap响应式网页制作模板 学生海贼王动漫bootstrap框架网站作品

    HTML实例网页代码, 本实例适合于初学HTML的同学。该实例里面有设置了css的样式设置，有div的样式格局，这个实例比较全面，有助于同学的学习,本文将介绍如何通过从头开始设计个人网站并将其转换为代码的过程来实践设计。 ⚽精彩专栏推荐👇🏻👇🏻👇🏻 ❤ 【作者主页

    2024年02月11日
    浏览(51)
  • 数据结构-链表结构-双向链表

    数据结构-链表结构-双向链表

    双向链表也叫双链表，与单向链表不同的是，每一个节点有三个区域组成：两个指针域，一个数据域 前一个指针域：存储前驱节点的内存地址 后一个指针域：存储后继节点的内存地址 数据域：存储节点数据 以下就是双向链表的最基本单位 节点的前指针域指向前驱，后指针

    2024年02月04日
    浏览(34)
  • 【数据结构】双向奔赴的爱恋 --- 双向链表

    【数据结构】双向奔赴的爱恋 --- 双向链表

    关注小庄 顿顿解馋๑ᵒᯅᵒ๑ 引言：上回我们讲解了单链表(单向不循环不带头链表)，我们可以发现他是存在一定缺陷的，比如尾删的时候需要遍历一遍链表，这会大大降低我们的性能，再比如对于链表中的一个结点我们是无法直接访问它的上一个结点，那有什么解决方法呢

    2024年04月08日
    浏览(82)
  • 数据结构双向链表

    数据结构双向链表

    Hello，好久不见，今天我们讲链表的双向链表，这是一个很厉害的链表，带头双向且循环，学了这个链表，你会发现顺序表的头插头删不再是一个麻烦问题，单链表的尾插尾删也变得简单起来了，那废话不多说，让我们开始我们的学习吧！ 首先我们要了解它的物理和逻辑结构

    2024年02月11日
    浏览(30)
  • 数据结构 - 双向链表

    数据结构 - 双向链表

    文章目录 目录 文章目录 前言 一、什么是双向链表? 双向链表有什么优势? 二、双向链表的设计和实现 1.设计思想 尾增 : 在链表的末尾添加新的元素  头插 : 在链表头部插入节点  删除 : 根据val的值删除节点  查找 : 根据索引的值查找并返回节点 总结 大家好,今天给大家讲解

    2024年02月09日
    浏览(26)
  • 数据结构-双向链表

    数据结构-双向链表

    在单链表那一篇博客中介绍了单链表和双向链表的优缺点，所以此篇博客直接分享怎样实现一个带头双向循环链表。 单链表博客： 首先我们需要写一个结构体，双向带头链表的话需要一个前驱指针prev和一个后驱指针next，前驱指针的作用是方便找尾节点，因为头节点的prev指

    2024年02月05日
    浏览(32)

  • 数据结构---双向链表

    单向链表：一块内存指向下一个内存。 单链表存在一些缺陷： 1.查找速度慢。 2.不能从后往前找。 3.找不到前驱。 链表的结构分为8种： 1.单向和双向 2.带头和不带头 带头的链表有一个带哨兵位的头结点，这个节点不存储有效数据。 好处 ：尾插更方便，不需要二级指针了，

    2024年02月02日
    浏览(38)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包