【探索数据结构】线性表之双链表

2024-05-27 03:20
文章标签 数据结构 探索 线性表 双链

本文主要是介绍【探索数据结构】线性表之双链表，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

🎉🎉🎉欢迎莅临我的博客空间，我是池央，一个对C++和数据结构怀有无限热忱的探索者。🙌

🌸🌸🌸这里是我分享C/C++编程、数据结构应用的乐园✨

🎈🎈🎈期待与你一同在编程的海洋中遨游，探索未知的技术奥秘💞

📝专栏指路:

📘【C++】专栏：深入解析C++的奥秘，分享编程技巧与实践。

📘【数据结构】专栏：探索数据结构的魅力，助你提升编程能力。

前言

之前我们已经探索了顺序表和单链表我们继续一起来探索逻辑结构里面的线性结构。线性表在逻辑结构上是连续的，线性表中双链表（本篇主角）在物理结构上是不连续的。

文章重点介绍:带头双向循环链表

一、双链表

1.概念

双链表，也叫双向链表，是链表的一种特殊形式。在双链表中，每个数据节点都有两个指针，一个指向前一个节点（前驱节点），另一个指向后一个节点（后继节点）。这种结构使得从双链表中的任意一个节点开始，都可以很方便地访问它的前驱节点和后继节点。

2.分类

（1）按不同属性分

  • 带头节点的双链表：这种双链表在第一个数据节点之前有一个头结点。头结点是为了操作的统一和方便而设立的，放在第一元素的结点之前，其数据域一般无意义（也可存放链表的长度）。有了头结点，对在第一元素结点前插入结点和删除第一结点，其操作与其它结点的操作就统一了。
  • 不带头节点的双链表：与带头结点的双链表相反，这种链表没有头结点，直接从第一个数据节点开始。

（2）按循环性分

  • 双向循环链表：在双向链表的基础上，将头结点的后驱指针指向尾节点，尾节点的前驱指针指向头结点，从而形成一个双向环。
  • 双向非循环链表：这是标准的双向链表，没有形成一个环，只是简单地通过前驱和后继指针连接各个节点。

3.链表结构

typedef int LTDataType;
typedef struct LTNode LTNode;
struct LTNode
{LTDataType data;//数据LTNode* prev;//前驱指针LTNode* next;//后继指针
};

二、对双链表的操作

0.创建节点

//创建节点
LTNode* LTBuyNode(LTDataType x)
{LTNode* node = (LTNode*)malloc(sizeof(LTNode));if (node == NULL){perror("malloc fail!");exit(1);}node->data = x;node->next = node->prev = node;//不能置为空，都要指向自己return node;
}

1.初始化

后续对链表的操作都是不需要改变头结点的，哨兵位节点不能被删除，节点的地址，也不能发生改变只需传一级指针。为了保持接口的一致性。我们没有在初始化方法中选择传二级指针的方式实现

// 初始化
LTNode* LTInit()
{LTNode* phead = LTBuyNode(-1);return phead;
}

a3a432f8c86347a58ca032d1f485207d.png

2.打印

// 打印
void LTPrint(LTNode* phead)
{//从第一个有效节点遍历LTNode* pcur = phead->next;while (pcur != phead){printf("%d->", pcur->data);pcur = pcur->next;}printf("\n");
}

3.尾插

5a93f6ba31674491a04c3b29d8f41e5f.png

只有头结点时的尾插：

54509d768a324af4a387a3b1fb464425.png

// 尾插
void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);//phead phead->prev phead->nextLTNode* newnode = LTBuyNode(x);//先改变新节点的指针指向不影响原链表newnode->prev = phead->prev;newnode->next = phead;//不可以调换下面两句顺序，否则会找不到原链表的尾结点phead->prev->next = newnode;phead->prev = newnode;
}

4.头插

1948a25fe63a4d8c9e237272adf4fdff.png

// 头插
void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);//phead phead->next LTNode* newnode = LTBuyNode(x);newnode->next = phead->next;newnode->prev = phead;//尽量不要调换下面两句顺序phead->next->prev = newnode;phead->next = newnode;
}

790b4cb260344d90bacbf1549363339a.png

5.尾删

1efd723dd7134570835dfeb5ceffba02.png

// 尾删
void LTDelBack(LTNode* phead)
{assert(phead&&phead->next);//链表不能为空//phead  phead->prev//把要删除的节点先存起来以防找不到他的前一个节点LTNode* del = phead->prev;del->prev->next = phead;phead->prev = del->prev;free(del);del = NULL;
}

6.头删

639c4cff529f42e8917aa85221262988.png

