数据结构:双向链表的实现(C实现)

在这里插入图片描述

个人主页 : 个人主页
个人专栏 : 《数据结构》 《C语言》

文章目录

    • 前言
  • 一、实现思路
    • 1.节点的结构(ListNode)
    • 2.新节点的创建(BuyListNode)
    • 3.头结点的创建(ListCreate)
    • 4.双向链表的销毁(ListDestroy)
    • 5.双向链表的打印(ListPrint)
    • 6.双向链表的尾插(ListPushBack)
    • 7.双向链表的尾删(ListPopBack)
    • 8.双向链表的头插(ListPushFront)
    • 9.双向链表的头删(ListPopFront)
    • 10.双向链表的查找(ListFind)
    • 11.双向链表在pos前插入(ListInsert)
    • 12.双向链表删除pos位置处的节点(ListErase)
  • 二、代码实现
  • 总结


前言

本篇博客,将要实现的是带头双向循环链表,该结构实现尾插,尾删只需要O(1)的时间复杂度。
其结构如下所示:

在这里插入图片描述


一、实现思路

1.节点的结构(ListNode)

既然要实现的链表是双向循环的,那么对于指针域,我们就需要指向节点上一个的指针指向节点下一个的指针。至于双向循环,我们只需要尾节点的next指向头结点,头结点的prev指向尾节点,即可实现双向循环。
如下:
在这里插入图片描述

typedef int LTDataType;//方便以后修改数据类型typedef struct ListNode
{LTDataType data;struct ListNode* next;struct ListNode* prev;
}ListNode;

2.新节点的创建(BuyListNode)

动态开辟一块空间,使该节点的prev,next都指向自己(方便头结构的创建),再为data赋值,返回该空间地址。

在这里插入图片描述

//创建新节点
ListNode* BuyListNode(LTDataType x)
{ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));if (newnode == NULL){perror("malloc");exit(-1);}newnode->data = x;newnode->next = newnode;newnode->prev = newnode;return newnode;
}

3.头结点的创建(ListCreate)

复用BuyListNode函数,使头结点的data为无效数据(这里即为-1)。

//创建返回链表的头结点
ListNode* ListCreate()
{return BuyListNode(-1);
}

4.双向链表的销毁(ListDestroy)

要销毁链表,我们就要遍历链表,那么如何遍历链表?

  • 以遍历到头节点为结束条件
  • 从头结点的下一个节点开始遍历

如上,我们就可以循环遍历链表。
销毁节点,我们需要两指针变量,一个记录要free的节点(cur),一个记录要free的节点的下一个节点(curNext)。每次free(cur),使cur = curNext。
在这里插入图片描述

//双向链表的销毁
void ListDestroy(ListNode* pHead)
{assert(pHead);ListNode* cur = pHead->next;while (cur != pHead){ListNode* curNext = cur->next;free(cur);cur = curNext;}free(pHead);
}

5.双向链表的打印(ListPrint)

我们只有遍历打印链表即可。

  • 以遍历到头节点为结束条件
  • 从头结点的下一个节点开始遍历
//双向链表的打印
void ListPrint(ListNode* pHead)
{assert(pHead);ListNode* cur = pHead->next;printf("head<=>");while (cur != pHead){printf("%d<=>", cur->data);cur = cur->next;}printf("head\n");
}

6.双向链表的尾插(ListPushBack)

我们只需要让尾节点(tail)的next指向newnode,newnode的prev指向尾节点(tail),newnode的next指向头结点,头结点的prev指向newnode.
我们知道该链表是双向循环的,那么头结点的上一个节点就是尾节点。(与单链表相比该链表实现尾插并不需要遍历找尾,时间复杂度是O(1) )。
在这里插入图片描述

//双向链表的尾插
void ListPushBack(ListNode* pHead, LTDataType x)
{assert(pHead);ListNode* newnode = BuyListNode(x);ListNode* tail = pHead->prev;tail->next = newnode;newnode->prev = tail;pHead->prev = newnode;newnode->next = pHead;
}

