AI 助理
备案控制台
开发者社区 云计算 文章 正文

双向链表专题

2024-06-20 80
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 双向链表专题


1. 双向链表的结构

注意：

这⾥的“带头”跟前面我们说的“头节点”是两个概念，带头链表里的头节点，实际为“哨兵位”，哨兵位节点不存储任何有效元素，只是站在这里“放哨的”。

“哨兵位”存在的意义：遍历循环链表避免死循环。

2. 双向链表的实现

  1. 定义双向链表中节点的结构
//定义双向链表中节点的结构
typedef int LTDataType;
typedef struct ListNode
{
  LTDataType data;
  struct ListNode* prev;
  struct ListNode* next;
}LTNode;
  1. 初始化

注意，双向链表是带有哨兵位的，插入数据之前链表中必须要先初始化一个哨兵位

void LTInit(LTNode** pphead)
{
  *pphead = (LTNode*)malloc(sizeof(LTNode));
  if (NULL == *pphead)
  {
    perror("malloc fail!");
    exit(1);
  }
  (*pphead)->data = -1;
  (*pphead)->next = (*pphead)->prev = *pphead;
}

也可以这样写：

  1. 尾插

概念： 当链表中只有哨兵位节点的时候，我们称该链表为空链表；即哨兵位是不能删除的。

不需要改变哨兵位，则不需要传二级指针；如果需要修改哨兵位的话，则传二级指针。

LTNode* LTBuyNode(LTDataType x)
{
  LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
  if (NULL == newnode)
  {
    perror("malloc fail!");
    exit(1);
  }
  newnode->data = x;
  newnode->next = newnode->prev = newnode;
  return newnode;
}
//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{
  assert(phead);
  LTNode* newnode = LTBuyNode(x);
  //phead phead->prev(ptail) newnode
  newnode->next = phead;
  newnode->prev = phead->prev;
  phead->prev->next = newnode;
  phead->prev = newnode;
}

因为写了申请新节点的函数，所以上面的初始化代码可以优化：

LTNode* LTInit()
{
  LTNode* phead = LTBuyNode(-1);
  return phead;
}
  1. 打印
void LTPrint(LTNode* phead)
{
  //phead不能为空
  assert(phead);
  LTNode* pcur = phead->next;
  while (pcur != phead)
  {
    printf("%d->", pcur->data);
    pcur = pcur->next;
  }
  printf("\n");
}
  1. 头插

//头插
void LTPushFront(LTNode* phead, LTDataType x)
{
  assert(phead);
  LTNode* newnode = LTBuyNode(x);
  //phead newnode phead->next
  newnode->next = phead->next;
  newnode->prev = phead;
  phead->next->prev = newnode;
  phead->next = newnode;
}
  1. 尾删

//尾删
void LTPopBack(LTNode* phead)
{
  assert(phead);
  //链表为空：只有一个哨兵位节点
  assert(phead->next != phead);//若哨兵位节点的next指针或者prev指针指向的是自己，说明当前链表为空
  LTNode* del = phead->prev;
  LTNode* prev = del->prev;
  prev->next = phead;
  phead->prev = prev;
  free(del);
  del = NULL;
}
  1. 头删

//头删
void LTPopFront(LTNode* phead)
{
  assert(phead);
  assert(phead->next != phead);
  LTNode* del = phead->next;
  LTNode* next = del->next;
  //phead del next
  next->prev = phead;
  phead->next = next;
  free(del);
  del = NULL;
}
  1. 查找
LTNode* LTFind(LTNode* phead, LTDataType x)
{
  assert(phead);
  LTNode* pcur = phead->next;
  while (pcur != phead)
  {
    if (x == pcur->data)
    {
      return pcur;
    }
    pcur = pcur->next;
  }
  return NULL;
}
  1. 在pos位置之后插入数据
//在pos位置之后插入数据
void LTInsert(LTNode* pos, LTDataType x)
{
  assert(pos);
  LTNode* newnode = LTBuyNode(x);
  //pos newnode pos->next
  newnode->next = pos->next;
  newnode->prev = pos;
  pos->next->prev = newnode;
  pos->next = newnode;
}
  1. 删除pos位置的数据

//删除pos位置的数据
void LTErase(LTNode* pos)
{
  assert(pos);
  //pos->prev pos pos->next
  pos->next->prev = pos->prev;
  pos->prev->next = pos->next;
  free(pos);
  pos = NULL;
}
  1. 销毁