// 头删
void LTDelFront(LTNode* phead)
{assert(phead && phead->next);//链表不能为空//把要删除的节点先存起来以防找不到他的后一个节点LTNode* del = phead->next;del->next->prev = phead;phead->next = del->next;free(del);del = NULL;
}

7.查找

LTNode* LTFind(LTNode* phead, LTDataType x)
{assert(phead);//从第一个有效节点遍历LTNode* pcur = phead->next;while (pcur != phead){if (pcur->data == x){return pcur;}pcur = pcur->next;}return NULL;
}

8.在指定位置之后插入数据

9e9aaa6d63c345648d51464be4357ba5.png

// 指定位置之后插入
void LTPushPos(LTNode* pos, LTDataType x)
{assert(pos);//pos->next pos LTNode* newnode = LTBuyNode(x);//先改变新节点的指针指向不影响原链表newnode->prev = pos;newnode->next = pos->next;pos->next->prev = newnode;pos->next = newnode;
}

9.删除指定节点

pos理论上来说不能为phead，但是没有参数phead，无法增加校验

9d31adf4092a4ca6bd0fce646f3973c7.png

// 删除指定节点
void LTErase(LTNode* pos)
{assert(pos);//pos->next pos->prevpos->prev->next = pos->next;pos->next->prev = pos->prev;free(pos);pos = NULL;
}

10.销毁链表

// 销毁
void LTDestroy(LTNode* phead)
{assert(phead);//从第一个有效节点遍历LTNode* pcur = phead->next;while (pcur != phead){//先把要删除节点的下一个节点存起来//不然要删除后续节点无法被找到LTNode* next = pcur->next;free(pcur);pcur = next;}//把哨兵位置为空free(phead);phead = NULL;
}

三、测试（仅供参考）

#include"List.h"
void test01()
{LTNode* plist = LTInit();//尾插LTPushBack(plist, 3);LTPushBack(plist, 2);LTPushBack(plist, 1);LTPrint(plist);//头插LTPushFront(plist, 4);LTPushFront(plist, 5);LTPushFront(plist, 6);LTPrint(plist);//尾删LTDelBack(plist);LTPrint(plist);//头删LTDelFront(plist);LTPrint(plist);LTNode* find = LTFind(plist, 5);if (find == NULL){printf("没有找到\n");}else{printf("找到了\n");}/*LTErase(find);LTPrint(plist);*/LTPushPos(find, 10);LTPrint(plist);LTDestroy(plist);//为保持接口一致性没有传二级指针//需要手动把实参置为空plist = NULL;
}
int main()
{test01();return 0;
}

四、双链表的主要应用

1.双向遍历

当需要频繁地在链表中向前和向后移动时，双链表非常有用。与单链表只能从头节点开始遍历不同，双链表可以从任何节点开始向前或向后遍历。

2.实现LRU（最近最少使用）缓存

LRU缓存策略常用于操作系统、数据库和缓存系统中，用于确定哪些数据应当被移除或替换，以便为新的数据腾出空间。在LRU缓存中，最近最少使用的数据项会被移除。使用双链表可以方便地将最近访问的节点移到链表的前端，并在需要时从链表的后端移除节点。

3.实现双向队列（Deque）

双向队列是一种具有队列和栈的性质的数据结构，支持从两端插入和删除元素。使用双链表可以轻松地实现这样的数据结构。

4.撤销和重做功能

在许多文本编辑器、图形编辑器和应用程序中，用户可能需要撤销或重做之前的操作。使用双链表可以存储用户的操作历史，并允许用户向前或向后遍历这些操作。

5.文件系统的元数据管理

在文件系统中，文件和目录的元数据（如名称、大小、修改日期等）通常存储在链表中。由于文件系统需要支持删除和插入操作，并且可能需要从任意位置开始遍历，因此双链表是一个合适的选择。

6.网络协议中的数据传输

在某些网络协议中，数据需要在不同的节点之间传输，并且可能需要在传输过程中进行插入或删除操作。双链表可以方便地实现这样的数据传输机制。

7.内存管理

在某些操作系统和内存管理系统中，双链表被用于跟踪和管理内存块。例如，在内存分配和回收过程中，双链表可以用于记录哪些内存块是可用的，哪些是被占用的。

8.范围查询

在某些应用场景中，可能需要查找位于某个范围内的所有元素。使用双链表可以方便地实现这样的范围查询操作，因为可以从任意节点开始向前或向后遍历链表。

下回预告：栈

持续更新中...

敬请期待

这篇关于【探索数据结构】线性表之双链表的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1006381。

相关文章

深入探索协同过滤：从原理到推荐模块案例

深入探索协同过滤：从原理到推荐模块案例

