网站导航
> 技术文档 > 数据结构之双链表(超详解)_双链表结构详解

数据结构之双链表(超详解)_双链表结构详解

网友: 技术文档 2025-07-30 12:09:18

在这里插入图片描述

在这里插入图片描述

文章目录

  • 链表分类
  • 双向链表
    • 概念
    • 结构
    • 创建头节点
  • 尾插、头插
    • 尾插
    • 头插
  • 尾删、头删
    • 尾删
    • 头删
  • 指定位置插入、删除结点
    • 指定位置插入结点
    • 指定位置删除结点
  • 查找结点
    • 链表打印
  • 双链表销毁
  • 双链表实现

链表分类

链表总共有八种结构如下。
数据结构之双链表(超详解)_双链表结构详解
数据结构之双链表(超详解)_双链表结构详解
在众多链表结构中，实际中最常用的有这两种结构：单链表和双向带头循环链表(即双链表)。

  1. 无头单向非循环链表：结构简单，⼀般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。
  2. 带头双向循环链表：结构最复杂，⼀般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势。(并且掌握如上两种数据结构的实现，其他种类的链表也能够实现)

双向链表

概念

数据结构之双链表(超详解)_双链表结构详解
这里的head充当什么作用呢？
带头链表里的头结点，实际为“哨兵位”，哨兵位结点不存储任何有效元素，只是站在这里\"放哨的\"。

结构

根据双链表概念，定义结构两个指针分别指向下一个结点和前一个结点的地址，并且每一个结点都能存储数据data。
数据结构之双链表(超详解)_双链表结构详解

申请结点

数据结构之双链表(超详解)_双链表结构详解

创建头节点

根据概念创建一个头结点起到\"放哨\"的作用，这个结点可随意给值。
为什么用一级指针接收呢？
保证哨兵位节点不能被删除(若被删除则不是双链表)，节点的地址也不能发生改变，因此传一级最合适。
数据结构之双链表(超详解)_双链表结构详解

尾插、头插

尾插

首先，通过函数创建一个新节点，并将其数据域设置为输入的值x，得到新节点的指newnode。

设置新结点的指针以插入到尾部。由于这是一个循环链表，尾节点的next指向头节点，所以将新节点newnode的prev指针指向前一个结点。

更新原链表尾节点的指针，使其next指针指向新节点newnode，这样新节点就被正确地链接到链表的末尾。

最后，调整原头节点phead的prev指针，使其指向新节点newnode，确保链表的循环特性仍然保持，即尾节点的next始终指向头节点。

数据结构之双链表(超详解)_双链表结构详解

头插

头插与尾插的方法类似。
数据结构之双链表(超详解)_双链表结构详解

尾删、头删

尾删

  1. 保证双链表有效(即至少有一个哨兵位)。
  2. 定义结点del保存尾结点，让尾结点的前一个结点的next指向头结点。
  3. 头结点指向del的前一个结点。
  4. 释放尾结点del。
    数据结构之双链表(超详解)_双链表结构详解
    数据结构之双链表(超详解)_双链表结构详解

头删

头删与尾删的方法类似。
数据结构之双链表(超详解)_双链表结构详解

指定位置插入、删除结点

指定位置插入结点

  1. 指向结点是否有效，若无效则断言。
  2. 创建新结点，newnode的next指向未更新链表指定位置的下一个结点；newnode的prev指向指定结点。
  3. 未更新链表指定位置的下一个结点指向newnode结点；指定结点指向newnode结点。
    数据结构之双链表(超详解)_双链表结构详解
    数据结构之双链表(超详解)_双链表结构详解

指定位置删除结点

删除指定结点，想要形参的改变影响到实参，那么传二级指针不是更好吗？
事实的确如此，那么我们为什么在这里是传一级指针呢？
目的是为了保证接口一致性。可以发现，我们前面函数的实现大部分都是通过传一级指针实现双链表功能，如果这里突然传二级指针会造成疑惑。
需要注意的是：删除指定结点后，由于形参不能改变实参，因此需要我们手动置指定结点为NULL。
数据结构之双链表(超详解)_双链表结构详解

查找结点

和单链表一样，我们只需要遍历原链表查找结点，若没找到则返回NULL。
数据结构之双链表(超详解)_双链表结构详解

链表打印

数据结构之双链表(超详解)_双链表结构详解

双链表销毁

  1. 定义pcur指向头结点的下一个结点，并遍历双链表。
  2. 每次释放pcur结点，并让pcur指向下一个结点，直到pcur与头结点phead相遇为止。
  3. 为了保证接口的一致性，这里同样采用传一级指针，需要手动置双链表的头结点为NULL。
    数据结构之双链表(超详解)_双链表结构详解

