【数据结构】双向链表 C++

一、什么是双向链表

1、定义

双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点。

双向链表的结构如图(图片来源于网络):

2、时空复杂度

双向链表的空间复杂度是 O ( n ) O(n) O(n) 的,其时间复杂度如下:

操作时间复杂度
遍历 O ( n ) O(n) O(n)
访问指定节点 O ( 1 ) O(1) O(1)
删除指定编号节点 O ( n ) O(n) O(n)
删除指定位置节点 O ( 1 ) O(1) O(1)
在指定编号的节点后插入节点 O ( n ) O(n) O(n)
在指定位置的节点后插入节点 O ( 1 ) O(1) O(1)
查询前驱、后继 O ( 1 ) O(1) O(1)
修改指定编号节点的值 O ( n ) O(n) O(n)
修改指定位置节点的值 O ( 1 ) O(1) O(1)
交换两个 list 容器 O ( 1 ) O(1) O(1)

二、双向链表的基本操作

1. 定义双向链表节点

每个节点有三个值:

  1. val:存储每个节点的权值;
  2. last:指向每个节点的前面的第一个节点;
  3. next:指向每个节点的后面的第一个节点;

代码如下:

template<typename T>
struct ListNode{T value;ListNode<T>* last;ListNode<T>* next;ListNode():value(0){last=NULL,next=NULL;}ListNode(const T &x):value(x){last=NULL,next=NULL;}~ListNode(){value=0;delete last;delete next;}
};

2. 创建双向链表类

类里面包含两个节点和一个变量:

  1. headnode:头节点,初始时前驱后继均为空,值为 − 1 -1 1
  2. endnode:尾节点,初始时前驱后继均为空,值为 − 1 -1 1
  3. listsize:记录双向链表的节点个数,不包含头尾节点;

代码如下:

template<typename T>
class list{private:unsigned listsize;ListNode<T>* headnode;ListNode<T>* endnode;
};

3. 初始化双向链表类

共有四种初始化方式:

  1. list<类型名> a;:此时创建一个空的双向链表;
  2. list<类型名> a(n);:此时创建一个大小为 n n n 的双向链表,并将所有点的初始值赋为 0 0 0
  3. list<类型名> a(n,m):此时创建一个大小为 n n n 的双向链表,并将所有点的初始值赋为 m m m
  4. list<类型名> a={a1,a2,a3,...,an};:此时创建一个大小为 n n n 的双向链表,并将第 i i i 个节点的初始值赋为 a i a_i ai

第一种初始化方式代码如下:

list():listsize(0){headnode=new ListNode<T>(-1);endnode=new ListNode<T>(-1);
}

第二种初始化方式代码如下:

list(const int &size_t):listsize(size_t) {headnode=new ListNode<T>(-1);endnode=new ListNode<T>(-1);ListNode<T>* now=headnode;for(int i=0;i<listsize;++i){ListNode<T>* newnode=new ListNode<T>(0);endnode->last=newnode;newnode->next=endnode;newnode->last=now;now->next=newnode;now=now->next;}
}

第三种初始化方式代码如下:

list(const int &size_t,const int &val
):listsize(size_t){headnode=new ListNode<T>(-1);endnode=new ListNode<T>(-1);ListNode<T>* now=headnode;for(int i=0;i<listsize;++i){ListNode<T>* newnode=new ListNode<T>(val);endnode->last=newnode;newnode->next=endnode;newnode->last=now;now->next=newnode;now=now->next;}
}

第四种初始化方式代码如下:

typedef std::initializer_list<T> lisval;
list(lisval vals){listsize=0;headnode=new ListNode<T>(-1);endnode=new ListNode<T>(-1);ListNode<T>* now=headnode;for(auto val:vals){ListNode<T>* newnode=new ListNode<T>(val);endnode->last=newnode;newnode->next=endnode;newnode->last=now;now->next=newnode;now=now->next; ++listsize;}
}

3. 一些基础的函数

