【数据结构/C语言】深入理解 双向链表

简介: 【数据结构/C语言】深入理解 双向链表

一、双向链表的基本概念

双向链表的简介

双向链表是一种常见的数据结构,与单向链表类似,但它允许我们从两个方向遍历链表:向前和向后。每个节点包含三个部分:一个数据元素和两个指针,一个指向链表中的前一个节点,另一个指向链表中的下一个节点。

一般情况下,我们所说的双向链表指的是带头节点,双向,循环链表,以下若无特殊说明,均代表此含义。

以下是常见的单链表与双链表的图示及区别

双向链表的特点

  • 双向遍历:由于每个节点都包含指向前一个节点和下一个节点的指针,因此我们可以从链表的任何一个节点开始,向前或向后遍历链表。
  • 插入和删除操作:在双向链表中插入或删除节点通常比单向链表更加高效,因为我们可以直接访问要插入或删除节点的前一个和/或后一个节点,从而避免了对链表的遍历。
  • 空间效率:与数组相比,双向链表在内存使用上更加灵活。链表可以在运行时动态地分配和释放内存,而不需要预先分配固定大小的内存块。

双向链表的优缺点

优点

  • 动态分配内存,空间效率高。
  • 插入和删除操作效率高,特别是当知道要操作节点的位置时。
  • 可以从两个方向遍历链表。

缺点

  • 相对于数组,链表在内存使用上可能不够紧凑,因为每个节点都需要额外的空间来存储指针。
  • 访问链表中特定位置的元素需要从头或尾开始遍历链表,这可能导致效率较低(尽管可以使用哈希表等数据结构来优化访问速度)。

二、双向链表的结构

双向链表节点的结构

双向链表中的每个节点通常包含以下部分:

  1. 数据元素:可以是任何类型的数据,如整数、浮点数、字符串或对象。
  2. prev 指针:指向前一个节点的指针。
  3. next 指针:指向下一个节点的指针。
typedef int LTDataType;//数据类型重定义,可以是任意数据类型
typedef struct ListNode//双向链表节点结构
{
  LTDataType data;//数据
  struct ListNode* prev;//指向前一个节点的指针
  struct ListNode* next;//指向下一个节点的指针
}LTNode;

双向链表的整体结构

相比单链表只有独立存在的每个节点,双向链表多了哨兵位节点,该节点作为头结点,不存储有效数据,只有指向第一个有效节点的next指针和指向尾节点的prev指针。

只要链表存在,哨兵位节点就存在

三、双向链表的实现方法

1.双向链表的初始化

双向链表的初始化也就是创建一个哨兵位节点,所以实现初始化之前需要先封装一个节点申请函数

单独封装的申请节点函数

  • 动态申请节点大小的空间
  • 判空
  • 通过形参接受的数据初始化节点数据部分
  • next指针和prev指针都指向自身(因为双向链表是循环链表)
  • 返回节点地址
LTNode* NewNode(LTDataType x)//申请节点
{
  LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
  if (newnode == NULL)
  {
    perror("NewNode\n");
    exit(1);
  }
  newnode->data = x;//根据参数初始化数据
  newnode->next = newnode->prev = newnode;//两个指针初始都指向自身
  return newnode;
}

双向链表初始化

  • 调用申请节点函数创建一个哨兵位节点,作为链表的头结点
  • 返回链表头结点地址

注意:

双向链表因为有哨兵位的存在,链表始终不为空,哨兵位节点不会被改变,所以不再需要传递地址,以及用二级指针接收。这一点区别于单链表实现

LTNode* LTInit()            //链表初始化
{
  LTNode* newnode = NewNode(-1);
  return newnode;
}

2.双向链表的头插

