[数据结构]双链表详解

[数据结构]双链表详解

news/2025/2/23 15:18:11

目录

一、链表的分类

1. 单向或者双向

2. 带头或者不带头

3. 循环或者非循环

二、双向链表

1.双向链表内部定义

2.双向链表的初始化（void LTPrint(LTNode* phead);）

3.双向链表的销毁（void LTDataDestroy(LTNode* phead);）

4.双向链表的尾插（void LTPushBack(LTNode* phead, LTDataType x);）

5.判断链表是否为空（bool LTEmpty(LTNode* phead);）

6.双向链表的尾删（void LTPopBack(LTNode* phead);）

7.双向链表的头插（ void LTPushFront(LTNode* phead, LTDataType x); ）

8.双向链表的头删（void LTPopFront(LTNode* phead);）

9.双向链表的查找（LTNode* LTFind(LTNode* phead, LTDataType x);）

10.双向链表的删除（void LTErase(LTNode* pos);）

11.双向链表在pos位置之前插入一个值（void LTInsert(LTNode* pos,LTDataType x);）

三、双向链表的完整代码

List.h

List.c

test.c

四、顺序表和链表的对比

一、链表的分类

实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：

1. 单向或者双向

2. 带头或者不带头

带头的为哨兵位置头结点，特点：不存储有效数据优点：插入数据时不需要探空

3. 循环或者非循环

虽然有这么多的链表的结构，但是我们实际中最常用还是两种结构：

1. 无头单向非循环链表： 结构简单 ，一般不会单独用来存数据。实际中更多是作为 其他数据结

构的子结构 ，如哈希桶、图的邻接表等等。另外这种结构在 笔试面试 中出现很多。

2. 带头双向循环链表： 结构最复杂 ，一般用在单独存储数据。实际中使用的链表数据结构，都

是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带

来很多优势，实现反而简单了，后面我们代码实现了就知道了。

二、双向链表

1.双向链表内部定义

#pragma once
typedef int LTDataType;
typedef struct ListNode
{
       struct ListNode* next;
       struct ListNode* prev;
       LTDataType data;
}LTNode;

2.双向链表的初始化（void LTPrint(LTNode* phead);）

//双链表的初始化
LTNode* LTInit()
{
       LTNode* phead = BuyListNode(-1);
       phead->next = phead;
       phead->prev = phead;
       return phead;
}

3.双向链表的销毁（void LTDataDestroy(LTNode* phead);）

// 双链表的销毁
void LTDataDestroy(LTNode* phead) {
       assert(phead);  // 确保头节点不为空
       LTNode* cur = phead->next;  // 从第一个节点开始
       while (cur != phead) {      // 遍历链表，直到回到头节点
              LTNode* next = cur->next;  // 保存下一个节点
              free(cur);                 // 释放当前节点
              cur = next;                // 移动到下一个节点
       }
       free(phead);  // 释放头节点
       phead = NULL; // 将头节点指针置为 NULL（注意：这里只是局部修改，外部需要手动置空）
}

4.双向链表的尾插（void LTPushBack(LTNode* phead, LTDataType x);）

//双链表的尾插
void LTPushBack(LTNode* phead, LTDataType x)
{
       LTNode* newnode = BuyListNode(x);
       LTNode* tail = phead->prev;
       //phead           tail  newnode
       tail->next = newnode;
       newnode->prev = tail;
       newnode->next = phead;
       phead->prev = newnode;
       tail = tail->next;
}

这里不需要用二级指针，因为这个函数里面没有修改phead的值，因为有哨兵结点，那么就不需要考虑链表为空的情况，这里对比单链表的尾插：在单链表的尾插中如果链表为空那么就有一个这个操作：*pphead = newnode;这里修改了形参的值那么就必须传递二级指针

void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
       SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
       if (newnode == NULL)
       {
              perror("malloc fail");
       }
       newnode->data = x;
       newnode->Next = NULL;
       if (*pphead == NULL)
       {
              *pphead = newnode;
       }。
       else
       {
              //找尾
              SLTNode* tail = *pphead;
              while (tail->Next != NULL)
              {
                      tail = tail->Next;
              }
              tail->Next = newnode;
       
}