这些函数是除了加点删点之外最常见的几个函数。

  1. size():获取链表的大小,返回一个 unsigned 值,表示当前链表中普通节点(非头尾节点)的个数。

    代码如下:

    unsigned size() const {return listsize;
    }
    
  2. empty():返回当前链表是否为空,如果是,返回 true,否则返回 false。

    代码如下:

    bool empty() const {return listsize==0;
    }
    
  3. begin():返回第一个普通节点。

    代码如下:

    ListNode<T>* begin(
    ) const {return headnode->next;
    }
    
  4. end():返回尾指针。

    代码如下:

    ListNode<T>* end(
    ) const {return endnode;
    }
    
  5. rbegin():返回最后一个普通节点。

    代码如下:

    ListNode<T>* rbegin(
    ) const {return endnode->last;
    }
    
  6. rend():返回头指针。

    代码如下:

    ListNode<T>* rend(
    ) const {return headnode;
    }
    
  7. front():返回第一个普通节点的值。

    代码如下:

    T front() const {return begin()->value;
    }
    
  8. back():返回最后一个普通节点的值。

    代码如下:

    T back() const {return rbegin()->value;
    }
    
  9. print():遍历并输出链表中每个普通节点的值,结尾换行。

    代码如下:

    void print(
    ) const {if(empty()) return;ListNode<T>* now=headnode->next;while(now->next!=NULL){printf("%d ",now->value);now=now->next;} putchar('\n');
    }
    
  10. swap(list<类型名> &b):交换两个 list 容器,实际上是交换头尾指针和 l i s t s i z e listsize listsize

    代码如下:

    void swap(list<T> &b){ListNode<T>* temp;temp=headnode;headnode=b.headnode;b.headnode=temp;temp=endnode;endnode=b.endnode;b.endnode=temp;unsigned size_t=listsize;listsize=b.listsize;b.listsize=size_t;
    }
    

5. 插入节点

共四种方法,代码如下:

void push_back(const T &val
){ ++listsize;if(endnode->last==NULL){ListNode<T>* newnode=new ListNode<T>(val);endnode->last=newnode;newnode->next=endnode;headnode->next=newnode;newnode->last=headnode;return;}ListNode<T>* pre=endnode->last;ListNode<T>* newnode=new ListNode<T>(val);pre->next=newnode;newnode->last=pre;newnode->next=endnode;endnode->last=newnode;
}
void push_front(const T &val
){ ++listsize;if(headnode->next==NULL){ListNode<T>* newnode=new ListNode<T>(val);endnode->last=newnode;newnode->next=endnode;headnode->next=newnode;newnode->last=headnode;return;}ListNode<T>* suf=headnode->next;ListNode<T>* newnode=new ListNode<T>(val);headnode->next=newnode;newnode->last=headnode;newnode->next=suf;suf->last=newnode;
}
void insert(const T &pos,const T &val
){  int nowpos=0;if(pos==0){push_front(val);++listsize; return;} else if(pos>=listsize){push_back(val);++listsize; return;}ListNode<T>* now=headnode->next;while(now->next!=NULL){++nowpos;if(nowpos==pos){ListNode<T>* newnode=new ListNode<T>(val);ListNode<T>* suf=now->next;newnode->next=suf;suf->last=newnode;newnode->last=now;now->next=newnode;++listsize; return;}now=now->next;}
}
void insert(ListNode<T>* now,const T &val
){if(now==endnode){push_back(val); return;}ListNode<T>* newnode=new ListNode<T>(val);ListNode<T>* suf=now->next;newnode->next=suf;suf->last=newnode;newnode->last=now;now->next=newnode;++listsize; return;
}

6. 修改指定位置的值

两种方法,代码如下:

void reassign(const T &pos,const T &val
){if(pos>listsize) return;if(empty()||!pos) return;ListNode<T>* now=headnode->next;int nowpos=0;while(now->next!=NULL){++nowpos;if(nowpos==pos){now->value=val;return;} now=now->next;}
}
void reassign(ListNode<T>* now,const int &val
) const {now->value=val;
}

7.删除节点

和插入一样,共有四种,代码如下:

void pop_back(){if(empty()) return;ListNode<T>* now=endnode->last;ListNode<T>* pre=now->last;if(pre==headnode){endnode->last=NULL;headnode->last=NULL;--listsize; return;}endnode->last=pre;pre->next=endnode;--listsize;
}
void pop_front(){if(empty()) return;ListNode<T>* now=headnode->next;ListNode<T>* suf=now->next;if(suf==endnode){endnode->last=NULL;headnode->last=NULL;--listsize; return;}headnode->next=suf;suf->last=headnode;--listsize;
}
void erase(const int &pos
) {if(pos>listsize) return;if(empty()||!pos) return;ListNode<T>* now=headnode->next;int nowpos=0;while(now!=endnode){++nowpos;if(nowpos==pos){ListNode<T>* pre=now->last;ListNode<T>* suf=now->next;if(pre==headnode||suf==endnode){endnode->last=NULL;headnode->next=NULL;delete now;--listsize; return;}pre->next=suf;suf->last=pre;delete now;--listsize; return;}now=now->next;}
}
void erase(ListNode<T>* now
){  if(now==headnode) return;if(now==endnode) return;if(empty()) return;ListNode<T>* pre=now->last;ListNode<T>* suf=now->next;if(pre==headnode||suf==endnode){endnode->last=NULL;headnode->last=NULL;--listsize; return;}pre->next=suf;suf->last=pre;--listsize; return;
}

8. 注销双向链表类

遍历一遍,然后将每个节点都删除就可以了。

代码如下:

~list(){ListNode<T>* now=headnode->next;while(now!=NULL){ListNode<T>* nxt=now->next;delete now;now=nxt;} delete headnode; listsize=0;
}

三、完整代码

我知道你们只看这个

码风丑陋,不喜勿喷