双向链表头插

  • 头插就是将新节点插入到哨兵位节点和第一个有效节点之间
  • 形参接收一个哨兵位地址和要插入的数据
  • 首先对哨兵位地址判空,判断链表结构是否正常
  • 申请新节点,存入要插入的数据
  • 接下来是移动指针
  • 一般情况下应当先调整新节点的指针,因为新节点指针调整不会影响到原链表:
  • 新节点prev指向哨兵位,next指向哨兵位的next所指向节点
  • 然后,调整第一个有效节点的prev指针,不再指向哨兵位而是指向新节点;调整哨兵位next指针,不再指向原来的第一个有效节点,而是指向新节点
  • 新节点插入完成

void LTPushFront(LTNode* phead, LTDataType x)//头插
{
  assert(phead);//判空
  LTNode* newnode = NewNode(x);//申请节点
 
  newnode->next = phead->next;//改变新节点指针指向
  newnode->prev = phead;
 
  phead->next->prev = newnode;//改变原链表相关节点指针指向
  phead->next = newnode;
 
}

3.双向链表的尾插

双向链表尾插

  • 尾插就是将新节点插入到原链表最后一个节点和哨兵位之间
  • 首先对哨兵位地址判空,判断链表结构是否正常
  • 申请新节点,存入要插入的数据
  • 调整指针:
  • 新节点next指向哨兵位节点,prev指向原链表最后一个有效节点(哨兵位prev所指向的节点)
  • 原链表最后一个有效节点的next指向新节点
  • 哨兵位prev指向新节点
  • 新节点尾差完成

void LTPushBack(LTNode* phead, LTDataType x)//尾插
{
  assert(phead);//判空
  LTNode* newnode = NewNode(x);//申请节点
 
  newnode->next = phead;//改变新节点指针指向
  newnode->prev = phead->prev;
 
  phead->prev->next = newnode;//改变原链表相关节点指针指向
  phead->prev = newnode;
}

4.双向链表的头删

双向链表头删

  • 头删就是将双向链表第一个有效节点删除
  • (头删的前提是链表至少存在一个有效节点)
  • 首先创建一个指针del指向要删除的节点(哨兵位节点next指向的节点)
  • 然后将第二个有效节点的prev指针指向哨兵位节点
  • 哨兵位节点的next指针指向第二个有效节点
  • 指针修改完成,此时第二个有效节点成为链表的第一个有效节点,释放del指向的节点
  • (如果删除之前链表只有一个节点,删除完之后只剩下一个哨兵位节点,两个指针都指向自己)

void LTPopFront(LTNode* phead)    //头删
{
  assert(phead && phead->next != phead);//判空
  LTNode* del = phead->next;//暂时存储要删除的节点
 
  del->next->prev = phead;//移动指针
  phead->next = del->next;
 
  free(del);//释放节点空间
  del = NULL;
}

5.双向链表的尾删

双向链表尾删

  • 尾删就是将双向链表的最后一个有效节点删除
  • (尾删的前提是至少存在一个有效节点)
  • 首先创建一个指针del指向要删除的节点(哨兵位prev指向节点)
  • 然后将倒数第二个节点的next指针指向哨兵位
  • 将哨兵位的prev指针指向倒数第二个节点
  • 指针修改完成,此时倒数第二个节点成为最后一个节点,释放del指向的节点
  • (如果删除之前链表只有一个节点,删除完之后只剩下一个哨兵位节点,两个指针都指向自己)

void LTPopBack(LTNode* phead)   //尾删
{
  assert(phead && phead->next != phead);//判空
  LTNode* del = phead->prev;//暂时存储要删除的节点
 
  del->prev->next = phead;//移动指针
  phead->prev = del->prev;
 
  free(del);//释放节点空间
  del = NULL;
}

6.查找节点

双向链表查找(根据数据查找节点)

  • 首先对哨兵位地址判空,否则可能对空地址解引用
  • 创建一个遍历链表的指针,从第一个有效节点开始,将节点数据与要查找的数据进行比对,如果相同返回节点地址
  • 出循环,说明未找到,返回NULL
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;
}

7.在指定位置之前插入节点