void LTDesTroy(LTNode** pphead)
{
  assert(pphead);
  //哨兵位不能为空
  assert(*pphead);
  LTNode* pcur = (*pphead)->next;
  while (pcur != *pphead)
  {
    LTNode* next = pcur->next;
    free(pcur);
    pcur = next;
  }
  //链表中只有一个哨兵位
  free(*pphead);
  *pphead = NULL;
}

也可以这样写：

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

但是要注意：这样写要在调用完函数后再写一句 plist = NULL;

这两种写法我们更推荐第二种：推荐传一级指针**（保持接口一致性）**

完整代码：

//List.h
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
//定义双向链表中节点的结构
typedef int LTDataType;
typedef struct ListNode
{
  LTDataType data;
  struct ListNode* prev;
  struct ListNode* next;
}LTNode;
//注意，双向链表是带有哨兵位的，插入数据之前链表中必须要先初始化一个哨兵位
//void LTInit(LTNode** pphead);
LTNode* LTInit();
//void LTDesTroy(LTNode** pphead);
void LTDesTroy(LTNode* phead);//推荐传一级指针（保持接口一致性）
void LTPrint(LTNode* phead);
//概念：当链表中只有哨兵位节点的时候，我们称该链表为空链表；即哨兵位是不能删除的
//不需要改变哨兵位，则不需要传二级指针
//如果需要修改哨兵位的话，则传二级指针
void LTPushBack(LTNode* phead, LTDataType x);
void LTPushFront(LTNode* phead, LTDataType x);
//头删、尾删
void LTPopBack(LTNode* phead);
void LTPopFront(LTNode* phead);
//查找
LTNode* LTFind(LTNode* phead, LTDataType x);
//在pos位置之后插入数据
void LTInsert(LTNode* pos, LTDataType x);
//删除pos位置的数据
void LTErase(LTNode* pos);