7.双向链表的尾删(ListPopBack)

我们只需要两个指针tail (指向尾节点),tailPrev (指向尾节点的上一个节点)。
free掉tail,使tailPrev的next指向头结点,头结点的prev指向tailPrev。

  • 注意:head->next == head 时,链表无有效数据,不能尾删数据。

在这里插入图片描述

//双向链表的尾删
void ListPopBack(ListNode* pHead)
{assert(pHead);//pHead->next == pHead时,链表没有元素assert(pHead->next != pHead);ListNode* tail = pHead->prev;ListNode* tailPrev = tail->prev;pHead->prev = tailPrev;tailPrev->next = pHead;free(tail);
}

8.双向链表的头插(ListPushFront)

我们只需要一个指针 first (头结点的下一个节点),使first的prev指向newnode,newnode的next指向first,head的next指向newnode,newnode的prev指向head。

在这里插入图片描述
head节点是哨兵位,不存储有效数据。

//双向链表的头插
void ListPushFront(ListNode* pHead, LTDataType x)
{assert(pHead);ListNode* newnode = BuyListNode(x);ListNode* first = pHead->next;newnode->next = first;first->prev = newnode;newnode->prev = pHead;pHead->next = newnode;
}

9.双向链表的头删(ListPopFront)

我们需要两个指针frist (指向头结点的下一个节点),second (指向头结点的下一个的下一个节点)。
free掉first,使second的prev指向头结点,头结点的next指向second。

  • 注意:如果head->next == head,表示链表为空,不能头删。

在这里插入图片描述

//双向链表的头删
void ListPopFront(ListNode* pHead)
{assert(pHead);assert(pHead->next != pHead);ListNode* first = pHead->next;ListNode* second = first->next;second->prev = pHead;pHead->next = second;free(first);
}

10.双向链表的查找(ListFind)

我们需要遍历链表,比较链表元素是否是要查找对象。如果找到了,返回该节点的地址。如果找不到,返回NULL。

//双向链表的查找
ListNode* ListFind(ListNode* pHead, LTDataType x)
{assert(pHead);ListNode* cur = pHead->next;while (cur != pHead){if (cur->data == x)return cur;cur = cur->next;}return NULL;
}

11.双向链表在pos前插入(ListInsert)

我们需要一个指针 posPrev (指向pos前一个节点)。
pos的prev指向newnode,newnode的next指向pos;posPrev的next指向newnode,newnode的prev指向posPrev。

  • 如果pos指向头结点(哨兵位),那么ListInsert相当与完成尾插。
  • 如果pos指向头结点(哨兵位)的下一个节点,那么ListInsert相当于头插。

在这里插入图片描述

//双向链表在pos前进行插入
void ListInsert(ListNode* pos, LTDataType x)
{assert(pos);ListNode* newnode = BuyListNode(x);ListNode* posPrev = pos->prev;newnode->prev = posPrev;posPrev->next = newnode;newnode->next = pos;pos->prev = newnode;
}

12.双向链表删除pos位置处的节点(ListErase)

我们需要两个指针posPrev(记录pos的上一个节点的地址),posNext(记录pos的下一个节点的地址)。free掉pos,使posNext的prev指向posPrev,posPrev的next指向posNext。

  • 如果pos指向头结点的下一个,那么ListErase相当于头删。
  • 如果pos指向头结点的上一个(也就是尾节点),那么ListErase相当于尾删。

在这里插入图片描述


//双向链表删除pos位置的节点
void ListErase(ListNode* pos)
{assert(pos);ListNode* posNext = pos->next;ListNode* posPrev = pos->prev;posPrev->next = posNext;posNext->prev = posPrev;free(pos);
}

二、代码实现

对于头插,尾插函数,我复用了ListInsert函数。
对于头删,尾删函数,我复用了ListErase函数。