5.判断链表是否为空（bool LTEmpty(LTNode* phead);）

//判断链表是否为空
bool LTEmpty(LTNode* phead)
{
       assert(phead);
       return phead->next == phead;
       //等价于
       /*if (phead->next == phead)
       {
              return true;
       }
       else
       {
              return false;
       }*/
}

6.双向链表的尾删（void LTPopBack(LTNode* phead);）

//判断链表是否为空
bool LTEmpty(LTNode* phead)
{
       assert(phead);
       return phead->next == phead;
       //等价于
       /*if (phead->next == phead)
       {
              return true;
       }
       else
       {
              return false;
       }*/
}

7.双向链表的头插（ void LTPushFront(LTNode* phead, LTDataType x); ）

双链表的头插需要注意，不要一上来就phead->next=newnode newnode->pre=phead;这样就不能找到原来的第一个了

//双链表的头插
void LTPushFront(LTNode* phead, LTDataType x)
{
       assert(phead);
       LTNode* newnode = BuyListNode(x);
       newnode->next = phead->next;//newnode->next要指向d1，d1就是phead->next
       phead->next->prev = newnode;
       phead->next = newnode;
       newnode->prev = phead;
}

8.双向链表的头删（void LTPopFront(LTNode* phead);）

//双链表的头删
void LTPopFront(LTNode* phead)
{
       assert(phead);
       assert(!LTEmpty(phead));
       LTNode* head = phead->next;
       LTNode* headnext = head->next;
       phead->next = headnext;
       head->prev = phead;
       free(head);
       head = NULL;
}

9.双向链表的查找（LTNode* LTFind(LTNode* phead, LTDataType x);）

//双链表的查找
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;
}

10.双向链表的删除（void LTErase(LTNode* pos);）

//删除
void LTErase(LTNode* pos)
{
       //prev   pos   next
       assert(pos);
       LTNode* p = pos->prev;
       LTNode* n = pos->next;
       p->next = n;
       n->prev = p;
       free(pos);
       pos = NULL;//这行代码其实没有特别大的意义
}

11.双向链表在pos位置之前插入一个值（void LTInsert(LTNode* pos,LTDataType x);）

//在pos位置之前插入一个值
void LTInsert(LTNode* pos,LTDataType x)
{
       assert(pos);
       LTNode* prev = pos->next;
       LTNode* newnode = BuyListNode(x);
       //prev   newnode    pos
       prev->next = newnode;
       newnode->prev = prev;
       newnode->next = pos;
       pos->prev = newnode;
}

思考一个问题：有了Insert还需不需要头插？

答：不用 LTInsert（phead->next,x）就是头插，尾插也一样LTInsert（phead,x）

三、双向链表的完整代码

List.h

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<errno.h>
#include<stdbool.h>
typedef int LTDataType;
typedef struct ListNode
{
       struct ListNode* next;
       struct ListNode* prev;
       LTDataType data;
}LTNode;
//双链表的打印
void LTPrint(LTNode* phead);
//双链表的初始化
LTNode* LTInit();
//双链表的销毁
void LTDataDestroy(LTNode* phead);
//双链表的尾插
void LTPushBack(LTNode* phead, LTDataType x);
//双链表的尾删
void LTPopBack(LTNode* phead);
//判断链表是否为空
bool LTEmpty(LTNode* phead);
//双链表的头插
void LTPushFront(LTNode* phead, LTDataType x);
//双链表的头删
void LTPopFront(LTNode* phead);
//在pos位置之前插入一个值
void LTInsert(LTNode* pos,LTDataType x);
//删除
void LTErase(LTNode* pos);
//双链表的查找
LTNode* LTFind(LTNode* phead, LTDataType x);

List.c