#include<stdio.h>
#include<stdlib.h>
#include<initializer_list>
namespace STL{template<typename T>struct ListNode{T value;ListNode<T>* last;ListNode<T>* next;ListNode():value({}){last=NULL,next=NULL;}ListNode(const T &x):value(x){last=NULL,next=NULL;}~ListNode(){// value={};last=NULL;next=NULL;}};template<typename T>class list{private:unsigned listsize;ListNode<T>* headnode;ListNode<T>* endnode;public:list():listsize(0){headnode=new ListNode<T>(T({-1}));endnode=new ListNode<T>(T({-1}));}list(const int &size_t):listsize(size_t) {headnode=new ListNode<T>(-1);endnode=new ListNode<T>(-1);ListNode<T>* now=headnode;for(int i=0;i<listsize;++i){ListNode<T>* newnode=new ListNode<T>(0);endnode->last=newnode;newnode->next=endnode;newnode->last=now;now->next=newnode;now=now->next;}}list(const int &size_t,const int &val):listsize(size_t){headnode=new ListNode<T>(-1);endnode=new ListNode<T>(-1);ListNode<T>* now=headnode;for(int i=0;i<listsize;++i){ListNode<T>* newnode=new ListNode<T>(val);endnode->last=newnode;newnode->next=endnode;newnode->last=now;now->next=newnode;now=now->next;}}typedef std::initializer_list<T> lisval;list(lisval vals){listsize=0;headnode=new ListNode<T>(-1);endnode=new ListNode<T>(-1);ListNode<T>* now=headnode;for(auto val:vals){ListNode<T>* newnode=new ListNode<T>(val);endnode->last=newnode;newnode->next=endnode;newnode->last=now;now->next=newnode;now=now->next; ++listsize;}}unsigned size() const {return listsize;}bool empty() const {return listsize==0;}ListNode<T>* begin() const {return headnode->next;}ListNode<T>* end() const {return endnode;}ListNode<T>* rbegin() const {return endnode->last;}ListNode<T>* rend() const {return headnode;}T front() const {return begin()->value;}T back() const {return rbegin()->value;}void print() const {if(empty()) return;ListNode<T>* now=headnode->next;while(now->next!=NULL){printf("%lld ",now->value);now=now->next;} putchar('\n');}void push_back(const T &val){ ++listsize;if(endnode->last==NULL){ListNode<T>* newnode=new ListNode<T>(val);endnode->last=newnode;newnode->next=endnode;headnode->next=newnode;newnode->last=headnode;return;}ListNode<T>* pre=endnode->last;ListNode<T>* newnode=new ListNode<T>(val);pre->next=newnode;newnode->last=pre;newnode->next=endnode;endnode->last=newnode;}void push_front(const T &val){ ++listsize;if(headnode->next==NULL){ListNode<T>* newnode=new ListNode<T>(val);endnode->last=newnode;newnode->next=endnode;headnode->next=newnode;newnode->last=headnode;return;}ListNode<T>* suf=headnode->next;ListNode<T>* newnode=new ListNode<T>(val);headnode->next=newnode;newnode->last=headnode;newnode->next=suf;suf->last=newnode;}void insert(const T &pos,const T &val){  int nowpos=0;if(pos==0){push_front(val);++listsize; return;} else if(pos>=listsize){push_back(val);++listsize; return;}ListNode<T>* now=headnode->next;while(now->next!=NULL){++nowpos;if(nowpos==pos){ListNode<T>* newnode=new ListNode<T>(val);ListNode<T>* suf=now->next;newnode->next=suf;suf->last=newnode;newnode->last=now;now->next=newnode;++listsize; return;}now=now->next;}}void insert(ListNode<T>* now,const T &val){if(now==endnode){push_back(val); return;}ListNode<T>* newnode=new ListNode<T>(val);ListNode<T>* suf=now->next;newnode->next=suf;suf->last=newnode;newnode->last=now;now->next=newnode;++listsize; return;}void reassign(const T &pos,const T &val){if(pos>listsize) return;if(empty()||!pos) return;ListNode<T>* now=headnode->next;int nowpos=0;while(now->next!=NULL){++nowpos;if(nowpos==pos){now->value=val;return;} now=now->next;}}void reassign(ListNode<T>* now,const int &val) const {now->value=val;}void pop_back(){if(empty()) return;ListNode<T>* now=endnode->last;ListNode<T>* pre=now->last;if(pre==headnode){endnode->last=NULL;headnode->next=NULL;delete now;--listsize; return;}endnode->last=pre;pre->next=endnode;delete now;--listsize;}void pop_front(){if(empty()) return;ListNode<T>* now=headnode->next;ListNode<T>* suf=now->next;if(suf==endnode){endnode->last=NULL;headnode->next=NULL;delete now;--listsize; return;}headnode->next=suf;suf->last=headnode;delete now;--listsize;}void erase(const int &pos) {if(pos>listsize) return;if(empty()||!pos) return;ListNode<T>* now=headnode->next;int nowpos=0;while(now!=endnode){++nowpos;if(nowpos==pos){ListNode<T>* pre=now->last;ListNode<T>* suf=now->next;if(pre==headnode||suf==endnode){endnode->last=NULL;headnode->next=NULL;delete now;--listsize; return;}pre->next=suf;suf->last=pre;delete now;--listsize; return;}now=now->next;}}void erase(ListNode<T>* now){  if(now==headnode) return;if(now==endnode) return;if(empty()) return;ListNode<T>* pre=now->last;ListNode<T>* suf=now->next;if(pre==headnode||suf==endnode){endnode->last=NULL;headnode->last=NULL;delete now;--listsize; return;}pre->next=suf;suf->last=pre;delete now;--listsize; return;}void swap(list<T> &b){ListNode<T>* temp;temp=headnode;headnode=b.headnode;b.headnode=temp;temp=endnode;endnode=b.endnode;b.endnode=temp;unsigned size_t=listsize;listsize=b.listsize;b.listsize=size_t;}~list(){ListNode<T>* now=headnode->next;while(now!=NULL){ListNode<T>* nxt=now->next;delete now;now=nxt;} delete headnode;listsize=0;}};
}
using STL::list;signed main(){system("pause");
}

给个赞再走吧

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

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

相关文章

虹科Pico汽车示波器 | 免拆诊断案例 | 2011款东风悦达起亚K5车发动机偶尔起动困难

一、故障现象 一辆2011款东风悦达起亚K5车&#xff0c;搭载G4KD发动机&#xff0c;累计行驶里程约为24.5万km。车主反映&#xff0c;第1次起动发动机时偶尔无法起动着机&#xff0c;第2次能够正常起动着机&#xff0c;但发动机故障灯异常点亮。为此在其他维修厂维修过&#xf…

GDAL源码剖析(九)之GDAL体系架构

GDAL源码剖析&#xff08;九&#xff09;之GDAL体系架构_gdal 源码-CSDN博客 在GDAL库中包含栅格数据的读写&#xff0c;矢量数据的读写&#xff0c;以及栅格和矢量数据的相关算法。下面主要对GDAL中栅格数据和矢量数据的体系架构做一个简单的说明。本人英文很烂&#xff0c;有…

vue的 blob文件下载文件时,后端自定义异常,并返回json错误提示信息,前端捕获信息并展示给用户

1.后端返回的json数据结构为&#xff1a; {"message":"下载失败&#xff0c;下载文件不存在&#xff0c;请联系管理员处理&#xff01;","code":500} 2.vue 请求后台接口返回的 Blob数据 3.问题出现的原因是&#xff0c;正常其他数据列表接口&…

统一处理异常和记录日志

统一处理异常 SpringBoot设计&#xff0c;如果出现错误404或500&#xff0c;自动调用特定路径下的html页面(路径和名字都特定)。/templates/error/404.html、/templates/error/500.html。程序中有错误自动就调用该页面。 但是错误有异步请求错误&#xff0c;也想同时记录日志。…

Windows系统安装WinSCP结合内网穿透实现公网远程SSH本地服务器

List item 文章目录 1. 简介2. 软件下载安装&#xff1a;3. SSH链接服务器4. WinSCP使用公网TCP地址链接本地服务器5. WinSCP使用固定公网TCP地址访问服务器 1. 简介 ​ Winscp是一个支持SSH(Secure SHell)的可视化SCP(Secure Copy)文件传输软件&#xff0c;它的主要功能是在本…

公司电脑如何对文件进行加密?

在现代企业中&#xff0c;文件加密是确保敏感数据安全的关键。使用华企盾DSC数据安全防泄密系统&#xff0c;公司电脑可以轻松地对文件进行加密&#xff0c;以防止未授权的访问和数据泄露。以下是对文件进行加密的步骤和方法&#xff1a; 智能半透明加密&#xff1a;这种模式允…

IntelliJ IDEA(WebStorm、PyCharm、DataGrip等)设置中英文等宽字体,英文为中文的一半(包括标点符号)

1.设置前&#xff08;idea默认字体为 JetBrains Mono&#xff09; 2.设置后&#xff08;楷体&#xff09;

Vue3 使用ElementUI 显示异常

element提供的样例不能正常显示&#xff0c;需要进行配置 1.npm install element-plus --save 2.main.js // main.ts import { createApp } from vue import ElementPlus from element-plus //全局引入 import element-plus/dist/index.css import App from ./App.vue const …

list的常用接口底层实现与介绍

目录 概念&#xff1a; list的基本结构&#xff1a; list的迭代器⭐❤&#xff1a; 自定义类型的完善&#xff1a; const的迭代器&#xff1a; insert erase&#xff1a; size empty push_back 、push_front 、pop_back、pop_front swap 、operator 析构函数…

【CSS】CSS三大特性、盒子模型

目录 CSS三大特性 1、层叠性 2、继承性 3、优先级 盒子模型 1、网页布局的本质 2、盒子模型&#xff08;Box Model&#xff09;组成 3、边框&#xff08;border&#xff09; 3.1、边框的使用 3.2、表格的细线边框 3.3、边框会影响盒子实际大小 4、内边距&#xff0…

Unity 九宫格

1. 把图片拖拽进资源文件夹 2.选中图片&#xff0c;然后设置图片 3.设置九宫格 4.使用图片&#xff0c;在界面上创建2个相同的Image,然后使用图片&#xff0c;修改Image Type 为Sliced

前端开发基础(HTML5 + CSS3)【第一篇】:HTML标签之文字排版、图片、链接、音频、视频 涵盖了两个综合案例 做到了基础学得会,实战写的出

点击前往前端开发基础专栏&#xff1a; 文章目录 HTML5 CSS3 开发一、开发环境搭建下载 VS Code1. 2 插件的下载1.3 项目和文件的下载 二、 什么是 HTML2.1 标签的语法2.2 代码演示&#xff1a;2.3 小结 三 、HTML基本骨架3.1 快捷键生成HTML骨架3.2 代码展示3.3 小结 四、标…

第十四讲:C语言字符函数和字符串函数

目录 1. 字符分类函数 2、字符转换函数 3. strlen的使⽤和模拟实现 4. strcpy 的使⽤和模拟实现 5. strcat 的使⽤和模拟实现 6. strcmp 的使⽤和模拟实现 7. strncpy 函数的使⽤ 8. strncat 函数的使⽤ 9. strncmp函数的使⽤ 10. strstr 的使⽤和模拟实现 11. strt…

Redis的持久化

目录 一、RDB&#xff08;Redis DataBase&#xff09; 二、AOF&#xff08;Append Only File&#xff09; Redis 是内存数据库&#xff0c;如果不将内存中的数据库状态保存到磁盘&#xff0c;那么一旦服务器进程退出&#xff0c;服务器中 的数据库状态也会消失。所以 Redis 提供…

从文字到思维:呆马GPT在人工智能领域的创新之旅

引言 生成式预训练变换器&#xff08;Generative Pre-trained Transformer&#xff0c;简称GPT&#xff09;领域是人工智能技术中的一大革新。自OpenAI推出第一代GPT以来&#xff0c;该技术经历了多代发展&#xff0c;不断提升模型的规模、复杂度和智能化程度。GPT模型通过在大…

【Linux】vim 编辑器

Linux 系统自带了 gedit 和 vi 编辑器&#xff0c;gedit 是图形化界面的操作&#xff0c;而 vi 由比较难用&#xff0c;所以建议安装 vim 编辑器&#xff0c;vim 是从 vi 发展出来的一个文本编辑器&#xff0c;相当于增强版的 vi &#xff0c;其代码补完、编译及错误跳转等功能…

从路由器syslog日志监控路由器流量

路由器是关键的网络基础设施组件&#xff0c;需要随时监控&#xff0c;定期监控路由器可以帮助管理员确保路由器通信正常。日常监控还可以清楚地显出通过网络的流量&#xff0c;通过分析路由器流量&#xff0c;安全管理员可及早识别可能发生的网络事件&#xff0c;从而避免停机…

负荆请罪将相和之后的廉颇蔺相如,下场如何?

“将相和”的故事相信许多人都听说过&#xff0c; 这个故事来自于司马迁的《史记》&#xff0c;并被许多版本的语文教科书所收录&#xff0c;而“完璧归赵”“负荆请罪”等成语也都是出自这个故事。但是这个故事并没有讲“将相和”之后的内容&#xff0c;实际上&#xff0c;蔺相…

C语言面试题之合法二叉搜索树

合法二叉搜索树 实例要求 实现一个函数&#xff0c;检查一棵二叉树是否为二叉搜索树&#xff1b; 示例 1: 输入:2/ \1 3 输出: true 示例 2: 输入:5/ \1 4/ \3 6 输出: false 解释: 输入为: [5,1,4,null,null,3,6]。根节点的值为 5 &#xff0c;但是其右子节点值为 4 …

VS2022使用属性表快速设置OpenCV工程属性

1.创建C控制台应用 2.配置工程 3.打开工程后,为工程添加属性表 打开属性管理器窗口,选择Debug|x64 然后右击选择添加新的项目属性表 并命名为opencv490_debug_x64 点击添加 Debug版本属性表添加成功 使用相同方法添加Release版本属性表 双击debug版本属性表并添加包含目录 添…