c++模拟实现list——详讲双链表--链表

news/2024/9/23 7:28:16/

在C语言中我们已经模拟实现了list，现在对比c++看看二者的区别

                                            双链表————详讲

个人博客主页：

个人主页

个人码云

码云代码

文章目录

  • 目录

    文章目录

    ​编辑

    前言

    一、list是什么？

    二、list的使用

    三、模拟实现list和搭建list的结构

    1.节点结构

    2.迭代器的详讲（这是和vector的区别）

    3.list基础结构

    4.修改器 

     

    四、测试list

    总结

链表就像这个火车

前言

1. list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。

2. list的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向 其前一个元素和后一个元素。

3. list与forward_list非常相似：最主要的不同在于forward_list是单链表，只能朝前迭代，已让其更简单高 效。

4. 与其他的序列式容器相比(array，vector，deque)，list通常在任意位置进行插入、移除元素的执行效率 更好。

5. 与其他序列式容器相比，list和forward_list最大的缺陷是不支持任意位置的随机访问，比如：要访问list 的第6个元素，必须从已知的位置(比如头部或者尾部)迭代到该位置，在这段位置上迭代需要线性的时间 开销；list还需要一些额外的空间，以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这 可能是一个重要的因素)

一、list是什么？

list就是带头双向链表，头节点存有链表的最后一个节点的地址和第一个节点的地址（链表的物理空间是不连续的，每一个节点的物理空间都是独立的），每一个节点中都存有上一个节点的地址和下一个节点的地址。

二、list的使用

list中的接口比较多，此处类似，只需要掌握如何正确的使用，然后再去深入研究背后的原理，已达到可扩展 的能力。以下为list中一些常见的重要接口。

 

 

 

 

 

#include <iostream>
#include <list>
#include <vector>
#include <algorithm>
using namespace std;#include <time.h>void test_list1()
{
//定义链表和插入数据list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);//迭代器的遍历list<int>::iterator it = lt.begin();while (it != lt.end()){cout << *it << " ";++it;}cout << endl;for (auto e : lt){cout << e <<" ";}cout << endl;//查找节点插入数据list<int>::iterator pos = find(lt.begin(), lt.end(), 3);if (pos != lt.end()){lt.insert(pos, 30);}for (auto e : lt){cout << e << " ";}cout << endl;
}

这里的迭代器的使用和vector一样但是这两个迭代器底层有着非常大的差距 ，在下面的模拟实现中会非常细致的讲解

思考：pos1++和pos2++的区别，这两个指针哪一个可以找到下一个元素的地址？？？

提示：曾经的顺序表和链表的关系。

void test_list2()
{list<int> lt;lt.push_back(10);lt.push_back(2);lt.push_back(5);lt.push_back(3);lt.push_back(4);lt.push_back(4);lt.push_back(6);lt.push_back(4);lt.push_back(0);for (auto e : lt){cout << e << " ";}cout << endl;lt.sort();// 迭代器功能分类// 1、单向  ++// 2、双向  ++  --  // 3、随机  ++  --  +  -//sort(lt.begin(), lt.end());for (auto e : lt){cout << e << " ";}cout << endl;
}

 

三、模拟实现list和搭建list的结构

1.节点结构

代码如下（示例）：

template<class T>//用到了类模板，由于我们想要插入任意类型的数据
struct list_node
{list_node<T>* _next;list_node<T>* _prev;T _data;list_node(const T& x = T())//对成员的默认初始化，这个也是一个匿名构造。:_next(nullptr)//初始化时将节点的下一个节点个下一个节点都置空, _prev(nullptr), _data(x)//插入x{}
};

1.在c语言中，结构体用的是struct，而在c++中我们也可以使用，它和calss相似，如果在一个类里面不需要区分共有成员和私有成员，我们就可以用struct。因为都是自定义类型所以我们需要对它进行成员的初始化。

2.在这个节点中我们存在着后面对成员的访问权限问题，所以我们选择使用struct。

2.迭代器的详讲（这是和vector的区别）

代码如下（示例）：

// 1、迭代器要么就是原生指针
// 2、迭代器要么就是自定义类型对原生指针的封装，模拟指针的行为
template<class T, class Ref, class Ptr>//类模板可以有多个参数，T是原生类型，也就是普通类型
//ref是const类型，不可进行修改；ptr是指针类型。
struct __list_iterator
{typedef list_node<T> node;typedef __list_iterator<T, Ref, Ptr> self;node* _node;__list_iterator(node* n):_node(n){}Ref operator*()//对*的重载，返回为const类型。{return _node->_data;}Ptr operator->()//对->的重载，->用在对地址的访问，也就是见引用node地址处的date{return &_node->_data;}self& operator++()//这里的++是前置++，返回的类型是节点类型，而不是节点的指针，在C语言中是一个地址{_node = _node->_next;return *this;}self operator++(int)//后置++，+了一个int类型进行对前置++的区分{self tmp(*this);_node = _node->_next;return tmp;}self& operator--(){_node = _node->_prev;return *this;}self operator--(int){self tmp(*this);_node = _node->_prev;return tmp;}bool operator!=(const self& s){return _node != s._node;}bool operator==(const self& s){return _node == s._node;}
};

