目录
0.前言
我们知道，list是一个双向循环链表，所以list的每个节点中需要存在一个指向前一个节点的指针prev、一个指向下一个节点的指针next和一个数据域data
1.节点类
因为list的底层是节点，而节点的底层又是prev、next指针和数据域data，所以我们先将节点封装为一个类，然后再用list类调用节点类。节点类的代码如下：
//定义链表节点
template<class T>
struct ListNode
{
ListNode<T>* _next;
ListNode<T>* _prev;
T _data;
//链表节点构造函数
ListNode(const T& x = T())
:_next(nullptr)
, _prev(nullptr)
, _data(x)
{}2.迭代器类
在string和vector中我们使用迭代器访问数据时需要有这样的操作：
vector<int>::iterator it = l1.begin();
while (it != l1.end())
{
cout << *it << " ";
++it;
}
cout << endl;需要知悉的是，在C++中，为了方便和统一，无论什么类我们大多都采用此方法进行访问，string与vector都是连续的，如此访问必然不会有差错，可是list并不是连续的
我们希望++it就能找到下一个节点，而it解引用（*it）就得到节点里存的data，所以，为了使迭代器能够正常访问，我们在自定义的类中必须实现以下方法：
1. 指针可以解引用，迭代器的类中必须重载operator*()
2. 指针可以通过->访问其所指空间成员，迭代器类中必须重载oprator->()
3. 指针可以++向后移动，迭代器类中必须重载operator++()与operator++(int)
4. 迭代器需要进行是否相等的比较，因此还需要重载operator==()与operator!=()
代码如下：
①普通迭代器
//①普通迭代器 可读可写
template<class T>
struct __list_iterator
{
typedef ListNode<T> Node;
typedef __list_iterator D;
Node* _node;
//迭代器构造函数
__list_iterator(Node* x)
:_node(x)
{}
//重载++
//前置++
D& operator++()//返回迭代器的引用
{
_node = _node->_next;//指向下一个节点
return *this;
}
//后置++
D operator++(int)
{
D tmp(*this);
_node = _node->_next;
return tmp;//返回拷贝之前的值
}
//重载--
//前置--
D& operator--()
{
_node = _node->_prev;
return *this;
}
//后置--
D operator--(int)
{
D tmp(*this);
_node = _node->_prev;
return tmp;
}
//重载解引用
T& operator*()//返回数据的引用
{
return _node->_data;//返回节点里的数据
}
//重载->
T* operator->()
{
return &_node->_data;
}
//重载！=
bool operator !=(const D& s)
{
return _node != s._node;
}
//重载==
bool operator==(const D& s)
{
return _node == s._node;
}
};②const迭代器
const迭代器的作用是只可读不可写，防止数据被修改，因此我们只需在普通迭代器的基础上对operator*()和operator->()添加const操作即可：
//②const迭代器 可读不可写
template<class T>
struct __list_const_iterator
{
typedef ListNode<T> Node;
typedef __list_const_iterator D;
Node* _node;
//迭代器构造函数
__list_const_iterator(Node* x)
:_node(x)
{}
//重载++
//前置++
D& operator++()//返回迭代器的引用
{
_node = _node->_next;//指向下一个节点
return *this;
}
//后置++
D operator++(int)
{
D tmp(*this);
_node = _node->_next;
return tmp;//返回拷贝之前的值
}
//重载--
//前置--
D& operator--()
{
_node = _node->_prev;
return *this;
}
//后置--
D operator--(int)
{
D tmp(*this);
_node = _node->_prev;
return tmp;
}
//重载解引用
const T& operator*()//返回数据的引用
{
return _node->_data;//返回节点里的数据
}
//重载->
const T* operator->()
{
return &_node->_data;
}
//重载！=
bool operator !=(const D& s)
{
return _node != s._node;
}
//重载==
bool operator==(const D& s)
{
return _node == s._node;
}
};③模板迭代器
观察以上两个迭代器，不同之处也就在于对operator*()和operator->()的操作不同，代码相似度可以说达到了90%，那么有没有办法减少冗余，提高代码的可读性呢？
答案当然是有的，我们可以为两个迭代器提供一个共同的模板，再提供两个参数，当调用普通迭代器和const迭代器时，只需根据所传递的参数而选择不同的迭代器。
template<class T, class Ref, class Ptr>
struct __list_iterator
{
typedef ListNode<T> Node;
typedef __list_iterator<T, Ref, Ptr> D;
Node* _node;
//迭代器构造函数
__list_iterator(Node* x)
:_node(x)
{}
//重载++
//前置++
D& operator++()//返回迭代器的引用
{
_node = _node->_next;//指向下一个节点
return *this;
}
//后置++
D operator++(int)
{
D tmp(*this);
_node = _node->_next;
return tmp;//返回拷贝之前的值
}
//重载--
//前置--
D& operator--()
{
_node = _node->_prev;
return *this;
}
//后置--
D operator--(int)
{
D tmp(*this);
_node = _node->_prev;
return tmp;
}
//重载解引用
Ref operator*()//返回数据的引用
{
return _node->_data;//返回节点里的数据
}
//重载->
Ptr operator->()
{
return &_node->_data;
}
//重载！=
bool operator !=(const D& s)
{
return _node != s._node;
}
//重载==
bool operator==(const D& s)
{
return _node == s._node;
}
};3.list类
做好了节点类和迭代器类的准备工作，终于来到了主角list类
//定义链表
template<class T>
class list
{
typedef ListNode<T> Node;
public:
/*typedef __list_iterator<T> iterator;
typedef __list_const_iterator<T> const_iterator;*/
typedef __list_iterator<T, T&, T*> iterator;
typedef __list_iterator<T, const T&, const T*> const_iterator;
private:
Node* _head;
};3.1 clear、析构函数、swap
①clear
//clear
void clear()
{
iterator it = begin();
while (it != end())
{
it = erase(it);
}
}② 析构函数
//析构函数
~list()
{
clear();
delete _head;
_head = nullptr;
}③ swap
//swap
void swap(list<T>& tmp)
{
std::swap(_head, tmp._head);
}3.2构造函数
①无参构造
//链表构造函数
list()
{
_head = new Node;
_head->_next = _head;
_head->_prev = _head;
}②赋值构造
//operator=
list<T>& operator=(list<T> lt)
{
swap(lt);
return *this;
}3.3 迭代器
//普通迭代器
iterator begin()
{
//return iterator(_head->_next);
return _head->_next;//单参数的构造函数支持隐式类型转换
}
iterator end()
{
return _head;
}
//const迭代器
const_iterator begin() const
{
//return iterator(_head->_next);
return _head->_next;//单参数的构造函数支持隐式类型转换
}
const_iterator end() const
{
return _head;
}3.4插入函数
①insert插入
//insert插入
iterator insert(iterator pos, const T& x)
{
Node* cur = pos._node;//取当前节点
Node* prev = cur->_prev;//当前节点的前一个节点
Node* newnode = new Node(x);//创建并初始化新节点
prev->_next = newnode;//前一个节点的_next指针指向新节点
newnode->_prev = prev;//新节点的_prev指针指向前一个节点
newnode->_next = cur;//新节点的_next指针指向当前节点（此时相对于新节点就变成了后一个节点）
cur->_prev = newnode;//当前节点的_prev指针指向新节点（此时相对于新节点就变成了后一个节点）
//return iterator(newnode);
return newnode;
}②头插
//push_front头插
void push_front(const T& x)
{
insert(begin(), x);
}③尾插
原始写法
void push_back(const T& x)
{
Node* newnode = new Node(x);//开辟并初始化新节点newnode
Node* tail = _head->_prev;//定义上一个节点为tail
tail->_next = newnode;//上一个节点tail的next指针指向新节点newnode
newnode->_prev = tail;//新节点newnode的prev指针指向上一个节点tail
newnode->_next = _head;//新节点newnode的next指针指向头节点_head
_head->_prev = newnode;//头节点_head的prve指针指向新节点newnode
}复用insert
void push_back(const T& x)
{
insert(end(), x);
}复用尾插，写拷贝构造：
//拷贝构造
list(list<T>& lt)
{
_head = new Node;
_head->_next = _head;
_head->_prev = _head;//拷贝之前先创建一个头节点，自己指向自己
for (const auto& e : lt)
{
push_back(e);
}
}3.5 删除函数
①erase删除
iterator erase(iterator pos)
{
assert(pos != end());//避免删除哨兵位的头节点
Node* cur = pos._node;//取当前节点
Node* prev = cur->_prev;//取前一个节点
Node* next = cur->_next;//取后一个节点
prev->_next = next;
next->_prev = prev;
//销毁当前节点
delete cur;
return next;
}②头删
//pop_front头删
void pop_front()
{
erase(begin());
}③尾删
//pop_back尾删
void pop_back()
{
erase(--end());
}4.测试
void test_list()
{
//无参构造
list<int> l1;
for (auto e : l1)
{
cout << e << " ";
}
cout << endl;
//插入
//insert插入
l1.insert(l1.begin(), 1);
for (auto e : l1)
{
cout << e << " ";
}
cout << endl;
//头插
l1.push_front(0);
for (auto e : l1)
{
cout << e << " ";
}
cout << endl;
//尾插
l1.push_back(2);
l1.push_back(3);
l1.push_back(4);
for (auto e : l1)
{
cout << e << " ";
}
cout << endl;
//删除
//erase删除
l1.erase(l1.begin());
for (auto e : l1)
{
cout << e << " ";
}
cout << endl;
//头删
l1.pop_front();
for (auto e : l1)
{
cout << e << " ";
}
cout << endl;
//尾删
l1.pop_back();
for (auto e : l1)
{
cout << e << " ";
}
cout << endl;
//赋值构造
list<int> l2 = l1;
for (auto e : l1)
{
cout << e << " ";
}
cout << endl;
}
源代码（list.h）
#pragma once
#include <iostream>
#include <assert.h>
using namespace std;
#include <assert.h>
namespace xxk
{
//定义链表节点
template<class T>
struct ListNode
{
ListNode<T>* _next;
ListNode<T>* _prev;
T _data;
//链表节点构造函数
ListNode(const T& x = T())
:_next(nullptr)
, _prev(nullptr)
, _data(x)
{}
};
//定义迭代器
//在vector使用迭代器时：
/*vector<int>::iterator it = l1.begin();
while (it != l1.end())
{
cout << *it << " ";
++it;
}
cout << endl;*/
//在这段代码中我们希望++it就能找到下一个节点，而it解引用（*it）我们需要得到节点里存的data
//可是链表并不是连续的，因迭代器使用形式与指针完全相同，想要实现以上功能，我们必须要在自定义类中实现以下方法：
//1. 指针可以解引用，迭代器的类中必须重载operator*()
//2. 指针可以通过->访问其所指空间成员，迭代器类中必须重载oprator->()
//3. 指针可以++向后移动，迭代器类中必须重载operator++()与operator++(int)
// 至于operator--() / operator--(int)释放需要重载，根据具体的结构来抉择，双向链表可以向前移动，
// 所以需要重载，如果是forward_list就不需要重载--
//4. 迭代器需要进行是否相等的比较，因此还需要重载operator == ()与operator != ()
//③为减少冗余，提高代码的可读性，使用模板将两个类写到一起
template<class T, class Ref, class Ptr>
struct __list_iterator
{
typedef ListNode<T> Node;
typedef __list_iterator<T, Ref, Ptr> D;
Node* _node;
//迭代器构造函数
__list_iterator(Node* x)
:_node(x)
{}
//重载++
//前置++
D& operator++()//返回迭代器的引用
{
_node = _node->_next;//指向下一个节点
return *this;
}
//后置++
D operator++(int)
{
D tmp(*this);
_node = _node->_next;
return tmp;//返回拷贝之前的值
}
//重载--
//前置--
D& operator--()
{
_node = _node->_prev;
return *this;
}
//后置--
D operator--(int)
{
D tmp(*this);
_node = _node->_prev;
return tmp;
}
//重载解引用
Ref operator*()//返回数据的引用
{
return _node->_data;//返回节点里的数据
}
//重载->
Ptr operator->()
{
return &_node->_data;
}
//重载！=
bool operator !=(const D& s)
{
return _node != s._node;
}
//重载==
bool operator==(const D& s)
{
return _node == s._node;
}
};
//定义链表
template<class T>
class list
{
typedef ListNode<T> Node;
public:
/*typedef __list_iterator<T> iterator;
typedef __list_const_iterator<T> const_iterator;*/
typedef __list_iterator<T, T&, T*> iterator;
typedef __list_iterator<T, const T&, const T*> const_iterator;
//普通迭代器
iterator begin()
{
//return iterator(_head->_next);
return _head->_next;//单参数的构造函数支持隐式类型转换
}
iterator end()
{
return _head;
}
//const迭代器
const_iterator begin() const
{
//return iterator(_head->_next);
return _head->_next;//单参数的构造函数支持隐式类型转换
}
const_iterator end() const
{
return _head;
}
//链表构造函数
list()
{
_head = new Node;
_head->_next = _head;
_head->_prev = _head;
}
//clear
void clear()
{
iterator it = begin();
while (it != end())
{
it = erase(it);
}
}
//析构函数
~list()
{
clear();
delete _head;
_head = nullptr;
}
//拷贝构造
list(list<T>& lt)
{
_head = new Node;
_head->_next = _head;
_head->_prev = _head;//拷贝之前先创建一个头节点，自己指向自己
for (const auto& e : lt)
{
push_back(e);
}
}
//swap
void swap(list<T>& tmp)
{
std::swap(_head, tmp._head);
}
//operator=
list<T>& operator=(list<T> lt)
{
swap(lt);
return *this;
}
//尾插
①
//void push_back(const T& x)
//{
// Node* newnode = new Node(x);//开辟并初始化新节点newnode
// Node* tail = _head->_prev;//定义上一个节点为tail
// tail->_next = newnode;//上一个节点tail的next指针指向新节点newnode
// newnode->_prev = tail;//新节点newnode的prev指针指向上一个节点tail
// newnode->_next = _head;//新节点newnode的next指针指向头节点_head
// _head->_prev = newnode;//头节点_head的prve指针指向新节点newnode
//}
//②复用insert
void push_back(const T& x)
{
insert(end(), x);
}
//insert插入
iterator insert(iterator pos, const T& x)
{
Node* cur = pos._node;//取当前节点
Node* prev = cur->_prev;//当前节点的前一个节点
Node* newnode = new Node(x);//创建并初始化新节点
prev->_next = newnode;//前一个节点的_next指针指向新节点
newnode->_prev = prev;//新节点的_prev指针指向前一个节点
newnode->_next = cur;//新节点的_next指针指向当前节点（此时相对于新节点就变成了后一个节点）
cur->_prev = newnode;//当前节点的_prev指针指向新节点（此时相对于新节点就变成了后一个节点）
//return iterator(newnode);
return newnode;
}
//push_front头插
void push_front(const T& x)
{
insert(begin(), x);
}
//erase删除函数
iterator erase(iterator pos)
{
assert(pos != end());//避免删除哨兵位的头节点
Node* cur = pos._node;//取当前节点
Node* prev = cur->_prev;//取前一个节点
Node* next = cur->_next;//取后一个节点
prev->_next = next;
next->_prev = prev;
//销毁当前节点
delete cur;
return next;
}
//pop_back尾删
void pop_back()
{
erase(--end());
}
//pop_front头删
void pop_front()
{
erase(begin());
}
private:
Node* _head;
};
void test_list()
{
//无参构造
list<int> l1;
for (auto e : l1)
{
cout << e << " ";
}
cout << endl;
//插入
//insert插入
l1.insert(l1.begin(), 1);
for (auto e : l1)
{
cout << e << " ";
}
cout << endl;
//头插
l1.push_front(0);
for (auto e : l1)
{
cout << e << " ";
}
cout << endl;
//尾插
l1.push_back(2);
l1.push_back(3);
l1.push_back(4);
for (auto e : l1)
{
cout << e << " ";
}
cout << endl;
//删除
//erase删除
l1.erase(l1.begin());
for (auto e : l1)
{
cout << e << " ";
}
cout << endl;
//头删
l1.pop_front();
for (auto e : l1)
{
cout << e << " ";
}
cout << endl;
//尾删
l1.pop_back();
for (auto e : l1)
{
cout << e << " ";
}
cout << endl;
//赋值构造
list<int> l2 = l1;
for (auto e : l1)
{
cout << e << " ";
}
cout << endl;
}
}