//Lish.h 文件#pragma once#include <stdio.h>
#include <stdlib.h>
#include <assert.h>typedef int LTDataType;typedef struct ListNode
{LTDataType data;struct ListNode* next;struct ListNode* prev;
}ListNode;//创建返回链表的头结点
ListNode* ListCreate();//创建新节点
ListNode* BuyListNode(LTDataType x);//双向链表的销毁
void ListDestroy(ListNode* pHead);//双向链表的打印
void ListPrint(ListNode* pHead);//双向链表的尾插
void ListPushBack(ListNode* pHead, LTDataType x);//双向链表的尾删
void ListPopBack(ListNode* pHead);//双向链表的头插
void ListPushFront(ListNode* pHead, LTDataType x);//双向链表的头删
void ListPopFront(ListNode* pHead);//双向链表的查找
ListNode* ListFind(ListNode* pHead, LTDataType x);//双向链表在pos前进行插入
void ListInsert(ListNode* pos, LTDataType x);//双向链表删除pos位置的节点
void ListErase(ListNode* pos);

//Lish.c  文件#include "List.h"//创建返回链表的头结点
ListNode* ListCreate()
{return BuyListNode(-1);
}//创建新节点
ListNode* BuyListNode(LTDataType x)
{ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));if (newnode == NULL){perror("malloc");exit(-1);}newnode->data = x;newnode->next = newnode;newnode->prev = newnode;return newnode;
}//双向链表的打印
void ListPrint(ListNode* pHead)
{assert(pHead);ListNode* cur = pHead->next;printf("head<=>");while (cur != pHead){printf("%d<=>", cur->data);cur = cur->next;}printf("head\n");
}//双向链表的尾插
void ListPushBack(ListNode* pHead, LTDataType x)
{assert(pHead);/*ListNode* newnode = BuyListNode(x);ListNode* tail = pHead->prev;tail->next = newnode;newnode->prev = tail;pHead->prev = newnode;newnode->next = pHead;*/ListInsert(pHead, x);
}//双向链表的尾删
void ListPopBack(ListNode* pHead)
{assert(pHead);//pHead->next == pHead时,链表没有元素assert(pHead->next != pHead);/*ListNode* tail = pHead->prev;ListNode* tailPrev = tail->prev;pHead->prev = tailPrev;tailPrev->next = pHead;free(tail);*/ListErase(pHead->prev);
}//双向链表的头插
void ListPushFront(ListNode* pHead, LTDataType x)
{assert(pHead);/*ListNode* newnode = BuyListNode(x);ListNode* first = pHead->next;newnode->next = first;first->prev = newnode;newnode->prev = pHead;pHead->next = newnode;*/ListInsert(pHead->next, x);
}//双向链表的头删
void ListPopFront(ListNode* pHead)
{assert(pHead);assert(pHead->next != pHead);/*ListNode* first = pHead->next;ListNode* second = first->next;second->prev = pHead;pHead->next = second;free(first);*/ListErase(pHead->next);
}//双向链表的查找
ListNode* ListFind(ListNode* pHead, LTDataType x)
{assert(pHead);ListNode* cur = pHead->next;while (cur != pHead){if (cur->data == x)return cur;cur = cur->next;}return NULL;
}//双向链表在pos前进行插入
void ListInsert(ListNode* pos, LTDataType x)
{assert(pos);ListNode* newnode = BuyListNode(x);ListNode* posPrev = pos->prev;newnode->prev = posPrev;posPrev->next = newnode;newnode->next = pos;pos->prev = newnode;
}//双向链表删除pos位置的节点
void ListErase(ListNode* pos)
{assert(pos);ListNode* posNext = pos->next;ListNode* posPrev = pos->prev;posPrev->next = posNext;posNext->prev = posPrev;free(pos);
}//双向链表的销毁
void ListDestroy(ListNode* pHead)
{assert(pHead);ListNode* cur = pHead->next;while (cur != pHead){ListNode* curNext = cur->next;free(cur);cur = curNext;}free(pHead);
}

总结

以上就是双向链表的实现!!!
在这里插入图片描述

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/78163.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

解决单节点es索引yellow