//List.c
#include "List.h"
//void LTInit(LTNode** pphead)
//{
//  *pphead = (LTNode*)malloc(sizeof(LTNode));
//
//  if (NULL == *pphead)
//  {
//    perror("malloc fail!");
//    exit(1);
//  }
//
//  (*pphead)->data = -1;
//  (*pphead)->next = (*pphead)->prev = *pphead;
//}
LTNode* LTBuyNode(LTDataType x)
{
  LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
  if (NULL == newnode)
  {
    perror("malloc fail!");
    exit(1);
  }
  newnode->data = x;
  newnode->next = newnode->prev = newnode;
  return newnode;
}
//LTNode* LTInit()
//{
//  LTNode* phead = (LTNode*)malloc(sizeof(LTNode));
//
//  if (NULL == phead)
//  {
//    perror("malloc fail!");
//    exit(1);
//  }
//
//  phead->data = -1;
//  phead->next = phead->prev = phead;
//
//  return phead;
//}
LTNode* LTInit()
{
  LTNode* phead = LTBuyNode(-1);
  return phead;
}
//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{
  assert(phead);
  LTNode* newnode = LTBuyNode(x);
  //phead phead->prev(ptail) newnode
  newnode->next = phead;
  newnode->prev = phead->prev;
  phead->prev->next = newnode;
  phead->prev = newnode;
}
//头插
void LTPushFront(LTNode* phead, LTDataType x)
{
  assert(phead);
  LTNode* newnode = LTBuyNode(x);
  //phead newnode phead->next
  newnode->next = phead->next;
  newnode->prev = phead;
  phead->next->prev = newnode;
  phead->next = newnode;
}
void LTPrint(LTNode* phead)
{
  //phead不能为空
  assert(phead);
  LTNode* pcur = phead->next;
  while (pcur != phead)
  {
    printf("%d->", pcur->data);
    pcur = pcur->next;
  }
  printf("\n");
}
//尾删
void LTPopBack(LTNode* phead)
{
  assert(phead);
  //链表为空：只有一个哨兵位节点
  assert(phead->next != phead);//若哨兵位节点的next指针或者prev指针指向的是自己，说明当前链表为空
  LTNode* del = phead->prev;
  LTNode* prev = del->prev;
  prev->next = phead;
  phead->prev = prev;
  free(del);
  del = NULL;
}
//头删
void LTPopFront(LTNode* phead)
{
  assert(phead);
  assert(phead->next != phead);
  LTNode* del = phead->next;
  LTNode* next = del->next;
  //phead del next
  next->prev = phead;
  phead->next = next;
  free(del);
  del = NULL;
}
LTNode* LTFind(LTNode* phead, LTDataType x)
{
  assert(phead);
  LTNode* pcur = phead->next;
  while (pcur != phead)
  {
    if (x == pcur->data)
    {
      return pcur;
    }
    pcur = pcur->next;
  }
  return NULL;
}
//在pos位置之后插入数据
void LTInsert(LTNode* pos, LTDataType x)
{
  assert(pos);
  LTNode* newnode = LTBuyNode(x);
  //pos newnode pos->next
  newnode->next = pos->next;
  newnode->prev = pos;
  pos->next->prev = newnode;
  pos->next = newnode;
}
//删除pos位置的数据
void LTErase(LTNode* pos)
{
  assert(pos);
  //pos->prev pos pos->next
  pos->next->prev = pos->prev;
  pos->prev->next = pos->next;
  free(pos);
  pos = NULL;
}
//void LTDesTroy(LTNode** pphead)
//{
//  assert(pphead);
//  //哨兵位不能为空
//  assert(*pphead);
//
//  LTNode* pcur = (*pphead)->next;
//
//  while (pcur != *pphead)
//  {
//    LTNode* next = pcur->next;
//    free(pcur);
//    pcur = next;
//  }
//
//  //链表中只有一个哨兵位
//  free(*pphead);
//  *pphead = NULL;
//}
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
#include "List.h"
void ListTest01()
{
  //LTNode* plist = NULL;
  //LTInit(&plist);
  LTNode* plist = LTInit();
  //尾插
  //LTPushBack(plist, 1);
  //LTPushBack(plist, 2);
  //LTPushBack(plist, 3);
  //LTPushBack(plist, 4);
  //LTPrint(plist);
  //头插
  LTPushFront(plist, 1);
  LTPushFront(plist, 2);
  LTPushFront(plist, 3);
  LTPushFront(plist, 4);
  LTPrint(plist);
  //LTPopBack(plist);
  //LTPrint(plist);
  //LTPopBack(plist);
  //LTPrint(plist);
  //LTPopBack(plist);
  //LTPrint(plist);
  //LTPopBack(plist);
  //LTPrint(plist);
  LTPopBack(plist);
  LTPrint(plist);
  //头删
  //LTPopFront(plist);
  //LTPrint(plist);
  //LTPopFront(plist);
  //LTPrint(plist);
  //LTPopFront(plist);
  //LTPrint(plist);
  //LTPopFront(plist);
  //LTPrint(plist);
  LTPopFront(plist);
  LTPrint(plist);
  LTNode* findRet = LTFind(plist, 3);
  //if (NULL == findRet)
  //{
  //  printf("未找到！\n");
  //}
  //else
  //{
  //  printf("找到了！\n");
  //}
  //在指定位置之后插入数据
  //LTInsert(findRet, 66);
  //LTPrint(plist);
  //删除pos位置的节点
  LTErase(findRet);
  LTPrint(plist);
  //LTDesTroy(&plist);
  LTDesTroy(plist);
  plist = NULL;
}
int main()
{
  ListTest01();
  return 0;
}

3. 顺序表和双向链表的优缺点分析