#include"List.h"
LTNode* BuyListNode(LTDataType x)
{
       LTNode* node = (LTNode*)malloc(sizeof(LTNode));
       if (node == NULL)
       {
              perror("malloc fail");
              return NULL;
       }
       node->next = NULL;
       node->prev = NULL;
       node->data = x;
       return node;
}
//双链表的打印
void LTPrint(LTNode* phead)
{
       assert(phead);
       LTNode* cur = phead->next;
       while (cur != phead)
       {
              printf("%d<->", cur->data);
              cur = cur->next;
       }
}
//双链表的初始化
LTNode* LTInit()
{
       LTNode* phead = BuyListNode(-1);
       phead->next = phead;
       phead->prev = phead;
       return phead;
}
// 双链表的销毁
void LTDataDestroy(LTNode* phead) {
       assert(phead);  // 确保头节点不为空
       LTNode* cur = phead->next;  // 从第一个节点开始
       while (cur != phead) {      // 遍历链表，直到回到头节点
              LTNode* next = cur->next;  // 保存下一个节点
              free(cur);                 // 释放当前节点
              cur = next;                // 移动到下一个节点
       }
       free(phead);  // 释放头节点
       phead = NULL; // 将头节点指针置为 NULL（注意：这里只是局部修改，外部需要手动置空）
}
//双链表的尾插
void LTPushBack(LTNode* phead, LTDataType x)
{
       LTNode* newnode = BuyListNode(x);
       LTNode* tail = phead->prev;
       //phead           tail  newnode
       tail->next = newnode;
       newnode->prev = tail;
       newnode->next = phead;
       phead->prev = newnode;
       tail = tail->next;
       //这里不需要用二级指针
       // 用二级指针是因为要改变结构体里面的指针
       // 而双链表改的都是结构体里面的变量，用结构体的指针即可
       //
}
//判断链表是否为空
bool LTEmpty(LTNode* phead)
{
       assert(phead);
       return phead->next == phead;
       //等价于
       /*if (phead->next == phead)
       {
              return true;
       }
       else
       {
              return false;
       }*/
}
//双链表的尾删
void LTPopBack(LTNode* phead)
{
       //找到尾和尾的前一个，让尾的前一个称为新的尾，不需要遍历
       assert(phead);
       assert(!LTEmpty(phead));
       LTNode* tail=phead -> prev;
       LTNode* tailprev = tail->prev;
       
       tailprev->next = phead;
       phead->prev = tailprev;
       free(tail);
       tail = NULL;
}
//双链表的头插
void LTPushFront(LTNode* phead, LTDataType x)
{
       //双链表的头插需要注意，不要一上来就phead->next=newnode  newnode->pre=phead;这样就不能找到原来的第一个了
       assert(phead);
       LTNode* newnode = BuyListNode(x);
       newnode->next = phead->next;//newnode->next要指向d1，d1就是phead->next
       phead->next->prev = newnode;
       phead->next = newnode;
       newnode->prev = phead;
}
//双链表的头删
void LTPopFront(LTNode* phead)
{
       assert(phead);
       assert(!LTEmpty(phead));
       LTNode* head = phead->next;
       LTNode* headnext = head->next;
       phead->next = headnext;
       head->prev = phead;
       free(head);
       head = NULL;
}
//在pos位置之前插入一个值
void LTInsert(LTNode* pos,LTDataType x)
{
       assert(pos);
       LTNode* prev = pos->next;
       LTNode* newnode = BuyListNode(x);
       //prev   newnode    pos
       prev->next = newnode;
       newnode->prev = prev;
       newnode->next = pos;
       pos->prev = newnode;
}//思考一个问题：有了Insert还需不需要头插？答：不用 LTInsert（phead->next,x）就是头插，尾插也一样LTInsert（phead,x）
//删除
void LTErase(LTNode* pos)
{
       //prev   pos   next
       assert(pos);
       LTNode* p = pos->prev;
       LTNode* n = pos->next;
       p->next = n;
       n->prev = p;
       free(pos);
       pos = NULL;//这行代码其实没有特别大的意义
}
//双链表的查找
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;
}

test.c

#include"List.h"
void TestList1()
{
       LTNode* plist = LTInit();
       //尾插测试
       LTPushBack(plist,1);
       LTPushBack(plist,2);
       LTPushBack(plist,3);
       LTPushBack(plist,4);
       LTPrint(plist);
       //尾删测试
       printf("\n");
       LTPopBack(plist);
       LTPopBack(plist);
       LTPrint(plist);
       //头插测试
       printf("\n");
       LTPushFront(plist,5);
       LTPushFront(plist,8);
       LTPrint(plist);
       //头删测试
       printf("\n");
       LTPopFront(plist);
       LTPrint(plist);
}
int main()
{
       TestList1();
       return 0;
}

