【C++】list模拟实现（详解）

🕗 发布于 2024-11-25 14:39 c++ 开发语言

本篇来详细说一下list的模拟实现，list的大体框架实现会比较简单，难的是list的iterator的实现。我们模拟实现的是带哨兵位头结点的list。

1.准备工作

为了不和C++库里面的list冲突，我们在实现的时候用命名空间隔开。

//list.h
#pragma once
#include <iostream>
using namespace std;
namespace lyj
{

}

//test.cpp
#include "list.h"
namespace lyj
{
void test1()
{
//后续测试代码
}
}
int main()
{
lyj::test1();
return 0;
}

在list.h的namespace里面实现list的节点，他的节点是一个单独的结构，并且要用类模板。

namespace lyj
{
template<class T>
struct list_node
{
T _data; //存的数据
list_node<T>* _next;//指向后一个节点
list_node<T>* _prev;//指向前一个节点
};
}

再在list.h的namespace里面实现list的类，也要用类模板。

template<class T>
struct list_node
{
T _data; //存的数据
list_node<T>* _next;//指向后一个节点
list_node<T>* _prev;//指向前一个节点
};

template<class T>
class list
{
typedef list_node<T> Node; //换个短的名字
public:
//成员函数

private:
Node* _head;
    size_t _size;//list原本没有，我们自己加的
};

成员变量加一个_size方便我们计算链表结点个数。

list_node类里面还需要一个构造函数。

struct list_node
{
T _data; //存的数据
list_node<T>* _next;//指向后一个节点
list_node<T>* _prev;//指向前一个节点

list_node(const T& data = T()) //给缺省值T()
:_data(data)
,_next(nullptr)
,_prev(nullptr)
{}
};

2.list构造函数

2.1 无参构造/默认构造

在list.h的list类里面实现。

list()
{
_head = new Node;
_head->_next = _head;
_head->_prev = _head;
}

哨兵位头节点，自己指向自己。

3.增删查改操作（1）

3.1 size和empty

前面说过，list里面没有设计这个成员变量，我们自己加上，方便记录个数。

size_t size() const
{
return _size;
}

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

3.2 push_back 尾插

我们要让尾节点的_next指向新节点，哨兵位头结点的_prev指向新节点，新节点的_prev指向原来的尾节点，让新节点的_next指向哨兵位头节点，这样，新节点就成了新的尾节点。

wAAACH5BAEKAAAALAAAAAABAAEAAAICRAEAOw==

编辑

代码实现如下。

void push_back(const T& x)
{
Node* newnode = new Node(x);
Node* tail = _head->_prev;//头结点的前一个就是尾节点
//将新节点连接起来
tail->_next = newnode;
newnode->next = _head;
newnode->_prev = tail;
_head->_prev = newnode;
    ++_size;
}

4.迭代器的实现（重难点）

list部分的迭代器已经不是原生指针了，因为链表空间不连续，对指针++，是+到了下一个连续的地址的位置，但是这个位置不是节点。想要访问数据，也不是简单的解引用。string和vector的迭代器可以直接用原生指针，但是list的结构比较特殊，所以他的迭代器的实现也比较特殊。

所以，我们要用一个类来封装节点的指针。

4.1 list_iterator类

在list.h的namespace里面实现list_iterator类，目前我们已经有3个类了。

template<class T>
struct list_iterator
{

};

struct和class的区别在【C++】类和对象（上）：初识类和对象-CSDN博客的第1点有详细介绍。

类里面我们对解引用运算符（*）和++运算符进行重载。

4.1.1 operator*

template<class T>
struct list_iterator
{
typedef list_node<T> Node; //换个短的名字
Node* _node;

T& operator*() //重载解引用运算符
{
return _node->_data;//返回数据
}
};

解引用运算符重载的返回值是T类型的引用，因为我们需要对数据进行修改。

4.1.2 operator++和operator-- (前置++/--)

Self& operator++() //重载++
{
_node = _node->_next;//加到下一个节点
return *this;//返回自己
}

迭代器++之后还是迭代器，所以返回类型是迭代器自己的类型。

Self& operator--() //重载--
{
_node = _node->_prev;//减到前一个节点
return *this;//返回自己
}

--也是一样。

4.1.3 operator!=和operator==

另外，我们还需要重载!=运算符。

bool operator!=(const Self& s) const
{
return _node != s._node;
}

还可以弄一个==。

bool operator==(const Self& s) const
{
return _node == s._node;
}

4.1.4 迭代器这个类的构造函数

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

4.2 list类里的迭代器实现

在list.h的list类里面实现。

先改个名字，统一一下。

public:
typedef list_iterator<T> iterator;

迭代器的begin是第一个节点的位置。

iterator begin()
{
iterator it(_head->next);
return it;
}

上面的写法是有名对象，我们还可以用匿名对象，如下。

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

还可以走隐式类型转换，因为单参数构造函数支持隐式类型转换，如下。

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

三种写法都可以，任选其一。

迭代器的end是最后一个节点的下一个位置，这里就是哨兵位头节点。

iterator end()
{
return _head;
}

在test.cpp中测试。

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;

5.增删查改操作（2）

5.1 insert

在pos位置之前插入节点。

void insert(iterator pos, const T& x)
{
Node* cur = pos._node;
Node* prev = cur->_prev;
Node* newnode = new Node(x);
//连接起来
newnode->_next = cur;
newnode->_prev = prev;
prev->_next = newnode;
cur->_prev = newnode;
++_size;
}

在test.cpp中测试。

