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

双向链表专题

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


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浪游
目录
相关文章
庄同学(魏庄)
|
9月前
|
SQL 存储 算法
clickhouse SQL优化
clickhouse 是 OLAP 数据库，但其具有独特的索引设计，所以如果拿 MySQL 或者其他 RDB 的优化经验来优化 clickhouse 可能得不到很好的效果，所以特此单独整理一篇文档，用于有 SQL 优化需求的同学，本人接触 clickhouse 时间也不长，难免有不足的地方，如果大家发现错误，还请不吝指正。
庄同学(魏庄)
83628 3
阿里云智能-计算巢-琥颐
|
8月前
|
人工智能 机器人 API
用AppFlow玩转通义百炼大模型应用
阿里云百炼平台提供一站式大模型开发服务，支持创建和定制应用，预置丰富插件和API。用户可以通过平台快速构建大模型应用，并利用AppFlow将其接入钉钉群聊，以AI卡片形式展示。
阿里云智能-计算巢-琥颐
73456 12
waves浪游
|
8月前
|
机器学习/深度学习 存储 算法
复杂度讲解
复杂度讲解
waves浪游
80 7
waves浪游
|
8月前
|
存储 编译器 C语言
通过这14点，让你快速入门C语言（3）
通过这14点，让你快速入门C语言（3）
waves浪游
35 0
waves浪游
|
8月前
500行代码实现贪吃蛇（2）
500行代码实现贪吃蛇（2）
waves浪游
82 8
waves浪游
|
8月前
|
Java 编译器 C语言
通过这14点，让你快速入门C语言（1）
通过这14点，让你快速入门C语言（1）
waves浪游
58 0
waves浪游
|
8月前
|
存储
单链表专题
单链表专题
waves浪游
46 4
waves浪游
|
8月前
|
存储 算法
顺序表专题
顺序表专题
waves浪游
54 4
waves浪游
|
8月前
|
存储 自然语言处理 程序员
程序环境和预处理（1）
程序环境和预处理（1）
waves浪游
64 0
左诗右码
|
8月前
|
存储 Shell 数据安全/隐私保护
Shell 内建命令：Shell 的内在魔力
Shell 内建命令比外部命令执行快，不需额外进程。`type` 命令用来检查命令类型。内建命令如 `cd`、`alias` 和 `echo` 直接在 Shell 中执行，不涉及磁盘 I/O。`type` 示例展示了 `cd` 是内建的，`ifconfig` 是外部的。`bash` 包含多种内建命令，如 `cd` 用于切换目录，`alias` 定义别名，`read` 从输入读取数据。`echo` 默认加换行，`echo -n` 可避免。
左诗右码
77 5

热门文章

最新文章

  • 1
    deepseek部署的详细步骤和方法，基于Ollama获取顶级推理能力！
  • 2
    讨论阶段性给予客户交付物所引发的风险问题
  • 3
    Linus Torvalds将中国亮相LinuxCon + ContainerCon + CloudOpen
  • 4
    DispatcherServlet与初始化主线
  • 5
    网络安全研究人员发现新漏洞：或成另一个WannaCry
  • 6
    Swift中常量和变量的声明
  • 7
    [20160516]adrci purge.txt
  • 8
    Docker Secure Deployment Guidelines
  • 9
    Eclipse没有权限操作rt.jar包中的sun包，导致sun.net.ftp.FtpClient引用报错
  • 10
    Learning Cocos2d-x for WP8（9）——Sprite到哪，我做主
  • 1
    去中心化存储：数据存储的新范式
    117
  • 2
    AI 赋能混合云运维：告别手工操作，迈向智能自愈！
    116
  • 3
    从Excel到大数据：别让工具限制你的思维！
    110
  • 4
    Go 切片导致 rand.Shuffle 产生重复数据的原因与解决方案
    97
  • 5
    基于SVPWM矢量控制的无速度传感器电机控制系统simulink建模与仿真
    34
  • 6
    基于小波变换和峰值搜索的光谱检测matlab仿真,带GUI界面
    38
  • 7
    DragAnything：视频PS来了！开源AI控制器让视频「指哪动哪」：拖拽任意物体轨迹，多对象独立运动一键生成
    41
  • 8
    FoloUp：比HR更懂岗位需求！开源语音面试平台爆火：1份岗位需求生成100问，语音AI追问逻辑漏洞
    29
  • 9
    KTransformers：告别天价显卡！国产框架让单卡24G显存跑DeepSeek-R1 671B大模型：推理速度飙升28倍
    307
  • 10
    基于深度学习的路面裂缝检测算法matlab仿真
    24

    • 相关电子书

    更多
  • 低代码开发师（初级）实战教程
  • 冬季实战营第三期：MySQL数据库进阶实战
  • 阿里巴巴DevOps 最佳实践手册
    • 下一篇
    阿里云oss简介和如何对接使用