双链表实现

List.h 

#define _CRT_SECURE_NO_WARNINGS 1#pragma once#include#include#includetypedef int LTDataType;//定义双向链表节点的结构typedef struct ListNode{LTDataType data;struct ListNode* next;struct ListNode* prev;}LTNode;//声明双向链表中提供的方法//初始化//void LTInit(LTNode** phead);LTNode* LTInit();//打印双链表void LTPrint(LTNode* phead);//哨兵位节点不能被删除，节点的地址也不能发生改变，因此传一级最合适//尾插void LTPushBack(LTNode* phead, LTDataType x);//插入数据之前，，链表必须初始化到只有一个头结点的情况//头插void LTPushFront(LTNode* phead, LTDataType x);//尾删void LTPopBack(LTNode* phead);//头删void LTPopFront(LTNode* phead);//在pos位置之后插入数据void LTInsert(LTNode* pos, LTDataType x);//删除pos节点void LTErase(LTNode* pos);//查找节点LTNode* LTFind(LTNode* phead, LTDataType x);//销毁节点void LTDesTroy(LTNode* phead);

List.c 

#define _CRT_SECURE_NO_WARNINGS 1#include\"List.h\"//申请节点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;}//初始化LTNode* LTInit(){//创建头结点//LTNode* phead = (LTNode*)malloc(sizeof(LTNode));//phead->data = -1;//phead->next = phead->prev = phead;//给双向链表创建一个哨兵位LTNode *phead = LTBuyNode(-1);}//打印双链表void LTPrint(LTNode* phead){assert(phead);LTNode* pcur = phead->next;while (pcur != phead){printf(\"%d->\", pcur->data);pcur = pcur->next;}printf(\"\\n\");}//尾插void LTPushBack(LTNode* phead, LTDataType x){assert(phead);LTNode* newnode = LTBuyNode(x);//phead newnode phead->prevnewnode->prev = phead->prev;newnode->next = phead;phead->prev->next = newnode;phead->prev = newnode;}//头插void LTPushFront(LTNode* phead, LTDataType x){assert(phead);LTNode* newnode = LTBuyNode(x);//phead newnode prev->nextnewnode->prev = phead;newnode->next = phead->next;phead->next->prev = newnode;phead->next = newnode;}//尾删void LTPopBack(LTNode* phead){//链表必须有效且链表不能为空(只有一个哨兵位)assert(phead && phead->next != phead);//phead phead->prev->prev phead->prev//phead del->prev del 让del=phead->prevLTNode* del = phead->prev;del->prev->next = phead;phead->prev = del->prev;//释放del节点free(del);del = NULL;}//头删void LTPopFront(LTNode* phead){assert(phead && phead->next != phead);//phead phead->next phead->next->next//phead del del->next 让del=phead->nextLTNode* del = phead->next;phead->next = del->next;del->next->prev = phead;//释放del节点free(del);del = NULL;}//在pos位置之后插入数据void LTInsert(LTNode* pos, LTDataType x){assert(pos);LTNode* newnode = LTBuyNode(x);//pos newnode pos->nextnewnode->next = pos->next;newnode->prev = pos;pos->next->prev = newnode;pos->next = newnode;}//删除pos节点void LTErase(LTNode* pos)//二级指针更好{assert(pos);//pos->prev pos pos->nextpos->next->prev = pos->prev;pos->prev->next = pos->next;free(pos);pos = 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 LTDesTroy(LTNode* phead){assert(phead);LTNode* pcur = phead->next;while (pcur != phead){LTNode* next = pcur->next;free(pcur);pcur = next;}//此时pcur指向phead,而phead未被销毁free(phead);phead = NULL;}

test.c 

#define _CRT_SECURE_NO_WARNINGS 1#include\"List.h\"void ListTest(){//LTNode* plist = NULL;//LTInit(&plist);LTNode* plist = LTInit();LTPushBack(plist, 1);LTPushBack(plist, 2);LTPushBack(plist, 3);LTPushFront(plist, 4);LTPrint(plist);LTPopBack(plist);LTPrint(plist);LTNode* find = LTFind(plist, 1);//if (find == NULL)//{//printf(\"没有找到\\n\");//}//else {//printf(\"找到了\\n\");//}LTInsert(find, 4);LTPrint(plist);LTErase(find);//不传二级(保持接口一致性)find = NULL;LTPrint(plist);LTDesTroy(plist);plist = NULL;}int main(){ListTest();return 0;}

在这里插入图片描述

在这里插入图片描述

网络标签：

相关问题