void test2()
{
list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
lt.insert(lt.begin(), 0);//头插0
list<int>::iterator it = lt.begin();
while (it != lt.end())
{
cout << *it << " ";
++it;
}
cout << endl;
}

5.2 头插以及尾插改装

我们实现了insert，push_back尾插就可以套用insert，第一个参数传迭代器end就可以了。

void push_back(const T& x)
{
insert(end(), x);
++_size;
}

push_front就是头插，也可以套用insert，第一个参数传迭代器begin就可以了。

void push_front(const T& x)
{
insert(begin(), x);
++_size;
}

两个一起在test.cpp中测试。

void test3()
{
list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_front(3);
lt.push_front(4);
list<int>::iterator it = lt.begin();
while (it != lt.end())
{
cout << *it << " ";
++it;
}
cout << endl;
}

5.3 erase 删除

把pos位置的数据删除，就是把pos前一个节点和pos后一个节点连接起来。但是我们不可以删除哨兵位头节点，迭代器end是尾节点的下一个节点，就是哨兵位，所以pos不可以是end。

void erase(iterator pos)
{
assert(pos != end());//不可以删哨兵位头节点
Node* prev = pos._node->_prev;//存pos前后节点
Node* next = pos._node->_next;
prev->_next = next;//链接pos前后节点
next->_prev = prev;
delete pos._node;//释放pos节点
--_size;
}

使用assert要包含头文件#include <assert.h>。

在test.cpp中测试。

list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
lt.erase(++lt.begin());//删除第二个节点
list<int>::iterator it = lt.begin();
while (it != lt.end())
{
cout << *it << " ";
++it;
}
cout << endl;

5.4 头删和尾删

实现了erase，头删和尾删就可以复用它。

void pop_back()//尾删
{
erase(--end());//迭代器部分重载过--
}

尾节点是end的前一个节点。

void pop_front()//头删
{
erase(begin());
}

在test.cpp中测试。

list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
lt.pop_front();//头删
lt.pop_back();//尾删
list<int>::iterator it = lt.begin();
while (it != lt.end())
{
cout << *it << " ";
++it;
}
cout << endl;

本次分享就到这里，list还有一部分没有介绍完，我们下次见，拜拜~

原文地址：https://blog.csdn.net/2402_82757055/article/details/143927621

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：贪心算法（2）
下一篇：Edify 3D: Scalable High-Quality 3D Asset Generation 论文解读

windows C#-异步文件访问
可使用异步功能访问文件。通过使用异步功能，你可以调用异步方法而无需使用回调，也不需要跨多个方法或 lambda 表达式来拆分代码。若要使同步代码异步，只需调用异步方法而非同步方法，并向代码中添加几个关
阅读更多2024-11-26
实现一个string的indexof方法，给出时空复杂度估计
文心快码(BaiduComate)是基于百度文心大模型，在研发全流程全场景下为开发者提供辅助建议的智能代码助手。结合百度积累多年的编程现场大数据、外部优秀开源数据，可为开发者生成更符合实际研发场景的优
阅读更多2024-11-26
如何使用Jedis连接Redis
使用Jedis连接redis
阅读更多2024-11-26
SQL注入的那些面试题总结
当php开启gpc或者使用addslashes函数时，单引号被加上反斜杠\'，其中的URL编码为%5C，我们传入%df'，等价于%df%5C'，此时若程序的默认字符集是GBK，mysql用GBK编码时
阅读更多2024-11-26
戴尔 AI Factory 上的 Agentic RAG 搭载 NVIDIA 和 Elasticsearch 向量数据库
戴尔 AI Factory with NVIDIA 是一款全面的端到端 AI 解决方案，旨在简化和加速各行业企业的 AI 采用。目录产品基于一系列戴尔先进的 PowerEdge 服务器构建，并与 NV
阅读更多2024-11-26
【Vscode】不同系统快捷键
1、移动行或选择将当前选定的内容上移或下移一行：Linux / Windows: Alt + Up / Down ArrowMac: Opt + Up / Down Arrow2 、复制行或选择将选定
阅读更多2024-11-26
敏捷开发01：敏捷简史和几种软件开发模型
敏捷简史介绍，几种软件开发模型
阅读更多2024-11-26
Spring Security @PreAuthorize注解
是 Spring Security 的一个注解，用于指定在方法调用前应评估的表达式，以确定调用者是否有权执行该方法。本教程介绍了如何使用 Spring 方法级安全和注解来保护 RestControll
阅读更多2024-11-26
PHP 8.4 重磅发布了
PHP 8.4 提前发布！原计划于2024年11月21日发布的PHP 8.4.0，惊喜地提前至11月19日正式上线，紧随其后的是11月20日发布的PHP 8.4.1。如此高效的发布节奏令人瞩目。本文将
阅读更多2024-11-26
如何开发一个脚手架
通过本文，你应该对如何开发一个脚手架有了一个大概的了解，并且学会了如何使用tsup打包 TypeScript 项目，以及如何发布 npm 包。当然，脚手架的功能远不止这些，还可以实现更多的功能，比如：
阅读更多2024-11-26

【C++】list模拟实现（详解）

1.准备工作

2.list构造函数

2.1 无参构造/默认构造

3.增删查改操作（1）

3.1 size和empty

3.2 push_back 尾插

4.迭代器的实现（重难点）

4.1 list_iterator类

4.1.1 operator*

4.1.2 operator++和operator-- (前置++/--)

4.1.3 operator!=和operator==

4.1.4 迭代器这个类的构造函数

4.2 list类里的迭代器实现

5.增删查改操作（2）

5.1 insert

5.2 头插以及尾插改装

5.3 erase 删除

5.4 头删和尾删

相关文章