文章标签：
存储
waves浪游
目录
相关文章
泡沫o0
|
XML 存储 Unix
DBus类型系统以及在Qt和C++ 中的使用（一）
DBus类型系统以及在Qt和C++ 中的使用
泡沫o0
950 0
Myon
|
SQL 安全 关系型数据库
supersqli（SQL注入流程及常用SQL语句）
supersqli（SQL注入流程及常用SQL语句）
Myon
320 0
哥很冷漠
|
JavaScript 定位技术
vue3 引入天地图
vue3 引入天地图
哥很冷漠
867 0
运营研究坊
|
9月前
|
Java Spring
SpringBoot2.7.18拦截器失效不起作用
本文记录了作者在配置Spring Boot项目中的拦截器时遇到的问题。通过复制和修改其他项目的拦截器代码，但发现拦截器始终不生效。最终发现问题出在`WebConfig.java`中配置路径模式的方式上，即在已设置`context-path`的情况下，不应再使用`addPathPatterns(contextPath + &quot;/**&quot;)`。文章提供了详细的配置文件和代码示例，帮助读者理解并避免类似问题。
运营研究坊
705 0
做梦都在改BUG
|
Python
Python实现PowerPoint演示文稿到图片的批量转换
PowerPoint演示文稿作为展示创意、分享知识和表达观点的重要工具，被广泛应用于教育、商务汇报及个人项目展示等领域。然而，面对不同的分享场景与接收者需求，有时需要我们将PPT内容以图片形式保存与传播。 这样能够避免软件兼容性的限制，确保信息接收者无需安装特定软件即可查看内容，还便于在网络社交平台、博客、电子邮件中快速分享与嵌入。而用Python代码可以高效地实现PowerPoint演示文稿到图片的批量转换，从而提升工作效率。 本文将介绍如何使用Python实现PowerPoint演示文稿到图片的转换。
做梦都在改BUG
186 1
bzf4tpxf3rljg
|
12月前
|
缓存 JavaScript 前端开发
集成Nunjucks
集成Nunjucks
bzf4tpxf3rljg
107 0
二哥不像程序员
|
机器学习/深度学习 算法 索引
面经｜缺失值填补的7种方法（使用场景+Python代码）
面经｜缺失值填补的7种方法（使用场景+Python代码）
二哥不像程序员
906 0
宇之追寻
|
关系型数据库 MySQL 数据库
MySQL索引与性能优化：代码实现指南
本文以代码实现为基础，深入探讨了MySQL索引与性能优化的关键概念。通过具体的示例，读者可以了解索引的作用与类型，学会创建和管理索引，掌握查询性能优化策略以及使用EXPLAIN命令分析查询计划。通过实际的代码操作，读者将更直观地理解如何利用索引提高查询效率，优化查询语句和连接操作，以及通过查询计划分析发现性能瓶颈。通过这些实用技巧，读者将能够在数据库操作中获得更出色的性能表现，为应用程序的高效运行提供有力支持。
宇之追寻
765 0
余二五
|
域名解析 缓存 网络协议
dnsmasq配置文件详解
余二五
1818 0
小白在努力jy
|
C语言 索引
【C语言】 操作符（下）： -- 条件操作符 --逗号表达式 -- 下标引用操作符 --表达式求值1
【C语言】 操作符（下）： -- 条件操作符 --逗号表达式 -- 下标引用操作符 --表达式求值1
小白在努力jy
159 0

热门文章

最新文章

  • 1
    MongoDB基础
  • 2
    Apache Flink 漫谈系列(10) - JOIN LATERAL
  • 3
    （ElasticsSearch学习）歌词检索Demo的实现：二. 搭建spring boot+spring data+jest+elasticsearch环境，实现歌词的全文检索
  • 4
    CentOs7 安装 Mysql5.7
  • 5
    工业物联网的容器化方法
  • 6
    [大数据之Spark]——Actions算子操作入门实例
  • 7
    mysql编译安装错误解决方法
  • 8
    《VMware Virtual SAN权威指南》一3.10　磁盘组的角色
  • 9
    NetApp提高收入预期 或将惠及EMC
  • 10
    linux永久更改eth0的ip地址后仍然ping不通过
  • 1
    前沿速览：TrafficVLM、DeepSeek-Terminus、Qwen3-Omni、蚂蚁百灵、Wan2.2-Animate、Qianfan-VL
    54
  • 2
    建筑施工安全 “智能防线”！AI 施工监测系统，全方位破解多场景隐患难题
    32
  • 3
    当AI遇上智慧能源：边缘计算才是“节能王炸组合”
    31
  • 4
    云存储账单太吓人？教你几招运维优化省钱大法
    34
  • 5
    AI在智慧能源管理中的边缘计算应用
    36
  • 6
    sigar获取机器部分负载信息方法及问题解决
    28
  • 7
    Optuna v4.5新特性深度解析：GPSampler实现约束多目标优化
    31
  • 8
    香烟品牌识别和规格识别设计思路
    32
  • 9
    《AI工具驱动的分布式任务调度系统从0到1实践解析》
    25
  • 10
    《人机分工重塑开发：遗留系统重构的AI实践指南》
    28

    • 相关电子书

    更多
  • 低代码开发师（初级）实战教程
  • 冬季实战营第三期：MySQL数据库进阶实战
  • 阿里巴巴DevOps 最佳实践手册
    • 下一篇
    2025云栖大会，阿里云百炼邀请您的参与和见证