1.类模板中提到过，一个模板可以有多个模板参数，每一个模板可以控制某一种类型。

2.我们的类模板功能非常强大，到我们想要写一个类，但是这个类要写两者类型时，我们需要写两个类出来，但是用了模板我们只需要加一个模板参数即可；

3.“->”用于地址访问和见引用，而“."用于类的成员访问，二者都是见引用的作用。

template<class T>class list{typedef list_node<T> node;public:typedef __list_iterator<T, T&, T*> iterator;typedef __list_iterator<T, const T&, const T*> const_iterator;
iterator begin()
{//iterator it(_head->_next);//return it;return iterator(_head->_next);
}const_iterator begin() const
{return const_iterator(_head->_next);
}iterator end()
{return iterator(_head);
}const_iterator end() const
{//iterator it(_head->_next);//return it;return const_iterator(_head);
}

因为在迭代器中我们的”*“重载即用了普通类型，也用了const类型，所以我们单独给它一个名字Ref，当我们用const类型迭代器时，传递过来的模板参数是const。这是*重载就是const类型。 

3.list基础结构

template<class T>
class list
{typedef list_node<T> node;
public:typedef __list_iterator<T, T&, T*> iterator;typedef __list_iterator<T, const T&, const T*> const_iterator;list(const list<T>& lt)//拷贝构造{empty_init();list<T> tmp(lt.begin(), lt.end());swap(tmp);}	void empty_init(){_head = new node;_head->_next = _head;_head->_prev = _head;}list()//默认构造{empty_init();}template <class Iterator>list(Iterator first, Iterator last)//区间拷贝构造{empty_init();while (first != last){push_back(*first);++first;}~list(){clear();delete _head;_head = nullptr;}private:node* _head;};

4.修改器 

 

void swap(list<T>& tmp)//交换两个节点
{std::swap(_head, tmp._head);
}
void clear()//清空内容
{iterator it = begin();while (it != end()){//it = erase(it);erase(it++);}
}
void push_back(const T& x)//尾插
{/*node* tail = _head->_prev;node* new_node = new node(x);tail->_next = new_node;new_node->_prev = tail;new_node->_next = _head;_head->_prev = new_node;*/insert(end(), x);
}
void push_front(const T& x)//头插
{insert(begin(), x);
}void pop_back()//尾删
{erase(--end());
}void pop_front()//头删
{erase(begin());
}void insert(iterator pos, const T& x)//任意位置插入
{node* cur = pos._node;node* prev = cur->_prev;node* new_node = new node(x);prev->_next = new_node;new_node->_prev = prev;new_node->_next = cur;cur->_prev = new_node;
}iterator erase(iterator pos)//任意位置删除
{assert(pos != end());node* prev = pos._node->_prev;node* next = pos._node->_next;prev->_next = next;next->_prev = prev;delete pos._node;return iterator(next);
}

有了insert函数，我们就不需要push_back和push_front函数了，erase也是； 

四、测试list

	void test_list1(){const list<int> lt1;const int n = 10;//n = 11;list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);// int*list<int>::iterator it = lt.begin();while (it != lt.end()){(*it) *= 2;cout << *it << " ";++it;}cout << endl;for (auto e : lt){cout << e << " ";}cout << endl;print_list(lt);}struct AA{int _a1;int _a2;AA(int a1 = 0, int a2 = 0):_a1(a1), _a2(a2){}};void test_list2(){list<AA> lt;lt.push_back(AA(1, 1));lt.push_back(AA(2, 2));lt.push_back(AA(3, 3));// AA* ptrlist<AA>::iterator it = lt.begin();while (it != lt.end()){//cout << (*it)._a1 << ":" << (*it)._a2 << endl;		cout << it->_a1 << ":" << it->_a2 << endl;//cout << it.operator->()->_a1 << ":" << it.operator->()->_a1 << endl;++it;}cout << endl;}void test_list3(){list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);for (auto e : lt){cout << e << " ";}cout << endl;auto pos = lt.begin();++pos;lt.insert(pos, 20);for (auto e : lt){cout << e << " ";}cout << endl;lt.push_back(100);lt.push_front(1000);for (auto e : lt){cout << e << " ";}cout << endl;lt.pop_back();lt.pop_front();for (auto e : lt){cout << e << " ";}cout << endl;}void test_list4(){list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);for (auto e : lt){cout << e << " ";}cout << endl;lt.clear();for (auto e : lt){cout << e << " ";}cout << endl;lt.push_back(10);lt.push_back(2);lt.push_back(3);lt.push_back(40);for (auto e : lt){cout << e << " ";}cout << endl;}void test_list5(){list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_back(5);for (auto e : lt){cout << e << " ";}cout << endl;list<int> lt2(lt);for (auto e : lt2){cout << e << " ";}cout << endl;list<int> lt3;lt3.push_back(10);lt3.push_back(20);lt3.push_back(30);for (auto e : lt3){cout << e << " ";}cout << endl;lt2 = lt3;for (auto e : lt2){cout << e << " ";}cout << endl;for (auto e : lt3){cout << e << " ";}cout << endl;}

总结

迭代器中的类模板

修改器的insert和erase

了解list的基本结构


http://www.ppmy.cn/news/1431641.html

相关文章

Qt 集成VTK

Qt 集成VTK

Qt hello | 专注于Qt的技术分享平台 一&#xff0c;需求集成VTK环境到Qt中 二&#xff0c;步骤 下载vtk源码&#xff0c;并使用cmake 结合vs2019编辑成dll库。GitHub - Kitware/VTK: Mirror of Visualization Toolkit repositoryQt工程引入&#xff0c;库比较多&#xff0c;…
阅读更多...
java锁常识

java锁常识

AQS框架 AQS&#xff08;AbstractQueuedSynchronizer&#xff09;是 Java 中用于构建锁和同步器的基础框架。它提供了一种实现同步器的方式&#xff0c;使得开发者可以基于 AQS 构建各种类型的同步工具&#xff0c;如独占锁、共享锁、信号量等。 AQS 主要基于 FIFO 队列&…
阅读更多...
Java 基础：工厂方法模式

Java 基础：工厂方法模式

工厂方法模式&#xff08;Factory Method Pattern&#xff09;是一种创建型设计模式&#xff0c;它提供了一个创建对象的通用接口&#xff0c;但将实际创建逻辑推迟到子类中实现。这种模式允许客户端使用抽象接口来创建特定类型的对象&#xff0c;而无需了解具体的实现细节。以…
阅读更多...
【后端】python深度学习的详细指引

【后端】python深度学习的详细指引

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 前言一、什么是深度学习二、python深度学习的详细指引1. 确定学习目标和项目2. 学习基础知识3. 选择合适的深度学习框架4. 学习深度学习理论5. 实践项目6. 深入学习…
阅读更多...
05_Qt资源文件添加

05_Qt资源文件添加

Qt资源文件添加 Qt 资源系统是一个跨平台的资源机制&#xff0c;用于将程序运行时所需要的资源以二进制的形式存储于可执行文件内部。如果你的程序需要加载特定的资源&#xff08;图标、文本翻译等&#xff09;&#xff0c;那么&#xff0c;将其放置在资源文件中&#xff0c;就…
阅读更多...
CSS基础：浮动（float）的3种方式，清除浮动3种方式的详解

CSS基础：浮动（float）的3种方式，清除浮动3种方式的详解

你好&#xff0c;我是云桃桃。 一个希望帮助更多朋友快速入门 WEB 前端的程序媛。 云桃桃-大专生&#xff0c;一枚程序媛&#xff0c;感谢关注。回复 “前端基础题”&#xff0c;可免费获得前端基础 100 题汇总&#xff0c;回复 “前端工具”&#xff0c;可获取 Web 开发工具合…
阅读更多...
智能合约：概念与特点（了解什么是智能合约以及它的特点，如自动执行、不可篡改和可信任）

智能合约：概念与特点（了解什么是智能合约以及它的特点，如自动执行、不可篡改和可信任）

1.自动执行 智能合约通过预定义的代码和规则&#xff0c;在满足特定条件时自动执行。无需第三方介入&#xff0c;合约中的操作将在预定条件满足时自动触发。 2.不可篡改 智能合约的代码一旦部署在区块链上&#xff0c;便不可更改。这意味着合约一旦被创建&#xff0c;其中的规则…
阅读更多...
基于ssm冀中工程技师校园网站设计与实现论文

基于ssm冀中工程技师校园网站设计与实现论文

摘 要 使用旧方法对冀中工程技师学院网站的信息进行系统化管理已经不再让人们信赖了&#xff0c;把现在的网络信息技术运用在冀中工程技师学院网站的管理上面可以解决许多信息管理上面的难题&#xff0c;比如处理数据时间很长&#xff0c;数据存在错误不能及时纠正等问题。这次…
阅读更多...
最新文章

Copyright @ 2022~2023