双向链表在指定位置之前插入节点:

  • 插入的前提是指定位置存在
  • 申请新节点,存入要插入的数据
  • 调整指针:
  • 临时创建一个指针prev指向指定位置节点的perv指向节点
  • 新节点next指针指向指定位置节点,prev指针指向prev节点
  • 然后再修改原链表指针:
  • 指定位置节点的prev指针指向新节点,prev节点的next指针指向新节点
  • 新节点插入完成
void LTInsert(LTNode* pos, LTDataType x)//在pos位置之前插入数据
{
  assert(pos);//判空
  LTNode* newnode = NewNode(x);//申请新节点
 
  newnode->next = pos;//改变新节点指针指向
  newnode->prev = pos->prev;
 
  pos->prev->next = newnode;//改变原链表相关节点指针指向
  pos->prev = newnode;
 
}

8.删除指定位置节点

双向链表删除指定位置节点

  • 删除指定节点的前提是该节点必须存在
  • 首先创建一个指针del指向要删除的节点
  • 然后将该节点的前一个结点的next指针指向它的后一个节点,后一个节点的prev指针指向他的前一个节点
  • 释放该节点
  • (如果删除之前链表只有一个节点,删除完之后只剩下一个哨兵位节点,两个指针都指向自己)

void LTErase(LTNode* pos)//删除指定位置节点
{
  assert(pos);//判空
  pos->next->prev = pos->prev;//改变要删除节点的前后节点指针指向
  pos->prev->next = pos->next;
 
  free(pos);
  pos = NULL;
 
}

9.打印链表数据

双向链表数据打印

  • 首先对地址判空,防止对空地址解引用
  • 创建一个遍历链表的指针,从第一个有效节点打印数据,然后向后移动,直到指针遍历到哨兵位
void LTPrint(LTNode* phead)  //链表数据打印
{
  assert(phead);//判空
  LTNode* pcur = phead->next;//遍历链表的指针
 
  while (pcur != phead)//打印数据
  {
    printf("%d->", pcur->data);
    pcur = pcur->next;
  }
  printf("\n");
}

10.双向链表销毁

双向链表的销毁

  • 从第一个有效节点开始,创建指针循环遍历链表:
  • 创建next指针临时保存下一个节点,释放本节点,遍历指针指向next节点
  • 循环至有效节点全部被释放
  • 然后将哨兵位节点释放,指针置空,销毁完成

注意:

为了与其他配套函数的参数保持一致,这里的参数本该用二级指针接收,却用一级指针接收。出函数后,需要手动将哨兵位指针置空

四、C语言实现代码及测试

DouSlist.h 双链表头文件

//DouSlist.h 双链表头文件
#define _CRT_SECURE_NO_WARNINGS 1
 
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
 
typedef int LTDataType;//数据类型重定义,可以是任意数据类型
typedef struct ListNode//双向链表节点结构
{
  LTDataType data;//数据
  struct ListNode* prev;//指向前一个节点的指针
  struct ListNode* next;//指向下一个节点的指针
}LTNode;
 
LTNode* NewNode(LTDataType x);//申请节点
LTNode* LTInit();             //链表初始化
 
void LTPushFront(LTNode* phead, LTDataType x);//头插
void LTPushBack(LTNode* phead, LTDataType x);//尾插
 
void LTPopBack(LTNode* phead);    //尾删
void LTPopFront(LTNode* phead);   //头删
 
 
LTNode* LTFind(LTNode* phead, LTDataType x);//查找节点
 
void LTInsert(LTNode* pos, LTDataType x);//在pos位置之后插入数据
void LTErase(LTNode* pos);//删除指定位置节点
 
void LTPrint(LTNode* phead);  //链表数据打印
void LTDestroy(LTNode* phead);//链表销毁

DouSList.c  双链表源文件

//DouSList.c  双链表源文件
#define _CRT_SECURE_NO_WARNINGS 1
#include"DouSList.h"
 
