热门标签
热门文章
- 1Stable Diffusion 安装教程_stable diffusion·中 python安装在哪里
- 2Stable Diffusion 模型分享：Inkpunk Diffusion（动漫、墨水朋克）
- 3【git】TortoiseGit图标不显示 及 文件夹中.git文件夹不显示_tortoisegit文件夹没有图标
- 4Github 上传、下载过慢的解决方案_githubdesktop上传慢
- 5探秘DataV：可视化神器，数据洞察新体验
- 6# 我实践：搭建轻量git服务器的两个方案
- 7Python 使用轻量级 Flask 框架搭建 Web 服务器详细教程（基础篇）_flask搭建web服务器
- 8ELK日志采集系统搭建
- 9科研难点：三线表的制作与调整
- 10信息系统项目管理师证书有什么用？_信息系统管理工程中级有什么用
当前位置: article > 正文
c++中的链表list的模拟实现
作者：羊村懒王 | 2024-05-02 12:30:13
赞
踩
c++中的链表list的模拟实现
拖更了半个月，我终于来填c++的坑啦。上次我们说的vetcor不知道小伙伴还记得多少呢？今天我们要讲list的模拟实现。
目录
架构
我们之前也写过c语言版本的链表，当时很麻烦，还要传二级指针。但是现在不用了引用就能解决。我们先把大体的架构搭出来。
结点
list是一个个的结点指针链接，而且我们看手册的时候，会发现ist是一个双向带头的链表。所以我们先写节点的代码加粗样式。
template<class T> struct ListNode { //为什么要用struct？其实用class也ok，但是要整个public，因为节点我希望你可以随时申请，所以不能弄成私有。 ListNode(const T& val=T()) :_prev(nullptr) ,_next(nullptr) ,data(val) { } ListNode<T>* _prev; //为什么是ListNode<T>*的指针呢？因为我们将来要指向 //ListNode<T>类型的节点。 ListNode<T>* _next; T data; };
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
list表的结构
我们也说了是双向带头链表，所以list一定要有头结点。
template<class T>
class list
{
public:
typedef ListNode<T> Node;
private:
Node* _head;//头结点是一个节点指针类型。
size_t _size;//因为库中有size这个接口，这里存一个会方便一点。
};
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
构造函数
在我们之前实现过得带头双向链表，在刚开始的时候，就是对头结点进行处理，让头结点的前后指针指向自己。
list()
{
_head = new Node;//给头一个空间
_head->_prev = _head;
_head->_next = _head;
_size = 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
尾插push_back()
尾插，我们很熟悉了。就是先new出一个节点的大小，然后把这个节点连接到链表的尾部。如图：
void push_back(const T& val)
{
Node* node = new Node(val);//申请节点
Node* tail = _head->_prev;//如何找到4？是_head->prev！保存起来方便我们使用。
node->_prev = tail;//链接
node->_next = _head;
tail->_next = node;
_head->_prev = node;
_size++;//修改size
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
尾删pop_back()
尾删也是老朋友了。话不多说如图：
简单叙述过程：就是先找到尾巴，然后保存一起来(方便我们删除)。然后将指针链接到尾删的前一个值。
void pop_back()
{
Node* tail = _head->_prev;//保存
_head->_prev = tail->_prev;//更改指向
tail->_prev->_next = _head;
delete tail;//删除节点
_size--;//别忘了修改个数
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
计算个数：size()
这个就很简单了，因为我们内置了个数，所以直接返回就好了。
size_t size()
{
return _size;
}
- 1
- 2
- 3
- 4
判断空empty()
bool empty()
{
return _size == 0;
}
- 1
- 2
- 3
- 4
※迭代器问题
链表的迭代器很麻烦，不像vector那样用下标访问就可以的我们先把迭代器的主体写出来，分析一下，我们都需要什么吧。
bit::list<int>::const it = lt2.begin();
while (it != lt2.end())
{
std::cout << *it << " ";
it++;
}
- 1
- 2
- 3
- 4
- 5
- 6
我们平时访问数据的时候就这些，例如：迭代器本身、*星号、begin()、end()、自增++。那怎么写呢？
普通迭代器
问题：迭代器本身怎么写，还用T* 吗？写在list中码？(一定要思考这个问题！)
答案：不不不，我问你的自增，你在增谁？增加的list还是迭代器？我们要写operator++()，你一定要明白是谁在++。如果你把迭代器写到list中，你operator++()自增的是谁？一定要把这个问题想清楚。
自增的迭代器本身。那么我们的自增就不能写到list中，也就表示迭代器不能写在list中。那么我们就需要另外写一个类封装了。OK！开写！
迭代器主体
我们要遍历这个list链表的时候，我们一定要有这个地方的节点指针，我们才能访问这里的数据对吧，所以里面的成员变量是Node* _node;
template<class T>
class List_Iterator
{
public:
typedef ListNode<T> Node;
Node* _node;
List_Iterator(Node* node)
:_node(node)
{}
};
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
begin()和end()
begin()和end()多好写，begin()是返回数据的开始和end()返回头结点(有效数据的下一个)。
问题：你写在哪？list类？还是iterator类？
答：思考一下，你的数据在哪？你的数据在list 里面对吧，我要访问遍历数据，我去哪里拿数据？list中，那么你的begin()和end()一定不能写在iterator。begin()和end()应该写在list中。
template<class T> class list { public: typedef ListNode<T> Node; iterator begin() { //这里存在单参数构造函数的隐式类型转换 //按道理 return iterator(_head->next); //应该是这样的，匿名对象，但是单参数的构造函数可以进行隐式类型转换。 return _head->_next; } iterator end() { return _head; } private: Node* _head;//头结点是一个节点指针类型。 size_t _size;//因为库中有size这个接口，这里存一个会方便一点。 };
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
operator*()
因为我们遍历一般都是要打印出它的值，所星号也是必不可少的。星号表示解压用。那么我们只需要返回当前节点的值就可以了。
T& operator* ()
{
return _node->data;
}
- 1
- 2
- 3
- 4
前置++ operator++()
自增很简单，我们只需要下一个节点的指针就好，那么我们怎么找到下一个节点呢？是不是当前节点的_next?那就更简单了。
List_Iterator<T>& operator++()
{
//this->_node= this->_node->_next;
_node= _node->_next;
return *this;
}
- 1
- 2
- 3
- 4
- 5
- 6
后置++ operator++(int)
后置++，就是我们创建一个临时变量，然后返回临时变量，但是让实际已经指向下一个节点了。注：不能返回引用，因为是临时变量。
List_Iterator<T> operator++(int)
{
List_Iterator<T> tmp(*this);
_node = _node->_next;
return tmp;
}
- 1
- 2
- 3
- 4
- 5
- 6
前置-- operator–()
为什么要重载自减呢？是因为有些地方我们还是有需要的，所以就直写了。
List_Iterator<T> & operator--()
{
_node= _node->_prev;
return *this;
}
- 1
- 2
- 3
- 4
- 5
后置-- operator–(int)
List_Iterator<T> operator--(int)
{
Self tmp(*this);
_node = _node->_prev;
return tmp;
}
- 1
- 2
- 3
- 4
- 5
- 6
重载不等于 operator!=(const Self& rhs)
问题：在比较的时候，我们比的是节点指针还是数值呢？
答：节点指针！数值可能重复。
bool operator!=(const Self& rhs )
{
return rhs._node != _node;
}
- 1
- 2
- 3
- 4
重载箭头 operator->()
为什么要重载operator->？我们一直用int内置类型来作为样例，这没有问题，但是我想问你，你的list只存int吗？没有自定义类型吗？如果我希望能存一个student类呢？可能你说(*it).成员变量也可以啊，但是你觉得方便吗？所以我们要重载->。
箭头的运算符重载：
从图上我们能发现，他隐藏了一个箭头，他应该是it.operator->()->_a1;但是事实上只有意见箭头，就表明了，他隐藏了一个箭头。
T* operator->()
{
return &_node->data;
}
- 1
- 2
- 3
- 4
const迭代器问题
以上，我们用的都是普通的迭代器，那么const迭代器怎么写呢？你会说，我知道了！只要让他不改变不就好了？OK！说干就干。显示就是，依然改了，并没有用。
解决方法一：创建新的类。
问题就出在了你迭代器本身，你的返回值依然是普通的，我依然可以改。那你突然灵光一现，我在写一个const_ListIterator类就好了！好说干就干。你用了一下，真好用。但是你有没有发现代码很冗余？唯独只有operator*()和operator->()的返回值改变了，因为在拿取值的时候，我们要返回const类型的。
template<class T> class List_ConstIterator { public: typedef ListNode<T> Node; typedef List_ConstIterator<T> Self; Node* _node; List_ConstIterator(Node* node) :_node(node) {} //前置++ Self& operator++() { _node = _node->_next; return *this; } //后置++ Self operator++(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& rhs) { return rhs._node != _node; } bool operator==(const Self& rhs) { return _node == rhs._node; } const T& operator* () { return _node->data; } const T* operator->() { return &_node->data; } };
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
解决方法二：模板
我们上面也说只是两个成员函数的返回类型不同，那么我们在处理返回类型不同的时候怎么做的呢？对！就是模板！模板是不是可以传不同类型呀？那么我们就只需要改一下。
list类中：
template<class T ,class Ref ,class Ptr> class List_Iterator { public: typedef ListNode<T> Node; typedef List_Iterator< T, Ref, Ptr> Self; Node* _node; List_Iterator(Node* node) :_node(node) {} //前置++ Self& operator++() { _node= _node->_next; return *this; } //后置++ Self operator++(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& rhs ) { return rhs._node != _node; } bool operator==(const Self& rhs) { return _node == rhs._node; } Ptr operator->() { return &_node->data; } Ref operator* () { return _node->data; } };
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
在某个位置前插入 insert()
库中给我们了三种，我们只实现第一种。需要迭代器类型的pos和 T val。刚好迭代器问题我们刚刚解决。
连接方式，如图：
iterator insert(iterator pos, const T& val) { //我写的不美观 Node* node = new Node(val); Node* tmp=pos._node->_prev; tmp->_next = node; node->_prev = tmp; node->_next = pos._node; pos._node->_prev = node; _size++; return _head; // Node* node = new Node(val); // Node* prev=pos->prev; // node->prev=prev; // node->next=pos; // pos->prev=node; // prev->next=node; // _size++; // return _head }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
删除某位置的值 erase()
这里我们要注意，库中要求返回被删除值的下一个的迭代器。
iterator erase(iterator pos) { //不美观版本 assert(pos != end());//这里我担心有人有人恶意传迭代器，所以就判断了一下。 Node* tmp = pos._node->_prev; tmp->_next = pos._node->_next; pos._node->_next->_prev = tmp; delete pos._node; _size--; return tmp->_next; /*美观版本 Node* cur = pos._node; Node* prev = cur->_prev; Node* next = cur->_next; prev->_next = next; next->_prev = prev; delete cur; return next;*/ }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
清空链表 clear()
注意，我们清空的链表，不需要清头指针，所以直接用迭代器，pop_back()就可以了。
void clear()
{
iterator it = begin();
while (it != end())
{
it = erase(it);
}
_size = 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
拷贝构造
拷贝构造这里有几个问题。
问题1：直接push_back()可以吗？
答：不可以。你的头指针没有初始化，都是空，插入直接空指针访问。所以你需要初始化。
问题2：用我注释部分的迭代器可以吗？
答：不行，如果你传进来是一个const类型的迭代器呢？普通迭代器类型不匹配，除非你用auto。
//lt1(lt2) list(const list<T>& lt) { empty_init();//初始化头结点。 for (auto& e : lt) { push_back(e); } iterator it = lt.begin(); 类型不明确，用范围for更好 //auto it = lt.begin();//这样也可以 //while (it != lt.end()) //{ // push_back(*it); // it++; //} }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
析构函数
释放空间，并且还有头结点！！！有些小伙伴以为只用释放各个数据的节点就可以了，但是头结点也是你开出来的空间啊，所以也要记得释放。
~list()
{
clear();//复用
delete _head;
}
- 1
- 2
- 3
- 4
- 5
问题
如果我什么都写了，只有拷贝构造没有写，下面图代码对吗？
答：不对，因为传值传参回去调用拷贝构造，没有写拷贝构造就是浅拷贝，当函数结束 临时对象会被析构。但是浅拷贝导致本对象被析构，当整体结束的时候会导致二次析构。
实现整体代码
#pragma once #include<iostream> #include<assert.h> namespace bit { template<class T> struct ListNode { ListNode(const T& val=T()) :_prev(nullptr) ,_next(nullptr) ,data(val) { } ListNode<T>* _prev;//为什么是ListNode<T>*的指针呢？因为我们将来要指向 //ListNode<T>类型的节点。 ListNode<T>* _next; T data; }; template<class T ,class Ref ,class Ptr> class List_Iterator { public: typedef ListNode<T> Node; typedef List_Iterator< T, Ref, Ptr> Self; Node* _node; List_Iterator(Node* node) :_node(node) {} //前置++ Self& operator++() { _node= _node->_next; return *this; } //后置++ Self operator++(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& rhs ) { return rhs._node != _node; } Ref operator* () { return _node->data; } bool operator==(const Self& rhs) { return _node == rhs._node; } Ptr operator->() { return &_node->data; } }; //template<class T> //class List_ConstIterator //{ //public: // typedef ListNode<T> Node; // typedef List_ConstIterator<T> Self; // Node* _node; // List_ConstIterator(Node* node) // :_node(node) // {} // //前置++ // Self& operator++() // { // _node = _node->_next; // return *this; // } // //后置++ // Self operator++(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& rhs) // { // return rhs._node != _node; // } // const T& operator* () // { // return _node->data; // } // bool operator==(const Self& rhs) // { // return _node == rhs._node; // } // const T* operator->() // { // return &_node->data; // } //}; template<class T> class list { public: typedef ListNode<T> Node; typedef List_Iterator<T, T&, T*> iterator; typedef List_Iterator<T, const T&, const T*> const_iterator; //typedef List_Iterator<T> iterator; //typedef List_ConstIterator<T> const_iterator; void empty_init() { _head = new Node;//给头一个空间 _head->_prev = _head; _head->_next = _head; _size = 0; } list() { empty_init(); //刚创建一个链表的时候，没有插入任何数据，我们需要让他指向自己 } ~list() { clear(); delete _head; } //lt1(lt2) list(const list<T>& lt) { empty_init(); for (auto& e : lt) { push_back(e); } iterator it = lt.begin(); 类型不明确，用范围for更好 //auto it = lt.begin();//这样也可以 //while (it != lt.end()) //{ // push_back(*it); // it++; //} } void push_back(const T& val) { /*Node* node = new Node(val); Node* tail = _head->_prev; node->_prev = tail; node->_next = _head; tail->_next = node; _head->_prev = node;*/ insert(end(), val); } void pop_back() { /*Node* tail = _head->_prev; _head->_prev = tail->_prev; tail->_prev->_next = _head; delete tail;*/ erase(--end()); } //当我们想使用insert的时候，发现需要迭代器那么我们先实现迭代器，怎么做呢？ iterator begin() { //这里存在单参数构造函数的隐式类型转换 // return _head->_next; } iterator end() { return _head; } const_iterator begin()const { //这里存在单参数构造函数的隐式类型转换 return _head->_next; } const_iterator end()const { return _head; } //目前测试的迭代器没有大碍，那么就写insert iterator insert(iterator pos, const T& val) { //我写的不美观 Node* node = new Node(val); Node* tmp=pos._node->_prev; tmp->_next = node; node->_prev = tmp; node->_next = pos._node; pos._node->_prev = node; _size++; return _head; // Node* node = new Node(val); // Node* prev=pos->prev; // node->prev=prev; // node->next=pos; // pos->prev=node; // prev->next=node; // _size++; // return _head } iterator erase(iterator pos) { //我写的不美观 assert(pos != end()); Node* tmp = pos._node->_prev; tmp->_next = pos._node->_next; pos._node->_next->_prev = tmp; delete pos._node; _size--; return tmp->_next; //老师写的 /*Node* cur = pos._node; Node* prev = cur->_prev; Node* next = cur->_next; prev->_next = next; next->_prev = prev; delete cur; return next;*/ } size_t size() { return _size; } bool empty() { return _size == 0; } void clear() { iterator it = begin(); while (it != end()) { it = erase(it); } _size = 0; } private: Node* _head; size_t _size; }; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
- 117
- 118
- 119
- 120
- 121
- 122
- 123
- 124
- 125
- 126
- 127
- 128
- 129
- 130
- 131
- 132
- 133
- 134
- 135
- 136
- 137
- 138
- 139
- 140
- 141
- 142
- 143
- 144
- 145
- 146
- 147
- 148
- 149
- 150
- 151
- 152
- 153
- 154
- 155
- 156
- 157
- 158
- 159
- 160
- 161
- 162
- 163
- 164
- 165
- 166
- 167
- 168
- 169
- 170
- 171
- 172
- 173
- 174
- 175
- 176
- 177
- 178
- 179
- 180
- 181
- 182
- 183
- 184
- 185
- 186
- 187
- 188
- 189
- 190
- 191
- 192
- 193
- 194
- 195
- 196
- 197
- 198
- 199
- 200
- 201
- 202
- 203
- 204
- 205
- 206
- 207
- 208
- 209
- 210
- 211
- 212
- 213
- 214
- 215
- 216
- 217
- 218
- 219
- 220
- 221
- 222
- 223
- 224
- 225
- 226
- 227
- 228
- 229
- 230
- 231
- 232
- 233
- 234
- 235
- 236
- 237
- 238
- 239
- 240
- 241
- 242
- 243
- 244
- 245
- 246
- 247
- 248
- 249
- 250
- 251
- 252
- 253
- 254
- 255
- 256
- 257
- 258
- 259
- 260
- 261
- 262
- 263
- 264
- 265
- 266
- 267
- 268
- 269
- 270
- 271
- 272
- 273
- 274
- 275
- 276
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/羊村懒王/article/detail/524080
