c++:数据结构链表list的模拟实现

news/2025/3/16 23:35:18/

文章目录

  • 链表的知识回顾
  • 前期工作
  • 构造节点
  • 迭代器
    • 注意
    • 构造迭代器
    • 解引用*迭代器
    • 迭代器->
    • 迭代器++
    • 迭代器- -
    • 判断两个迭代器是否相等
  • 链表
    • empty_init
    • 构造
    • 拷贝构造
    • swap
    • operator=
    • begin和end
    • insert
    • push_back
    • push_front
    • erase
    • pop_back
    • pop_front
    • size
    • empty
    • clear
    • 析构


链表的知识回顾

链表是有一个个节点链接起来的.每一个节点里面存有数据val,下一个节点的地址next,双向循环链表还会有上一个节点的地址.
双向带头循环链表比双向循环链表多了一个头节点.又称哨兵位.在很多时候,多一个头节点能帮我们解决很多事.

在这里插入图片描述

下面模拟实现的就是双向带头循环链表,跟c++容器库list里面一样


前期工作

写一个自己的命名空间,防止跟库里面函数冲突.我们后面所写的函数都在中国命名空间里面.

namespace shh
{
}

构造节点

因为节点里面要存储很多值,所以我们写一个类把它封装起来.
同时,因为节点里面存储的数据val类型不清楚,写一个模板,让编译器自己根据类型去生成.

	//把节点封装成一个类template<class T>struct ListNode{ListNode<T>* prev = nullptr;ListNode<T>* next = nullptr;T val = T();ListNode(const T& tmp = T()):prev(nullptr), next(nullptr), val(tmp){}};

这里写一个构造,为我们后面可以直接用值tmp去生成节点,不用自己写.

迭代器

vector和string里面的迭代器都是原生指针,因为他们存储的物理空间连续.
例如: iterator(int
) ,iterator++ 会跳到下一个数字.iterator可以访问数据.