现象 单节点的es&#xff0c;自动创建索引后&#xff0c;默认副本个数为1&#xff0c;索引状态为yellow 临时解决 修改副本个数为0 永久解决 方法1、修改elasticsearch.yml文件&#xff0c;添加配置并重启es number_of_replicas&#xff1a;副本分片数&#xff0c;默认…

SpringBoot之logback-spring.xml详细配置

《logback官网》 各种指导文件&#xff0c;有空自己去看&#xff0c;比如&#xff1a;我们需要调整的是布局&#xff0c;直接看Layouts。 pom.xml <!-- 环境配置 --><profiles><profile><id>dev</id><properties><spring.profiles.a…

K8s operator从0到1实战

Operator基础知识 Kubernetes Operator是一种用于管理和扩展Kubernetes应用程序的模式和工具。它们是一种自定义的Kubernetes控制器&#xff0c;可以根据特定的应用程序需求和业务逻辑扩展Kubernetes功能。 Kubernetes Operator基于Kubernetes的控制器模式&#xff0c;通过自…

使用webpack建立React+TS项目

之前写过类似的文章&#xff0c;这次看到一本新书里也介绍了这个知识点&#xff0c;故尝试之。 Refer: 《Learn React With TypeScript - A Beginners Guide To Reactive Web Development With React 18 and TypeScript》chapter3 Creating a project with webpack 1.先建立一…

p7付费课程笔记6:CMS GC

目录 前言 工作步骤 缺点 问题 前言 上一章节我们讲了串/并行GC&#xff0c;这一章节说下CMS GC。看前思考一个问题&#xff0c;并行GC与CMS GC的区别在哪里。 什么是CMS收集器 CMS(Concurrent Mark-Sweep)是以牺牲吞吐量为代价来获得最短回收停顿时间的垃圾回收器。对于…

设计模式之六:命令模式(封装调用)

命令模式可以将请求的对象和执行请求的对象解耦&#xff08;实际上是通过命令对象进行沟通&#xff0c;即解耦&#xff09;。&#xff08;个人感觉&#xff0c;这章讲的很一般&#xff09; 按个人理解来讲&#xff1a; 假如需要一个遥控器&#xff0c;遥控器有一个插口可以插上…

[PM]敏捷开发之Scrum总结

在项目管理中&#xff0c;不少企业和项目团队也发现传统的项目管理模式已不能很好地适应今天的项目环境的要求。因此&#xff0c;敏捷项目管理应运而生&#xff0c;本文将为大家介绍Scrum敏捷项目管理以及应用方法。 什么是Scrum敏捷项目管理 敏捷项目管理作为新兴的项目管理模…

redis缓存雪崩和缓存击穿

目录 缓存雪崩 解决方案&#xff1a; 缓存击穿 ​解决方案 缓存雪崩 缓存雪崩是指在同一时段大量的缓存key同时失效或者Redis服务宕机&#xff0c;导致大量请求到达数据库&#xff0c;带来巨大压力。 解决方案&#xff1a; u 给不同的 Key 的 TTL 添加随机值 u 利用 Redis …

Redis的基础

一、进入redis 内部 / 关闭 # 方式一&#xff1a; // 进入redis redis-cli // 有密码输入密码 &#xff1a;auth [username] password auth 123456 # 方式二&#xff1a; // 进入redis 并且输入密码 redis-cli -a 123456// 如果在docker 里面的则可以 docker exec -it redis…

架构,性能和游戏 《游戏编程模式》学习笔记

开新坑&#xff0c;准备把《游戏编程模式》这本书啃完。这是一本讲设计模式的书&#xff0c;针对游戏开发而作&#xff0c;写得很好。 以下是读书笔记&#xff0c;文末有原文链接 每个程序都有一定的软件架构&#xff0c;哪怕是全塞到main里也是一种架构好的架构可以把代码写成…

RocketMQ使用