四、顺序表和链表的对比

顺序表和链表的对比
不同点	顺序表	链表
存储空间上	物理上一定连续	逻辑上连续，但物理上不一定连续
随机访问	支持O(n)	不支持O(n)
任意位置插入或者删除元素	可能需要搬移元素，效率低 O(N)	只需修改指针指向
插入	动态顺序表，空间不够时需要扩容	没有容量的概念
应用场景	元素高效存储 + 频繁访问	任意位置插入和删除频繁
缓存利用率	高	低

http://www.niftyadmin.cn/n/5863522.html

相关文章

Day9 25/2/22 SAT

Day9 25/2/22 SAT

【一周刷爆LeetCode，算法大神左神（左程云）耗时100天打造算法与数据结构基础到高级全家桶教程，直击BTAJ等一线大厂必问算法面试题真题详解（马士兵）】https://www.bilibili.com/video/BV13g41157hK?p4&v…

阅读更多...

MTK-Android13-包安装器PackageInstaller 静默安装实现

MTK-Android13-包安装器PackageInstaller 静默安装实现

目的我们最终是为了搞明白安装的整个流程。一方面通过安卓系统自带的包安装器来了解PMS 安装流程；另一方面熟悉框架层Framework 针对Android apk 安装流程。前两篇文章分析了PackagerInstaller 安装流程。 Android13-包安装器PackageInstaller-之apk安装跳转 An…

阅读更多...

C++：dfs，bfs各两则

C++：dfs，bfs各两则

1.木棒 167. 木棒 - AcWing题库乔治拿来一组等长的木棒，将它们随机地砍断，使得每一节木棍的长度都不超过 5050 个长度单位。然后他又想把这些木棍恢复到为裁截前的状态，但忘记了初始时有多少木棒以及木棒的初始长度。请你设计一个程序…

阅读更多...

力扣-贪心-376 摆动序列

力扣-贪心-376 摆动序列

思路记录前一个差值和后一个差值，需要分析很多情况只有在发生波动的时候才更新差值——单调中有平坡前一个差值0时也更新差值——平坡留下最左边元素最后一个元素不记录.默认从最后一个有坡度代码 class Solution { public:int wiggleMaxLength(vector<in…

阅读更多...

企业微信第三方应用开发025_企微通讯录组件使用04_vue中使用ww-open-data通讯录展示组件---企业微信开发027

企业微信第三方应用开发025_企微通讯录组件使用04_vue中使用ww-open-data通讯录展示组件---企业微信开发027

前面已经调试通了,已经成功了,这里只是给出一个例子,来实现,对ww-open-data的使用在vue中使用. 首先在: <template><div><el-dialog:close-on-click-modal="false"title="新增员工活码":type="type":visible.sync="dial…

阅读更多...

如何有效判断与排查Java GC问题

如何有效判断与排查Java GC问题

干货分享，感谢您的阅读！ 在现代Java应用中，垃圾回收（GC）是一个不可忽视的重要环节。尽管GC自动管理内存，避免了手动释放资源的麻烦，但它带来的性能开销却常常困扰开发者。从GC暂停时间到吞吐量…

阅读更多...

计算机网络-面试总结

计算机网络-面试总结

计算机网络从输入一个URL到页面加载完成的过程整体流程 DNS查询过程SSL四次握手HTTP 的长连接与短连接 HTTP 的 GET 和 POST 区别浏览器访问资源没有响应，怎么排查? OSI七层参考模型 TCP/IP四层参考模型比较 TCP/IP 参考模型与 OSI 参考模型 TCP三次握手&四…

阅读更多...

Python 高级数据结构操作全解析：从理论到实践

Python 高级数据结构操作全解析：从理论到实践

Python 高级数据结构操作全解析：从理论到实践本文深入剖析 Python 高级数据结构，通过丰富的代码示例、形象的配图，详细讲解集合、字典、堆、队列等数据结构的操作，同时拓展相关知识，帮助读者深入掌握 Python 编程核心…

阅读更多...

最新文章