LTNode* NewNode(LTDataType x)//申请节点
{
  LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
  if (newnode == NULL)
  {
    perror("NewNode\n");
    exit(1);
  }
  newnode->data = x;//根据参数初始化数据
  newnode->next = newnode->prev = newnode;//两个指针初始都指向自身
  return newnode;
}
LTNode* LTInit()            //链表初始化
{
  LTNode* newnode = NewNode(-1);
  return newnode;
}
void LTPushFront(LTNode* phead, LTDataType x)//头插
{
  assert(phead);//判空
  LTNode* newnode = NewNode(x);//申请节点
 
  newnode->next = phead->next;//改变新节点指针指向
  newnode->prev = phead;
 
  phead->next->prev = newnode;//改变原链表相关节点指针指向
  phead->next = newnode;
 
}
void LTPushBack(LTNode* phead, LTDataType x)//尾插
{
  assert(phead);//判空
  LTNode* newnode = NewNode(x);//申请节点
 
  newnode->next = phead;//改变新节点指针指向
  newnode->prev = phead->prev;
 
  phead->prev->next = newnode;//改变原链表相关节点指针指向
  phead->prev = newnode;
}
 
 
void LTPopFront(LTNode* phead)    //头删
{
  assert(phead && phead->next != phead);//判空
  LTNode* del = phead->next;//暂时存储要删除的节点
 
  del->next->prev = phead;//移动指针
  phead->next = del->next;
 
  free(del);//释放节点空间
  del = NULL;
}
 
void LTPopBack(LTNode* phead)   //尾删
{
  assert(phead && phead->next != phead);//判空
  LTNode* del = phead->prev;//暂时存储要删除的节点
 
  del->prev->next = phead;//移动指针
  phead->prev = del->prev;
 
  free(del);//释放节点空间
  del = NULL;
}
 
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;
}
 
void LTInsert(LTNode* pos, LTDataType x)//在pos位置之前插入数据
{
  assert(pos);//判空
  LTNode* newnode = NewNode(x);//申请新节点
 
  newnode->next = pos;//改变新节点指针指向
  newnode->prev = pos->prev;
 
  pos->prev->next = newnode;//改变原链表相关节点指针指向
  pos->prev = newnode;
 
}
 
void LTErase(LTNode* pos)//删除指定位置节点
{
  assert(pos);//判空
  pos->next->prev = pos->prev;//改变要删除节点的前后节点指针指向
  pos->prev->next = pos->next;
 
  free(pos);
  pos = NULL;
 
}
 
void LTPrint(LTNode* phead)  //链表数据打印
{
  assert(phead);//判空
  LTNode* pcur = phead->next;//遍历链表的指针
 
  while (pcur != phead)//打印数据
  {
    printf("%d->", pcur->data);
    pcur = pcur->next;
  }
  printf("\n");
}
 
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;
 
}

test.c   测试文件及测试结果

//test.c   测试文件
#define _CRT_SECURE_NO_WARNINGS 1
#include"DouSList.h"
 
void test1()
{
  LTNode* plist = LTInit();       //链表初始化
  LTPushFront(plist,1 );//头插
  LTPushFront(plist,2 );//头插
  LTPrint(plist);  //链表数据打印
  LTPushBack(plist, 3);//尾插
  LTPushBack(plist, 4);//尾插
  LTPrint(plist);  //链表数据打印
 
  LTPopBack(plist);   //尾删
  LTPopFront(plist);    //头删
  LTPrint(plist);  //链表数据打印
 
  LTNode* pos=LTFind(plist, 3);//查找
  LTInsert(pos, 5);//在pos位置之后插入数据
  LTPrint(plist);  //链表数据打印
 
 
  LTErase(pos);//删除指定位置节点
  pos = NULL;
 
  LTPrint(plist);  //链表数据打印
 
  LTDestroy(plist);//链表销毁
  plist = NULL;
}
int main()
{
  test1();
  return 0;
}

五、双向链表的应用场景