说明&#xff1a;本文介绍RocketMQ的消费模式&消息类型&#xff0c;RocketMQ的安装参考及简单使用&#xff0c;参考&#xff1a;http://t.csdn.cn/BKFPj 消费模式 RocketMQ与RabbitMQ最大的区别在于&#xff0c;RocketMQ是根据消息的Topic锁定消费者的&#xff0c;Topic属…

摄像头电池组和平衡车电池组

摄像头电池组 Wh~是电量 Wh V*Ah 毫安(mA)~是电流 电量是9.62Wh&#xff0c;电压是 3.7v 9.62 wh / 3.7v 2.6 Ah 2600mAH 4个并联电池&#xff1a;10400mAH / 4 2600mAH PH2.0mm-2Pins 平衡车 72 wh / 36v 2 Ah 2000mAH 对比自己买的单粒电池 vs 摄像头和平衡车的 …

嵌入式开发学习(STC51-15-红外遥控)

内容 使用外部中断功能&#xff0c;使按下红外遥控器&#xff0c;将对应键值编码数据解码后通过数码管显示 红外遥控介绍 红外线简介 人的眼睛能看到的可见光按波长从长到短排列&#xff0c;依次为红、橙、黄、绿、青、蓝、紫&#xff1b; 其中红光的波长范围为 0.62&…

前端小练习:案例5.律动爱心

目录 一.效果预览图 二.实现思路 ​编辑 1.html部分 2.css部分 三.完整代码 一.效果预览图 二.实现思路 想要实现爱心律动效果并不难&#xff0c;核心点是关键帧动画。 定义律动爱心需要的元素块&#xff0c;使用定位或者弹性布局等方法&#xff08;定位元素不适合布局&…

Android应用开发(6)TextView进阶用法

Android应用开发学习笔记——目录索引 本章介绍文本视图&#xff08;TextView&#xff09;的显示&#xff0c;包括&#xff1a;设置文本内容、设置文本大小、设置文本显示颜色。 一、设置TextView显示内容 Layout XML文件中设置 如&#xff1a;res/layout/activity_main.xm…

【Matter】基于Ubuntu 22.04 交叉编译chip-tool

编译工程之际&#xff0c;记录一下编译过程&#xff0c;免得后续遗忘&#xff0c;总结下来chip-tool 交叉编译涉及到的知识点&#xff1a; 需要了解如何支持交叉编译&#xff0c;基于GN编译框架需要理解应用库如何交叉编译&#xff0c;理解pkg-config的使用meson 编译&#xf…

“我,在腾讯月薪5万,离职后才明白:人越努力,只会越平庸”

那天看瑞达利欧说&#xff0c;他今年已经60岁了&#xff0c;可以说是阅人无数&#xff0c;但没有一个成功人士天赋异禀。 真的如他所说吗&#xff1f; 那张一鸣呢&#xff1f; 字节做到这么大&#xff0c;赚了这么多钱&#xff0c;不靠天赋&#xff0c;靠的是什么&#xff1…

C++笔记之从数组指针到函数数组指针(使用using name和std::function)

C笔记之从数组指针到函数数组指针(使用using name和std::function) 参考笔记&#xff1a; C之指针探究(三)&#xff1a;指针数组和数组指针 C之指针探究(十三)&#xff1a;函数指针数组 C之指针探究(二)&#xff1a;一级指针和一维数组 C之指针探究(十一)&#xff1a;函数名的…

IP路由基础+OSPF 基础

IP路由 RIB与FIB RIB&#xff1a;Routing Information Base&#xff0c;路由信息库 &#xff0c;路由器的控制平面 FIB&#xff1a;Forwarding Information Base&#xff0c;转发信息库&#xff0c;路由器的数据平面 路由信息库主要是记录直连路由以及协议宣告的路由信息&am…

【vue】vue基础知识

1、插值表达式&属性绑定 <!--template展示给用户&#xff0c;相当于MVVM模式中的V--> <template><div class"first_div">//插值表达式<p>{{ message }}</p>//这里的参数是从父组件的template里传过来的<p>{{data_1}}</p…