文章目录 前言一、协同过滤1. 基于用户的协同过滤（UserCF）2. 基于物品的协同过滤（ItemCF）3. 相似度计算方法 二、相似度计算方法1. 欧氏距离2. 皮尔逊相关系数3. 杰卡德相似系数4. 余弦相似度 三、推荐模块案例1.基于文章的协同过滤推荐功能2.基于用户的协同过滤推荐功能 前言     在信息过载的时代，推荐系统成为连接用户与内容的桥梁。本文聚焦于
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

上篇：6.1.数据结构-c/c++模拟实现堆上篇（向下，上调整算法，建堆，增删数据）-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小)： 2.2 C语言代码（手写堆） 2.3 C++代码（使用优先级队列 priority_queue）
阅读更多...
AI(文生语音)-TTS 技术线路探索学习:从拼接式参数化方法到Tacotron端到端输出

AI(文生语音)-TTS 技术线路探索学习:从拼接式参数化方法到Tacotron端到端输出

AI(文生语音)-TTS 技术线路探索学习:从拼接式参数化方法到Tacotron端到端输出 在数字化时代，文本到语音（Text-to-Speech, TTS）技术已成为人机交互的关键桥梁，无论是为视障人士提供辅助阅读，还是为智能助手注入声音的灵魂，TTS 技术都扮演着至关重要的角色。从最初的拼接式方法到参数化技术，再到现今的深度学习解决方案，TTS 技术经历了一段长足的进步。这篇文章将带您穿越时
阅读更多...
《数据结构（C语言版）第二版》第八章-排序（8.3-交换排序、8.4-选择排序）

《数据结构（C语言版）第二版》第八章-排序（8.3-交换排序、8.4-选择排序）

8.3 交换排序 8.3.1 冒泡排序 【算法特点】 (1) 稳定排序。 (2) 可用于链式存储结构。 (3) 移动记录次数较多，算法平均时间性能比直接插入排序差。当初始记录无序，n较大时， 此算法不宜采用。 #include <stdio.h>#include <stdlib.h>#define MAXSIZE 26typedef int KeyType;typedef char In
阅读更多...
轻松录制每一刻：探索2024年免费高清录屏应用

轻松录制每一刻：探索2024年免费高清录屏应用

你不会还在用一些社交工具来录屏吧？现在的市面上有不少免费录屏的软件了。别看如软件是免费的，它的功能比起社交工具的录屏功能来说全面的多。这次我就分享几款我用过的录屏工具。 1.福晰录屏大师 链接直达：https://www.foxitsoftware.cn/REC/  这个软件的操作方式非常简单，打开软件之后从界面设计就能看出来这个软件操作的便捷性。界面的设计简单明了基本一打眼你就会轻松驾驭啦
阅读更多...
深入探索嵌入式 Linux

深入探索嵌入式 Linux

摘要：本文深入探究嵌入式 Linux。首先回顾其发展历程，从早期尝试到克服诸多困难逐渐成熟。接着阐述其体系结构，涵盖硬件、内核、文件系统和应用层。开发环境方面包括交叉编译工具链、调试工具和集成开发环境。在应用领域，广泛应用于消费电子、工业控制、汽车电子和智能家居等领域。关键技术有内核裁剪与优化、设备驱动程序开发、实时性增强和电源管理等。最后展望其未来发展趋势，如与物联网融合、人工智能应用、安全性与
阅读更多...
【408数据结构】散列 （哈希）知识点集合复习考点题目

【408数据结构】散列 （哈希）知识点集合复习考点题目

苏泽  “弃工从研”的路上很孤独，于是我记下了些许笔记相伴，希望能够帮助到大家    知识点 1. 散列查找 散列查找是一种高效的查找方法，它通过散列函数将关键字映射到数组的一个位置，从而实现快速查找。这种方法的时间复杂度平均为(
阅读更多...
浙大数据结构：树的定义与操作

浙大数据结构：树的定义与操作

四种遍历 #include<iostream>#include<queue>using namespace std;typedef struct treenode *BinTree;typedef BinTree position;typedef int ElementType;struct treenode{ElementType data;BinTree left;BinTre
阅读更多...
Python 内置的一些数据结构

Python 内置的一些数据结构

文章目录 1. 列表 (List)2. 元组 (Tuple)3. 字典 (Dictionary)4. 集合 (Set)5. 字符串 (String) Python 提供了几种内置的数据结构来存储和操作数据，每种都有其独特的特点和用途。下面是一些常用的数据结构及其简要说明： 1. 列表 (List) 列表是一种可变的有序集合，可以存放任意类型的数据。列表中的元素可以通过索
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2