双向链表在许多场景中都非常有用,包括:

  1. LRU 缓存淘汰策略:在操作系统和数据库等系统中,双向链表经常用于实现最近最少使用(LRU)缓存淘汰策略。当缓存满时,最久未使用的项(即链表尾部的项)将被删除。
  2. 双向队列:双向链表也可以用作双向队列(Deque),支持从队列的前端和后端添加和删除元素。
  3. 撤销/重做功能:在文本编辑器或图形编辑器中,双向链表可以用于实现撤销和重做功能。每当用户执行一个操作时,该操作可以作为一个节点添加到链表的前端。当用户选择撤销时,可以从链表的前端删除一个节点;当用户选择重做时,可以从链表的已删除节点列表中恢复一个节点。
相关文章
|
11月前
|
算法 数据处理 C语言
C语言中的位运算技巧,涵盖基本概念、应用场景、实用技巧及示例代码,并讨论了位运算的性能优势及其与其他数据结构和算法的结合
本文深入解析了C语言中的位运算技巧,涵盖基本概念、应用场景、实用技巧及示例代码,并讨论了位运算的性能优势及其与其他数据结构和算法的结合,旨在帮助读者掌握这一高效的数据处理方法。
409 1
|
8月前
|
存储 机器学习/深度学习 算法
C 408—《数据结构》算法题基础篇—链表(下)
408考研——《数据结构》算法题基础篇之链表(下)。
200 30
|
8月前
|
存储 算法 C语言
C 408—《数据结构》算法题基础篇—链表(上)
408考研——《数据结构》算法题基础篇之链表(上)。
313 25
|
8月前
|
定位技术 C语言
c语言及数据结构实现简单贪吃蛇小游戏
c语言及数据结构实现简单贪吃蛇小游戏
|
9月前
|
搜索推荐 C语言
数据结构(C语言)之对归并排序的介绍与理解
归并排序是一种基于分治策略的排序算法,通过递归将数组不断分割为子数组,直到每个子数组仅剩一个元素,再逐步合并这些有序的子数组以得到最终的有序数组。递归版本中,每次分割区间为[left, mid]和[mid+1, right],确保每两个区间内数据有序后进行合并。非递归版本则通过逐步增加gap值(初始为1),先对单个元素排序,再逐步扩大到更大的区间进行合并,直至整个数组有序。归并排序的时间复杂度为O(n*logn),空间复杂度为O(n),且具有稳定性,适用于普通排序及大文件排序场景。
|
9月前
|
机器学习/深度学习 存储 C++
【C++数据结构——线性表】单链表的基本运算(头歌实践教学平台习题)【合集】
本内容介绍了单链表的基本运算任务,涵盖线性表的基本概念、初始化、销毁、判定是否为空表、求长度、输出、求元素值、按元素值查找、插入和删除数据元素等操作。通过C++代码示例详细解释了顺序表和链表的实现方法,并提供了测试说明、通 - **任务描述**:实现单链表的基本运算。 - **相关知识**:包括线性表的概念、初始化、销毁、判断空表、求长度、输出、求元素值、查找、插入和删除等操作。 - **测试说明**:平台会对你编写的代码进行测试,提供测试输入和预期输出。 - **通关代码**:给出了完整的C++代码实现。 - **测试结果**:展示了测试通过后的预期输出结果。 开始你的任务吧,祝你成功!
337 5
|
10月前
|
数据库
数据结构中二叉树,哈希表,顺序表,链表的比较补充
二叉搜索树,哈希表,顺序表,链表的特点的比较
数据结构中二叉树,哈希表,顺序表,链表的比较补充
|
10月前
|
存储 算法 C语言
【C语言】深入浅出:C语言链表的全面解析
链表是一种重要的基础数据结构,适用于频繁的插入和删除操作。通过本篇详细讲解了单链表、双向链表和循环链表的概念和实现,以及各类常用操作的示例代码。掌握链表的使用对于理解更复杂的数据结构和算法具有重要意义。
2922 6
|
11月前
|
存储 缓存 算法
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
282 5
|
11月前
|
并行计算 算法 测试技术
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面,旨在通过综合策略提升程序性能,满足实际需求。
266 1