【C++】List模拟实现
目录
- 💞💞 前言
- 一、什么是List
- 二、Lits模拟实现
- 2.1 List完整实现代码
- 2.2List框架
- ✨ListNode节点
- ✨List类
- 2.3尾插尾删
- 2.4迭代器封装
- ✨尾插尾删测试代码
- ✨const迭代器
- 2.5头插头删
- ✨头插头删测试代码
- 2.6任意位置插入
- 2.7任意位置删除
- ✨任意位置插入删除测试代码
- 2.8清空数据
- 2.9析构函数
- 2.10构造函数
- ✨默认构造
- ✨拷贝构造
- ✨initializer_list构造
- ✨测试代码
- 2.11赋值运算符重载
- ✨赋值运算符重载测试代码
- 三、结语
一、什么是List
C++中的list是一种双向链表（doubly linked list）的实现。它是C++标准库中的一种容器，可以存储一系列元素，并且允许在任意位置插入、删除和访问元素。对于双向链表有疑问的可以点击查看数据结构——带头双向循环链表详解
二、Lits模拟实现
2.1 List完整实现代码
#pragma once
using namespace std;
#include<iostream>
#include<assert.h>
namespace tutu
{
//1.list节点
template<class T>
struct ListNode
{
//默认构造
struct ListNode(const T& val = T())
:_node(val)
,_prev(NULL)
,_next(NULL)
{
}
//成员函数
T _node;
ListNode<T>* _prev;
ListNode<T>* _next;
};
//2.迭代器类
template<class T,class Ref,class Ptr>
struct List_Iterator
{
typedef struct ListNode<T> Node;
typedef List_Iterator<T,Ref,Ptr> self;
Node* _pnode;
//构造函数
List_Iterator(Node* node)
:_pnode(node)
{
}
Ref operator*()const
{
return _pnode->_node;
}
Ptr operator->() const
{
return &_pnode->_node;
}
//前置++
self& operator++()
{
_pnode = _pnode->_next;
return *this;
}
//后置++
self& operator++(int)
{
self tmp(*this);
_pnode = _pnode->_next;
return tmp;
}
//前置--
self& operator--()
{
_pnode = _pnode->_prev;
return *this;
}
//后置--
self& operator--(int)
{
self tmp(*this);
_pnode = _pnode->_prev;
return tmp;
}
bool operator!=(const self& pnode)
{
return !(_pnode == pnode._pnode);
}
bool operator==(const self& pnode)
{
return _pnode == pnode._pnode;
}
};
const迭代器
//template<class T>
//struct Const_List_Iterator
//{
// typedef struct ListNode<T> Node;
// typedef Const_List_Iterator<T> self;
// Node* _pnode;
// //构造函数
// Const_List_Iterator(Node* node)
// :_pnode(node)
// {
// }
// const T& operator*()const
// {
// return _pnode->_node;
// }
// const T* operator->()const
// {
// return &_pnode->node;
// }
// //前置++
// self& operator++()
// {
// _pnode = _pnode->_next;
// return *this;
// }
// //后置++
// self& operator++(int)
// {
// self tmp(*this);
// _pnode = _pnode->_next;
// return tmp;
// }
// //前置--
// self& operator--()
// {
// _pnode = _pnode->_prev;
// return *this;
// }
// //后置--
// self& operator--(int)
// {
// self tmp(*this);
// _pnode = _pnode->_prev;
// return tmp;
// }
// bool operator!=(const self& pnode)const
// {
// return !(_pnode == pnode._pnode);
// }
// bool operator==(const self& pnode)const
// {
// return _pnode == pnode._pnode;
// }
//};
//3.list类
template<class T>
class List
{
public:
typedef struct ListNode<T> Node;
typedef struct ListNode<T>* pNode;
//迭代器
typedef List_Iterator<T,T&,T*> iterator;
//const 迭代器，数据不可被修改，但可++,判断是否相等
typedef List_Iterator<T,const T&,const T*> const_iterator;
iterator begin()
{
return iterator(_listhead->_next);
}
iterator end()
{
return iterator(_listhead);
}
const_iterator begin()const
{
return const_iterator(_listhead->_next);
}
const_iterator end() const
{
return const_iterator(_listhead);
}
void EmptyInit()
{
_listhead = new Node();
_listhead->_prev = _listhead;
_listhead->_next = _listhead;
}
//默认构造
List()
{
EmptyInit();
}
//拷贝构造
List(List<T>& lt)
{
EmptyInit();
for (auto& e : lt)
{
push_back(e);
}
}
//initializer_list
List(initializer_list<T> il)
{
EmptyInit();
for (const auto& e : il)
{
push_back(e);
}
}
//赋值运算符重载
List<T>& operator=(List<T> lt)
{
swap(_listhead,lt._listhead);
return *this;
}
//清空数据
void clear()
{
pNode cur = _listhead->_next;
pNode del = _listhead->_next;
while (cur != _listhead)
{
cur = cur->_next;
delete del;
del = cur;
}
_listhead->_next = _listhead;
_listhead->_prev = _listhead;
}
//析构函数
~List()
{
clear();
//释放哨兵位头节点
delete _listhead;
}
//尾插
void push_back(const T& val = T())
{
/*pNode newnode = new Node(val);
newnode->_prev = _listhead->_prev;
_listhead->_prev->_next = newnode;
newnode->_next = _listhead;
_listhead->_prev = newnode;*/
insert(end(), val);
}
//尾删
void pop_back()
{
/*if (_listhead->_prev != _listhead)
{
pNode tail = _listhead->_prev->_prev;
delete _listhead->_prev;
_listhead->_prev = tail;
tail->_next = _listhead;
}*/
erase(--end());
}
//头插
void push_front(const T& val = T())
{
/*pNode newnode = new Node(val);
_listhead->_next->_prev = newnode;
newnode->_next = _listhead->_next;
newnode->_prev = _listhead;
_listhead->_next = newnode;*/
insert(begin(), val);
}
//头删
void pop_front()
{
/*if (_listhead->_prev != _listhead)
{
pNode head = _listhead->_next->_next;
delete _listhead->_next;
_listhead->_next = head;
head->_prev = _listhead;
}*/
erase(begin());
}
//任意位置前插入
iterator insert(iterator pos, const T& x)
{
pNode newnode = new Node(x);
pNode cur = pos._pnode;
cur->_prev->_next = newnode;
newnode->_prev = cur->_prev;
newnode->_next = cur;
cur->_prev = newnode;
//返回新插入位置的迭代器
return iterator(newnode);
}
//任意位置删除
iterator erase(iterator pos)
{
assert(pos != end());
Node* cur = pos._pnode;
Node* prev = cur->_prev;
Node* next = cur->_next;
prev->_next = next;
next->_prev = prev;
delete cur;
return iterator(next);
}
private:
pNode _listhead;
};
//迭代器测试
void test2()
{
List<int> lt1;
lt1.push_back(1);
lt1.push_back(2);
List<int>::iterator it = lt1.begin();
while (it != lt1.end())
{
cout << *it << endl;
++it;
}
}
void Func(const List<int>& lt)
{
// const iterator const 迭代器不能普通迭代器前面加const修饰
// const 迭代器目标本身可以修改，指向的内容不能修改 类似const T* p
List<int>::const_iterator it = lt.begin();
while (it != lt.end())
{
// 指向的内容不能修改
//*it += 10;
cout << *it << " ";
++it;
}
cout << endl;
}
//尾插尾删
void test3()
{
List<int> lt1;
lt1.push_back(1);
lt1.push_back(2);
lt1.push_back(3);
lt1.push_back(4);
lt1.pop_back();
lt1.pop_back();
List<int>::iterator it = lt1.begin();
while (it != lt1.end())
{
cout << *it << endl;
++it;
}
}
//头插头删
void test4()
{
List<int> lt1;
lt1.push_front(1);
lt1.push_front(2);
lt1.push_front(3);
lt1.push_front(4);
lt1.pop_front();
lt1.pop_front();
lt1.pop_front();
List<int>::iterator it = lt1.begin();
while (it != lt1.end())
{
cout << *it << endl;
++it;
}
}
//任意位置插入删除
void test5()
{
List<int> lt1;
List<int>::iterator it = lt1.begin();
lt1.insert(it, 1);
lt1.insert(it, 2);
lt1.insert(it,3);
it = lt1.begin();
it = lt1.erase(it);
while (it != lt1.end())
{
cout << *it << endl;
++it;
}
}
struct Pos
{
Pos(int a = 100, int b = 100)
:x(a)
, y(b)
{
}
int x;
int y;
};
void test()
{
List<Pos> lt;
lt.push_back(Pos(1,1));
lt.push_back(Pos(2, 2));
lt.push_back(Pos(3, 3));
List<Pos>::iterator it = lt.begin();
while (it != lt.end())
{
cout << it->x << ":" << it->y << endl;
it++;
}
}
//构造函数测试代码
void test6()
{
//默认构造
List<int> lt1;
lt1.push_back(1);
lt1.push_back(2);
lt1.push_back(3);
lt1.push_back(4);
List<int>::iterator it = lt1.begin();
while (it != lt1.end())
{
cout << *it << " ";
++it;
}
cout << endl;
//拷贝构造
List<int> lt2(lt1);
it = lt2.begin();
while (it != lt2.end())
{
cout << *it << " ";
++it;
}
cout << endl;
//initializer_list
List<int> lt3 = { 1,2,3,4 ,5};
it = lt3.begin();
while (it != lt3.end())
{
cout << *it << " ";
++it;
}
}
//赋值运算符重载测试代码
void test7()
{
//默认构造
List<int> lt1;
lt1.push_back(1);
lt1.push_back(2);
lt1.push_back(3);
lt1.push_back(4);
List<int>::iterator it = lt1.begin();
while (it != lt1.end())
{
cout << *it << " ";
++it;
}
cout << endl;
//赋值运算符重载
List<int> lt2 = lt1;
it = lt2.begin();
while (it != lt2.end())
{
cout << *it << " ";
++it;
}
cout << endl;
}
}2.2List框架
✨ListNode节点
该类用来封装一个一个的节点，包括两个指针，一个指针指向前一个节点，另一个指向后一个节点，和一个存放数据的类型：
//1.list节点
template<class T>
struct ListNode
{
//默认构造
struct ListNode(const T& val = T())
:_node(val)
,_prev(NULL)
,_next(NULL)
{
}
//成员函数
T _node;
ListNode<T>* _prev;
ListNode<T>* _next;
};ListNode类中还定义了构造函数，用来初始化数据
因为struct表明这个类里面的成员函数和成员变量都是公有的，所以直接使用struct就行
✨List类
该类包括一个成员变量，是指向第一个节点类的指针，也就是指向哨兵位头节点的指针
//2.list类
template<class T>
class List
{
public:
typedef struct ListNode<T> Node;
typedef struct ListNode<T>* pNode;
private:
pNode _listhead;
};2.3尾插尾删
//尾插
void push_back(const T& val = T())
{
pNode newnode = new Node(val);//开辟新节点，并用val初始化
newnode->_prev = _listhead->_prev;
_listhead->_prev->_next = newnode;
newnode->_next = _listhead;
_listhead->_prev = newnode;
}如下图所示：
在这里插入图片描述
尾插节点，需要将新节点的前一个指针指向最后一个节点也就是
_listhead->_prev，将最后一个节点的下一个指针指向新节点，新节点的下一个指针指向哨兵位头节点，还需要将哨兵位头节点前一个指针指向新节点因为前面的节点ListNode类中创建了构造函数，所以可以用val来初始化数据
//尾删
void pop_back()
{
if (_listhead->_prev != _listhead)//如果有节点
{
pNode tail = _listhead->_prev->_prev;
delete _listhead->_prev;
_listhead->_prev = tail;
tail->_next = _listhead;
}
}
在这里插入图片描述
对于尾删我们需要将倒数第二个节点的下一个指针指向哨兵位头节点以及将哨兵位头节点的下一个指向倒数第二个节点，并且释放掉最后一个节点
2.4迭代器封装
与vector的迭代器直接使用数据指针T*不同，list迭代器如果直接使用指针，由于物理空间位置不连续，是无法使用++，以及！=判断的，所以要将其封装在一个类中，并对其需要使用的运算符进行重载：
//普通迭代器
template<class T>
struct List_Iterator
{
typedef struct ListNode<T> Node;
typedef List_Iterator<T> self;
Node* _pnode;
//构造函数
List_Iterator(Node* node)
:_pnode(node)
{
}
T& operator*()const
{
return _pnode->_node;
}
T* operator->() const
{
return &_pnode->_node;
}
//前置++
self& operator++()
{
_pnode = _pnode->_next;
return *this;
}
//后置++
self& operator++(int)//提供一个参数区分
{
self tmp(*this);
_pnode = _pnode->_next;
return tmp;
}
//前置--
self& operator--()
{
_pnode = _pnode->_prev;
return *this;
}
//后置--
self& operator--(int)
{
self tmp(*this);
_pnode = _pnode->_prev;
return tmp;
}
bool operator!=(const self& pnode)
{
return !(_pnode == pnode._pnode);
}
bool operator==(const self& pnode)
{
return _pnode == pnode._pnode;
}
};因为struct表明这个类里面的成员函数和成员变量都是公有的，所以直接使用struct就行
注意这里operator->返回的是节点里面数据的指针T*，在使用时写一个->即可，为了可读性省略了一个箭头，例如对于下面的类：
struct Pos
{
Pos(int a = 100, int b = 100)
:x(a)
, y(b)
{
}
int x;
int y;
};我们将其存入list中：
void test()
{
List<Pos> lt;
lt.push_back(Pos(1,1));
lt.push_back(Pos(2, 2));
lt.push_back(Pos(3, 3));
List<Pos>::iterator it = lt.begin();
while (it != lt.end())
{
cout << it->x << ":" << it->y << endl;
it++;
}
}就可以通过重载的->来获取数据的指针并通过指针访问其中包含的数据，这里本来应该写两个->，但是为了可读性省略了一个
结果如下：
在这里插入图片描述
使用迭代器时，在list类中typedef成我们平常使用的样子iterator便于统一使用，比较规范
//3.list类
template<class T>
class List
{
public:
typedef struct ListNode<T> Node;
typedef struct ListNode<T>* pNode;
//迭代器
typedef List_Iterator<T> iterator;
iterator begin()
{
return iterator(_listhead->_next);
}
iterator end()
{
return iterator(_listhead);
}
private:
pNode _listhead;
};在return时就可以将节点指针拷贝构造成迭代器返回了
有了迭代器我们就可以遍历打印list里面的数据啦🥳🥳
✨尾插尾删测试代码
//尾插尾删
void test3()
{
List<int> lt1;
lt1.push_back(1);
lt1.push_back(2);
lt1.push_back(3);
lt1.push_back(4);
lt1.pop_back();
lt1.pop_back();
//迭代器遍历
List<int>::iterator it = lt1.begin();
while (it != lt1.end())
{
cout << *it << endl;
++it;
}
}结果如下：
在这里插入图片描述
✨const迭代器
对于const迭代器来说其数据是可以被访问但是不能修改，当然迭代器自身++，–是可以的，所以我们不能简单的直接在迭代器前面+const，在数据前面+const也不行，因为list中的数据不一定是const类型，所以要重新封装一个const迭代器
//const迭代器
template<class T>
struct Const_List_Iterator
{
typedef struct ListNode<T> Node;
typedef Const_List_Iterator<T> self;
Node* _pnode;
//构造函数
Const_List_Iterator(Node* node)
:_pnode(node)
{
}
const T& operator*()const
{
return _pnode->_node;
}
const T* operator->()const
{
return &_pnode->node;
}
//前置++
self& operator++()
{
_pnode = _pnode->_next;
return *this;
}
//后置++
self& operator++(int)
{
self tmp(*this);
_pnode = _pnode->_next;
return tmp;
}
//前置--
self& operator--()
{
_pnode = _pnode->_prev;
return *this;
}
//后置--
self& operator--(int)
{
self tmp(*this);
_pnode = _pnode->_prev;
return tmp;
}
bool operator!=(const self& pnode)const
{
return !(_pnode == pnode._pnode);
}
bool operator==(const self& pnode)const
{
return _pnode == pnode._pnode;
}
};如下图所示const迭代器的数据不能被修改：
在这里插入图片描述
我们发现能够修改数据的只有这两个函数：
const T& operator*()const
{
return _pnode->_node;
}
const T* operator->()const
{
return &_pnode->node;
}所以我们在返回值前面+const修饰其不能被修改即可，因为是const对象使用，所以后面也要+const修饰this
我们发现普通对象的迭代器和const对象使用的迭代器差异非常小，很多代码都是重复的，所以我们可以考虑使用模板来简化代码，代码如下：
template<class T,class Ref,class Ptr>
struct List_Iterator
{
typedef struct ListNode<T> Node;
typedef List_Iterator<T,Ref,Ptr> self;
Node* _pnode;
//构造函数
List_Iterator(Node* node)
:_pnode(node)
{
}
Ref operator*()const
{
return _pnode->_node;
}
Ptr operator->() const
{
return &_pnode->_node;
}
//前置++
self& operator++()
{
_pnode = _pnode->_next;
return *this;
}
//后置++
self& operator++(int)
{
self tmp(*this);
_pnode = _pnode->_next;
return tmp;
}
//前置--
self& operator--()
{
_pnode = _pnode->_prev;
return *this;
}
//后置--
self& operator--(int)
{
self tmp(*this);
_pnode = _pnode->_prev;
return tmp;
}
bool operator!=(const self& pnode)
{
return !(_pnode == pnode._pnode);
}
bool operator==(const self& pnode)
{
return _pnode == pnode._pnode;
}
};因为仅仅有两个函数返回值不一样，所以我们考虑多传两个模板参数，以减少代码的数量，简化代码
template<class T>
class List
{
public:
typedef struct ListNode<T> Node;
typedef struct ListNode<T>* pNode;
//迭代器
typedef List_Iterator<T,T&,T*> iterator;
//const 迭代器，数据不可被修改，但可++,判断是否相等
typedef List_Iterator<T,const T&,const T*> const_iterator;
iterator begin()
{
return iterator(_listhead->_next);
}
iterator end()
{
return iterator(_listhead);
}
const_iterator begin()const
{
return const_iterator(_listhead->_next);
}
const_iterator end() const
{
return const_iterator(_listhead);
}
private:
pNode _listhead;
};2.5头插头删
//头插
void push_front(const T& val = T())
{
pNode newnode = new Node(val);
_listhead->_next->_prev = newnode;
newnode->_next = _listhead->_next;
newnode->_prev = _listhead;
_listhead->_next = newnode;
}//头删
void pop_front()
{
if (_listhead->_prev != _listhead)
{
pNode head = _listhead->_next->_next;
delete _listhead->_next;
_listhead->_next = head;
head->_prev = _listhead;
}
}✨头插头删测试代码
//头插头删
void test4()
{
List<int> lt1;
lt1.push_front(1);
lt1.push_front(2);
lt1.push_front(3);
lt1.push_front(4);
lt1.pop_front();
lt1.pop_front();
lt1.pop_front();
List<int>::iterator it = lt1.begin();
while (it != lt1.end())
{
cout << *it << endl;
++it;
}
}结果如下：
在这里插入图片描述
2.6任意位置插入
//任意位置前插入
iterator insert(iterator pos, const T& x)
{
pNode newnode = new Node(x);//创建新节点，并初始化
pNode cur = pos._pnode;
cur->_prev->_next = newnode;
newnode->_prev = cur->_prev;
newnode->_next = cur;
cur->_prev = newnode;
//返回新插入位置的迭代器
return iterator(newnode);
}有了任意位置插入，就可以在头插和尾插这里实现代码复用：
//头插
void push_front(const T& val = T())
{
insert(begin(), val);
}
//尾插
void push_back(const T& val = T())
{
insert(end(), val);
}2.7任意位置删除
//任意位置删除
iterator erase(iterator pos)
{
assert(pos != end());
Node* cur = pos._pnode;
Node* prev = cur->_prev;
Node* next = cur->_next;
prev->_next = next;
next->_prev = prev;
delete cur;
return iterator(next);
}注意删除任意位置之后，迭代器会失效，所以可以返回新的迭代器，然后使用时重新赋值，这样才行
有了任意位置删除，就可以在头删和尾删这里实现代码复用：
//尾删
void pop_back()
{
erase(--end());
}
```cpp
//头删
void pop_front()
{
erase(begin());
}✨任意位置插入删除测试代码
//任意位置插入删除
void test5()
{
List<int> lt1;
List<int>::iterator it = lt1.begin();
lt1.insert(it, 1);
lt1.insert(it, 2);
lt1.insert(it,3);
it = lt1.begin();
it = lt1.erase(it);//更新迭代器
while (it != lt1.end())
{
cout << *it << endl;
++it;
}
}结果如下：
在这里插入图片描述
我们看到使用erase之后迭代器会失效，所以我们更新了迭代器
2.8清空数据
释放除了哨兵位头节点之外的所有节点，将哨兵位头节点的前后指针都指向自己
//清空数据
void clear()
{
pNode cur = _listhead->_next;
pNode del = _listhead->_next;
while (cur != _listhead)
{
cur = cur->_next;
delete del;
del = cur;
}
_listhead->_next = _listhead;
_listhead->_prev = _listhead;
}2.9析构函数
直接复用clear函数再释放哨兵位头节点即可
//析构函数
~List()
{
clear();
//释放哨兵位头节点
delete _listhead;
}2.10构造函数
无论是哪个构造函数，我们都需要一个哨兵位头节点，所以可以单独写一个函数，用来复用
//哨兵位头节点
void EmptyInit()
{
_listhead = new Node();
_listhead->_prev = _listhead;
_listhead->_next = _listhead;
}✨默认构造
只需一个哨兵位头节点即可
//默认构造
List()
{
EmptyInit();
}✨拷贝构造
//拷贝构造
List(List<T>& lt)
{
EmptyInit();/哨兵位
for (auto& e : lt)
{
push_back(e);
}
}有了哨兵位节点之后就可以遍历lt尾插实现深拷贝了
✨initializer_list构造
和拷贝构造一样，先需要一个哨兵位头节点然后遍历initializer_list，尾插实现构造
//initializer_list
List(initializer_list<T> il)
{
EmptyInit();
for (const auto& e : il)
{
push_back(e);
}
}✨测试代码
//构造函数测试代码
void test6()
{
//默认构造
List<int> lt1;
lt1.push_back(1);
lt1.push_back(2);
lt1.push_back(3);
lt1.push_back(4);
List<int>::iterator it = lt1.begin();
while (it != lt1.end())
{
cout << *it << " ";
++it;
}
cout << endl;
//拷贝构造
List<int> lt2(lt1);
it = lt2.begin();
while (it != lt2.end())
{
cout << *it << " ";
++it;
}
cout << endl;
//initializer_list
List<int> lt3 = { 1,2,3,4 ,5};
it = lt3.begin();
while (it != lt3.end())
{
cout << *it << " ";
++it;
}
}结果如下：
在这里插入图片描述
2.11赋值运算符重载
和vector一样利用形参拷贝，然后交换，利用析构释放之前的list对象，返回交换后的对象
//赋值运算符重载
List<T>& operator=(List<T> lt)
{
swap(_listhead,lt._listhead);
return *this;
}✨赋值运算符重载测试代码
//赋值运算符重载测试代码
void test7()
{
//默认构造
List<int> lt1;
lt1.push_back(1);
lt1.push_back(2);
lt1.push_back(3);
lt1.push_back(4);
List<int>::iterator it = lt1.begin();
while (it != lt1.end())
{
cout << *it << " ";
++it;
}
cout << endl;
//赋值运算符重载
List<int> lt2 = lt1;
it = lt2.begin();
while (it != lt2.end())
{
cout << *it << " ";
++it;
}
cout << endl;
}结果如下：
在这里插入图片描述
三、结语
对于list大部分和前面学习过的vector类似，关键点在于理解list的迭代器的封装以及const迭代器，还有list实现包括了三个类，它们分别都有类模板，容易绕晕，需要好好理解清楚，以上就是今天所有的内容啦~ 完结撒花~ 🥳🎉🎉
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2024-05-31，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
腾讯云开发者