但是链表没有办法做到这一点.所以,我们将链表节点的指针封装成一个类,然后用上运算符重载,自己控制运算符,就能实现vector中T*的功能.

	template<class T,class Ref,class Ptr>struct list_iterator{typedef ListNode<T> Node;typedef list_iterator<T,Ref,Ptr> iterator;//节点指针Node* _node;};

这个类里面封装的是节点的指针,所以它唯一的成员变量就是Node.*

注意

这里的模板有三个参数,为什么呢?
首先T是节点数据的类型,这个没问题.
但是其他两个呢?

Ref是引用,Ptr是指针.这样子写是为了能生成多种引用T&,和T.*
当我们需要修改这个数据是我们直接传T&.如果我们不允许别人修改数据时,传const T&,让别人只能读.不能修改.
其实还有另一种解决方法,copy这个类,把这个类改成const版本的.但是这样会造成代码冗余.

构造迭代器

		//list_iterator(Node* node):_node(node){}

写了这个,我们就可以传一个节点的指针来构造迭代器

解引用*迭代器

		Ref operator*(){return _node->val;}

Ref是T& / const T&
我们这里要模拟的是vector中T*的功能,解引用取得数据,所以返回节点中的数据

迭代器->

		Ptr operator->(){return &_node->val;}

Ptr是T / const T
我们这里要模拟的是指针中->的功能,所以要传数据T的地址.

在调用上,我们假设有一个类A,里面有两个值a1和a2,我们用这个类来充当节点中的数据val
it->是调用it.operator->(),返回的是一个T.
it.operator->() ->a1 才能取到a1

为了美观,编译器会帮我们减少一个箭头 变成 it->_a1

	struct A{int _a1, _a2;A(int a1 = 0, int a2 = 0):_a1(a1),_a2(a2){}};void TestList2(){list<A> lt;A a = { 3,3 };lt.push_back(a);lt.push_back(A{2,2});lt.push_back({1,1});list<A>::iterator it = lt.begin();while (it != lt.end()){/*cout << *it << " ";*/cout << it->_a1 << " "<< it->_a2;cout << endl;//it.operator->() ->a1//val* --> T*it++;}cout << endl;}

迭代器++

		//前置++  ++i;iterator& operator++(){_node = _node->next;return *this;}//后置++  i++;iterator operator++(int){iterator tmp(_node);_node = _node->next;return tmp;}

迭代器- -

		//--iiterator& operator--(){_node = _node->prev;return *this;}//i--iterator operator--(int){iterator tmp(_node);_node = _node->prev;return tmp;}

判断两个迭代器是否相等

		bool operator==(const iterator& it){return _node == it._node;}bool operator!=(const iterator& it){return _node != it._node;}

链表

template<class T>class list{public://调用可读可写的迭代器typedef list_iterator<T,T&,T*> iterator;//调用只能读,不能修改的迭代器typedef list_iterator<T, const T&,const T*> const_iterator;typedef ListNode<T> Node;private:Node* _head;size_t _size;};

链表里面有两个成员变量,一个作为头节点,一个计算节点的个数

empty_init

这个函数的功能和构造函数一样,写出来是为了后面进行复用.

		void empty_init(){_head = new Node;_head->next = _head;_head->prev = _head;_size = 0;}

构造

复用empty_init

		list(){empty_init();}

拷贝构造

list T2(T1)
初始化T2,然后把T1的值都塞到后面

		list(const list<T>& T1){empty_init();for (auto& e : T1){push_back(e);}}

swap

T2.swap(T1)
交换两个链表

		void swap(const list<T>& T1){std::swap(_head, T1._haed);std::swap(_size, T1._size);}

operator=

这里运用了一个很巧妙的写法,把传过来的值拷贝构造list T1,然后将T1和*this交换
直接白嫖编译器的成果(拷贝构造),纯纯资本家

		const list<T>& operator=(list<T> T1){swap(T1);return *this;}

begin和end

begin返回头节点的下一个,end返回头节点.因为容器底层实现,遍历等都是左闭右开[ )

		const_iterator begin() const{return _head->next;}const_iterator end() const{return _head;}iterator begin() {return _head->next;}iterator end() {return _head;}

insert

注意:在链表中,我们的节点都需要自己new出来,因为链表不是一个连续的空间,没有办法直接开好.要一个个自己搞
pos里面存储的节点指针才是我们需要的

		// prev  tmp  nextvoid insert(iterator pos, const T& val){//new一个用数据val开辟出来的节点Node* tmp = new Node(val);Node* prev = pos._node->prev;Node* next = pos._node;prev->next = tmp;tmp->prev = prev;tmp->next = next;next->prev = tmp;_size++;}

push_back

复用insert尾插

		void push_back(const T& val){insert(end(), val);}

push_front

复用insert头插

		void push_front(const T& val){insert(begin(), val);}

erase

注意:delete要删除自定义类型要调用析构函数,我们这里要删除的是节点(指针),而不是迭代器
不能delete pos,迭代器只有访问节点的功能,不能管理节点

		iterator erase(iterator pos){Node* cur = pos._node;Node* prev = pos._node->prev;Node* next = pos._node->next;prev->next = next;next->prev = prev;//delete cur;_size--;return next;}

pop_back

复用erase,注意要删除的不是头节点,而是头节点的前一个,也就是存储有效数据的最后一个
所以–end(),改好使用我们之前写的迭代器–.

		void pop_back(){erase(--end());}

pop_front

		void pop_front(){erase(begin());}

size

		size_t size(){return _size;}

empty

		bool empty(){return _size == 0;}

clear

删除掉除头节点之外的其他节点

		void clear(){iterator it = begin();while (it != end()){it = erase(it);}}

析构

在clear的前提下删除头节点

		~list(){clear();delete _head;_head = nullptr;}
文章来源:https://blog.csdn.net/2301_76886465/article/details/138157364
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.ppmy.cn/news/1441756.html

相关文章

PHP 错误 Unparenthesized `a ? b : c ? d : e` is not supported

最近在一个新的服务器上测试一些老代码的时候得到了类似上面的错误&#xff1a; [Thu Apr 25 07:37:34.139768 2024] [php:error] [pid 691410] [client 192.168.1.229:57183] PHP Fatal error: Unparenthesized a ? b : c ? d : e is not supported. Use either (a ? b : …

Docker从无到有

主要为windows下docker的安装与使用~ 初始Docker Docker理解 对于docker的加简介&#xff0c;我们可以官网获取它的概念&#xff0c;接下来就从什么是docker、为什么要使用docker以及它的作用来进行一个快速入门 前提&#xff1a;项目在发布时&#xff0c;不仅需要其jar包同…

static为什么不能修饰String类

在Java中&#xff0c;static 关键字用于修饰类成员&#xff08;字段、方法、内部类&#xff09;以及代码块&#xff0c;它主要表示这些成员或代码块与类本身关联&#xff0c;而不是与类的实例关联。当你提到 static 不能修饰 String 类时&#xff0c;我猜你可能是在思考为什么 …

软考之零碎片段记录(二十七)+复习巩固(十三、十四)

学习 1. 案例题 涉及到更新的。肯能会是数据流的终点E, P, D 数据流转。可能是 P->EP->D(数据更新)P->P(信息处理)D->P(提取数据信息) 2. 案例2 补充关系图时会提示不增加新的实体。则增加关联关系 3. 案例3 用例图 extend用于拓展&#xff0c;当一个用例…

网络攻击日益猖獗,安全防护刻不容缓

“正在排队登录”、“账号登录异常”、“断线重连”......伴随着社交软件用户的一声声抱怨&#xff0c;某知名社交软件的服务器在更新上线2小时后&#xff0c;遭遇DDoS攻击&#xff0c;导致用户无法正常登录。在紧急维护几小时后&#xff0c;这款软件才恢复正常登录的情况。 这…

conda 与 pip 工具笔记

前言 conda与pip是Python开发中常用的两种工具&#xff0c;conda本质是环境、包管理工具&#xff0c;pip是包管理工具&#xff0c;两者的功能有一定的重叠。本文主要记录开发工作中与两者相关的使用说明与注意事项。 推荐用conda创建隔离的虚拟环境&#xff0c;用pip进行包安…

【综述】DSP处理器芯片

文章目录 TI DSP C2000系列 TMS320F28003X 典型应用 开发工具链 参考资料 TI DSP TI C2000系列 控制领域 TI C5000系列 通信领域 TI C6000系列 图像领域 C2000系列 第三代集成了C28浮点DSP内核&#xff0c;采用了65nm工艺&#xff08;上一代180nm&#xff09; 第四代正在…

Spring事务回滚核心源码解读

记一次Springboot事务超时不回滚的分析过程 在Springboot中&#xff0c;我用的xml进行事务管理&#xff0c;DataSourceTransactionManager作为事务管理器&#xff0c;配置了事务控制在Service层&#xff1b;在事务管理器中&#xff0c;配置了defaultTimeout事务超时时间为5秒&…