提示：文章内容较长，请参考目录

总述

list模拟实现主要包括四个类：节点类、迭代器类、反向迭代器类、list类。
list底层结构：

因为list的底层空间不连续，所以迭代器不能使用原生态的指针，将节点类型的指针封装成类，重载解引用及自增等常用操作。list可以保存多种数据类型，所以这些类都写成类模板

一、节点类

list底层是带头结点的双向循环链表，先实现节点类，给成类模板的形式，便于插入不同类型的数据。

template<class T>
struct ListNode
{
	ListNode<T>* prev;
	ListNode<T>* next;
	T data;//要在链表中保存的数据类型

	ListNode(const T& value = T())
		:prev(nullptr)
		, next(nullptr)
		, data(value)
	{ }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

定义新节点的方法：

ListNode<变量类型>*变量名=new ListNode(value)；
1

二、迭代器类

迭代器类模板有三个参数，T：迭代器指向的元素类型，Ref：返回的引用类型，Ptr：返回的指针类型。Ref和Ptr一般不写成T&和T*。

成员变量

迭代器类的成员变量就是节点类型的指针

Node* _pNode;//成员变量，节点类型指针
1

构造函数

编译器默认的构造函数是无参的，构造函数需要给出

ListIterator(Node* pNode = nullptr)
	:_pNode(pNode)
{}
1
2
3

*重载

返回节点中保存的数据

Ref operator*()
{
	return _pNode->data;
}
1
2
3
4

->重载

返回节点中保存的数据的地址

Ptr operator->()
{
	return &_pNode->data;
}
1
2
3
4

->的重载只对内置类型有意义：

“++”

前置++
返回值是迭代器自身类型的引用，前面已经将ListIterator重命名位Self，表示迭代器自身的类型。

Self& operator++()
{
	_pNode = _pNode->next;
	return *this;
}
1
2
3
4
5

后置++
定义临时变量，返回自增前的值

Self operator++(int)
{
	Self temp(*this);
	_pNode = _pNode->next;
	return temp;
}
1
2
3
4
5
6

“–”

与++原理相同

Self& operator--()
{
	_pNode = _pNode->prev;
	return (*this);
}
Self operator--(int)
{
	Self temp(*this);
	_pNode = _pNode->prev;
	return temp;
}
1
2
3
4
5
6
7
8
9
10
11

“==“和”!=”

比较两个迭代器中封装的指针

bool operator!=(const Self& it)
{
	return _pNode != it._pNode;
}
bool operator==(const Self& it)
{
	return _pNode == it._pNode;
}
1
2
3
4
5
6
7
8

三、反向迭代器类

反向迭代器可以对迭代器类进行复用

因为类外访问静态成员变量时也会使用类名::变量名的方式，所以对迭代器类中的Reference和Pointer进行重命名时要加上typename,明确告诉编译器要重命名的是一个数据类型。否则编译器会报错：

成员变量

反向迭代器对迭代器类进行复用

private:
	Iterator _it;//正向迭代器
1
2

*重载

反向迭代器的解引用要做特殊处理，返回的是对迭代器–的值

Reference operator*()
{
	//*做特殊处理，先--,再解引用返回
	auto temp = _it;
	--temp;
	return *temp;
}
1
2
3
4
5
6
7

->重载

复用*的重载，返回value的地址

Pointer operator->()
{
	return &(operator*());
}
1
2
3
4

“++”

反向迭代器的++即为正向迭代器的–

Self operator++()
{
	--_it;
	return *this;
}
Self operator++(int)
{
	Self temp(*this);
	--_it;
	return *this;
}
1
2
3
4
5
6
7
8
9
10
11

“- -”

反向迭代器的–用正向迭代器的++替代

Self operator--()
{
	++_it;
	return *this;
}
Self operator--(int)
{
	Self temp(*this);
	++_it;
	return temp;
}
1
2
3
4
5
6
7
8
9
10
11

" == " 和"!="

比较反向迭代器类中保存的正向迭代器，复用正向迭代器中的比较方法

bool operator==(const Self& rit)
{
	return _it == rit;
}
bool operator!=(const Self& rit)
{
	return _it == rit._it;
}
1
2
3
4
5
6
7
8

四、list类

成员变量

list的成员变量只有一个head指针，指向链表的第一个节点

private:
	Node* head;
1
2

构造相关

空对象

list()
{
	CreatHead();
}
1
2
3
4

创造头节点的方法：

//提供一个创造头结点的方法
void CreatHead()
{
	//调用节点类的构造方法
	head = new Node();
	head->next = head;
	head->prev = head;
}
1
2
3
4
5
6
7
8

new申请空间，令head指向这段空间，head的next和prev都指向自己。

n个T类型元素

调用push_back方法，创造头节点后，不断进行尾插直到元素个数等于n

list(int n, const T& value = T())
{
	CreatHead();
	for (int i = 0; i < n; ++i)
	{
		push_back(value);
	}
}
1
2
3
4
5
6
7
8

拷贝构造

复用push_back

list(const list<T>& l)
{
	CreatHead();
	auto it = l.cbegin();
	while (it != l.cend())
	{
		push_back(*it);
		it++;
	}
}
1
2
3
4
5
6
7
8
9
10

迭代器构造

将迭代器构造方法写成函数模板，可以传入不同类型的迭代器来构造list对象

template<class InputIterator>
list(InputIterator first, InputIterator last)
{
	CreatHead();
	while (first != last)
	{
		push_back(*first);
		first++;
	}
}
1
2
3
4
5
6
7
8
9
10

赋值运算符重载

与拷贝构造写法相同

list<T>& operator=(const list<T>& l)
{
	if (this != &l)
	{
		clear();//先清空当前对象中的节点
		auto it = l.cbegin();
		while (it != l.cend())
		{
			push_back(*it);
			it++;
		}
	}
	return *this;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

析构

清空当前对象，释放头节点空间，将头节点置空

~list()
{
	clear();
	delete head;
	head = nullptr;
}
1
2
3
4
5
6

迭代器

正向迭代器

begin
此处的iterator是对ListIterator的重命名，这里会返回一个ListIterator类对象

iterator begin()
{
	//iterator it(head->next);
	//return it;
	//head->next是传递给迭代器类对象构造函数的参数,调用iterator的构造函数
	return iterator(head->next);//构造匿名对象返回
}
1
2
3
4
5
6
7

end

iterator end()
{
	return iterator(head);
}
1
2
3
4

const类型迭代器
iterator和const_iterator 是两个不同的类：

两者使用的是相同的类模板，但是传递的参数不同，最终实例化的也是不同的类。
cbegin&cend

const_iterator cbegin()const
{
	return const_iterator(head->next);
}
const_iterator cend()const
{
	return const_iterator(head);
}
1
2
3
4
5
6
7
8

反向迭代器

rbegin&rend
返回正向迭代器的end和begin

reverse_iterator rbegin()
{
	return reverse_iterator(end());
}
reverse_iterator rend()
{
	return reverse_iterator(begin());
}
1
2
3
4
5
6
7
8

crbegin&crend
复用正向迭代器的cend和cbegin

const_reverse_iteraotr crbegin()const
{
	return const_reverse_iteraotr(cend());
}
const_reverse_iteraotr crend()const
{
	return const_reverse_iteraotr(cbegin());
}
1
2
3
4
5
6
7
8

容量操作

size
遍历链表，统计节点个数

size_t size()
{
	auto it = cbegin();
	size_t count = 0;
	while (it != cend())
	{
		++count;
		++it;
	}
	return count;
}
1
2
3
4
5
6
7
8
9
10
11

empty
如果head->next是head本身则表明链表为空

bool empty()
{
	return head->next == head;
}
1
2
3
4

resize
改变节点个数，若新的节点个数大于旧的，则调用push_back填充元素；若新的节点个数小于原来的调用pop_back尾删

元素访问

front
复用迭代器解引用的方法，返回begin()位置元素

T& front()
{
	return *begin();
}
const T& front()const
{
	return *cbegin();
}
1
2
3
4
5
6
7
8

back
back表示最后一个元素，但是end()指向的是最后一个元素的下一个位置，需要定义临时变量，不能直接对end()进行- -。

T& back()
{
	auto it = end();
	//return --end()//错误写法
	it--;
	return *it;
}
const T& back()const
{
	auto it = end();
	it--;
	return *it;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

打印链表

定义一个打印链表的函数模板，检验方法。通过迭代器遍历链表，打印每一个节点的数据。

template<class T>
void PrintList(const list<T>& l)
{
	auto it = l.cbegin();
	while (it != l.cend())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;
}
1
2
3
4
5
6
7
8
9
10
11

元素修改

尾插与尾删

push_back
复用insert方法在end位置插入

void  push_back(const T& value)
{
	insert(end(), value);
}
1
2
3
4

pop_back
先判断链表是否为空，复用erase方法在end的前一个位置进行插入

void pop_back()
{
	if (empty())
	{
		return;
	}
	auto it = end();
	it--;
	erase(it);
}
1
2
3
4
5
6
7
8
9
10

头插与头删

复用insert与erase方法，在begin()位置进行插入或删除

void push_front(const T& value = T())
{
	insert(begin(), value);
}
void pop_front()
{
	erase(begin());
}
1
2
3
4
5
6
7
8

⭐insert

任意位置的插入：申请新节点，连接新节点与链表，断开旧的连接。
这里传入的参数是一个迭代器类对象，不能直接进行操作，要对对象中封装的_pNode指针进行操作。
返回值是新插入的节点的迭代器，所以要用申请的新节点的指针newnode构造一个迭代器类对象返回，不能直接返回newnode

iterator insert(iterator Insertpos, const T& value)
{
	Node* newnode = new Node(value);
	Node* pos = Insertpos._pNode;//_pNode是节点类型的指针
	newnode->next = pos;
	newnode->prev = pos->prev;
	newnode->prev->next = newnode;
	pos->prev = newnode;
	//return newnode;
	//⭐迭代器是封装的Node*指针，此时不能再返回newnode
	return iterator(newnode);//构造匿名对象返回
}
1
2
3
4
5
6
7
8
9
10
11
12

⭐erase

任意位置的删除：分别改变前后两个节点的next和prev指针的指向即可

iterator erase(iterator Erasepos)
{
	Node* pos = Erasepos._pNode;
	Node* ret = pos->next;
	pos->prev->next = pos->next;
	pos->next->prev = pos->prev;
	delete pos;
	return iterator(ret);
}
1
2
3
4
5
6
7
8
9

区间删除：复用单个节点删除的方法，遍历要删除的区间。
要用接收erase的返回值，防止迭代器失效

iterator erase(iterator first, iterator last)
{
	auto it = first;
	while (it != last)
	{
		//it=erase(it);
		//后置++会构造临时对象返回，不会导致迭代器失效
		erase(it++);
	}
	return it;
}
1
2
3
4
5
6
7
8
9
10
11

clear&swap

clear复用erase区间删除的方法，从begin删除到end位置；
swap方法调用标准库中的swap，交换两个链表的头节点。

void clear()
{
	erase(begin(), end());
}
void swap(list<T>& l)
{

	std::swap(head, l.head);
}
1
2
3
4
5
6
7
8
9

附：完整list类，含测试用例

#include
#include
using namespace std;

namespace ZH
{
	/
	//节点类模板, 
	template<class T>
	struct ListNode
	{
		ListNode<T>* prev;
		ListNode<T>* next;
		T data;

		ListNode(const T& value = T())
			:prev(nullptr)
			, next(nullptr)
			, data(value)
		{ }
	};
	
	/
	//迭代器类模板
	//list的迭代器不能使用原生态的指针，要进行封装
	//T：迭代器指向的元素类型
	//Ref：给operator*使用，返回引用类型，不要写成T&
	//Ptr：返回值使用，不要写成T*
	template<class T,class Ref,class Ptr>
	class ListIterator
	{
	public:
		typedef ListNode<T> Node;//化简节点类的名字
		typedef Ref Reference;//在反向迭代器类中使用
		typedef Ptr Pointer;

		typedef ListIterator<T, Ref, Ptr> Self;//简化迭代器类的名字

		//构造函数
		ListIterator(Node* pNode=nullptr)
			:_pNode(pNode)
		{}

		//重载部分需要使用的运算符即可：*、->、++、--、==
		Ref operator*()
		{
			return _pNode->data;
		}
		//T为自定义类型时有意义,
		Ptr operator->()
		{
			return &_pNode->data;
		}
		//前置++，返回值是迭代器自身类型的引用
		Self& operator++()
		{
			_pNode = _pNode->next;
			return *this;
		}
		//后置
		Self operator++(int)
		{
			Self temp(*this);
			_pNode = _pNode->next;
			return temp;
		}
		Self& operator--()
		{
			_pNode = _pNode->prev;
			return (*this);
		}
		Self operator--(int)
		{
			Self temp(*this);
			_pNode = _pNode ->prev;
			return temp;
		}
		//迭代器能进行比较
		bool operator!=(const Self& it)
		{
			return _pNode != it._pNode;
		}
		bool operator==(const Self& it)
		{
			return _pNode == it._pNode;
		}

		Node* _pNode;//成员变量，节点类型指针
	};

	
	//反向迭代器类模板，对迭代器进行复用
	template<class Iterator>
	class ListReverseIterator
	{
	public:
		//typedef Iterator::Reference Reference;
		//typedef Iterator::Pointer Pointer;
		typedef typename Iterator::Reference Reference;//typename指定Reference是Iterator中的数据类型
		typedef typename Iterator::Pointer Pointer;
		typedef ListReverseIterator<Iterator> Self;

		ListReverseIterator(Iterator it)
			: _it(it)
		{ }

		Reference operator*()
		{
			//*做特殊处理，先--,再解引用返回
			auto temp = _it;
			--temp;
			return *temp;
		}
		Pointer operator->()
		{
			return &(operator*());
		}
		Self operator++()
		{
			--_it;
			return *this;
		}
		Self operator++(int)
		{
			Self temp(*this);
			--_it;
			return *this;
		}
		Self operator--()
		{
			++_it;
			return *this;
		}
		Self operator--(int)
		{
			Self temp(*this);
			++_it;
			return temp;
		}
		bool operator==(const Self& rit)
		{
			return _it == rit;
		}
		bool operator!=(const Self& rit)
		{
			return _it == rit._it;
		}

	private:
		Iterator _it;//正向迭代器
	};

	template<class T>
	class list
	{
		typedef ListNode<T> Node;
		//typedef Node* iterator;//不能使用Node*作迭代器
		//迭代器
		typedef ListIterator<T, T&, T*> iterator;
		typedef ListIterator< T, const T&, const T*> const_iterator;
		
		typedef ListReverseIterator<iterator> reverse_iterator;
		typedef ListReverseIterator<const_iterator> const_reverse_iteraotr;

	public:
		///
		//构造
		list()
		{
			CreatHead();
		}
		list(int n, const T& value=T())
		{
			CreatHead();
			for (int i = 0; i < n; ++i)
			{
				push_back(value);
			}
		}
		list(const list<T>& l)
		{
			CreatHead();
			auto it = l.cbegin();
			while (it != l.cend())
			{
				push_back(*it);
				it++;
			}
		}
		//迭代器区间构造
		template<class InputIterator>
		list(InputIterator first, InputIterator last)
		{
			CreatHead();
			while (first != last)
			{
				push_back(*first);
				first++;
			}
		}
		//赋值运算符重载
		list<T>& operator=(const list<T>& l)
		{
			if (this != &l)
			{
				clear();//先清空当前对象中的节点
				auto it = l.cbegin();
				while (it != l.cend())
				{
					push_back(*it);
					it++;	
				}
			}
			return *this;
		}
		~list()
		{
			clear();
			delete head;
			head = nullptr;
		}
	public:
		//迭代器
		iterator begin()
		{
			//iterator it(head->next);
			//return it;
			//iterator是对ListIterator的重命名
			//这里会返回一个ListIterator类对象
			//head->next是传递给迭代器类对象构造函数的参数,调用iterator的构造函数
			return iterator(head->next);//构造匿名对象返回
		}
		iterator end()
		{
			return iterator(head);
		}
		//const类型迭代器
		const_iterator cbegin()const
		{
			return const_iterator(head->next);
		}
		const_iterator cend()const
		{
			return const_iterator(head);
		}

		//反向迭代器
		//反向迭代器的成员变量是一个迭代器类对象
		//end()即为传递给反向迭代器类构造函数的参数
		reverse_iterator rbegin()
		{
			return reverse_iterator(end());
		}
		reverse_iterator rend()
		{
			return reverse_iterator(begin());
		}
		//反向const类型迭代器
		const_reverse_iteraotr crbegin()const
		{
			return const_reverse_iteraotr(cend());
		}
		const_reverse_iteraotr crend()const
		{
			return const_reverse_iteraotr(cbegin());
		}

		/
		//容量
		size_t size()
		{
			auto it = cbegin();
			size_t count = 0;
			while (it != cend())
			{
				++count;
				++it;
			}
			return count;
		}
		bool empty()
		{
			return head->next == head;
		}
		void resize(int newsize,const T& value=T())
		{
			size_t oldsize = size();
			if (newsize > oldsize)
			{
				while (oldsize++<newsize)
				{
					push_back(value);
				}
			}
			if (newsize < oldsize)
			{
				while (oldsize-- < newsize)
				{
					pop_back();
				}
			}
		}

		///
		//元素访问
		T& front()
		{
			return *begin();
		}
		const T& front()const
		{
			return *cbegin();
		}
		T& back()
		{
			auto it = end();
			it--;
			return *it;
		}
		const T& back()const
		{
			auto it = end();
			it--;
			return *it;
		}


		/
		//元素修改
		void  push_back(const T& value)
		{
			insert(end(), value);
		}

		void pop_back()
		{
			if (empty())
			{
				return;
			}
			auto it = end();
			it--;
			erase(it);
		}
		void push_front(const T& value = T())
		{
			//Node* pos = head->next;
			/*Node* newnode = new Node(value);
			newnode->next = head->next;
			newnode->prev = head;
			head->next->prev = newnode;
			head->next = newnode;*/
		    //复用insert
			insert(begin(), value);
		}
		void pop_front()
		{
			erase(begin());
		}

		//⭐insert
		// iterator是ListIterator
		iterator insert(iterator Insertpos, const T& value)
		{
			Node* newnode = new Node(value);
			Node* pos = Insertpos._pNode;//_pNode是节点类型的指针
			newnode->next = pos;
			newnode->prev = pos->prev;
			newnode->prev->next = newnode;
			pos->prev = newnode;
			//return newnode;
			//⭐迭代器是封装的Node*指针，此时不能再返回newnode
			return iterator(newnode);//构造匿名对象返回
		}
		//⭐erase
		iterator erase(iterator Erasepos)
		{
			Node* pos = Erasepos._pNode;
			Node* ret = pos->next;
			pos->prev->next = pos->next;
			pos->next->prev = pos->prev;
			delete pos;
			return iterator(ret);
		}
		iterator erase(iterator first, iterator last)
		{
			auto it = first;
			while (it != last)
			{
				//it=erase(it);
				erase(it++);
			}
			return it;
		}

		void clear()
		{
			erase(begin(), end());
		}
		void swap(list<T>& l)
		{
			std::swap(head, l.head);
		}

	private:
		//提供一个创造头结点的方法
		void CreatHead()
		{
			//调用节点类的构造方法
			head = new Node();
			head->next = head;
			head->prev = head;
		}
	private:
		Node* head;

	};

	template<class T>
	void PrintList(const list<T>& l)
	{
		auto it = l.cbegin();
		while (it != l.cend())
		{
			cout << *it << " ";
			++it;
		}
		cout << endl;
	}
}

void Test1()
{
	ZH::list<int> l1;
	ZH::list<int> l2(3, 1);
	PrintList(l2);
	ZH::list<int> l3(l2.begin(), l2.end());
	PrintList(l3);
	vector<int> v{ 0,1,2,3,4 };
	ZH::list<int> l4(v.begin(), v.end());
	PrintList(l4);
}

void Test2()
{
	vector<int> v{ 1,2,3,4 };
	ZH::list<int> L1(v.begin(), v.end());
	L1.push_back(5);
	L1.push_back(6);
	L1.push_front(0);
	PrintList(L1);
	L1.pop_back();
	L1.pop_front();
	PrintList(L1);
	L1.erase(--L1.end());
	PrintList(L1);
}

void Test3()
{
	ZH::list<int> L1;
	L1.push_back(1);
	L1.push_back(2);
	L1.push_back(3);
	L1.push_front(0);
	PrintList(L1);
	L1.resize(6, 5);
	PrintList(L1);
}

struct A
{
	int a;
	int b;
	int c;
};

void Test4()
{
	A aa{ 1,2,3 };
	A bb{ 4,5,6 };
	A cc{ 7,8,9 };
	ZH::list<A> L;
	L.push_back(aa);
	L.push_back(bb);
	L.push_back(cc);
	auto it = L.begin();
	while (it != L.end())
	{
		//⭐it->得到的是节点的地址
		//本应是it->->a，编译器做了特殊处理
		cout << it->a << " ";
		it++;
	}
	cout << endl;
}

void Test5()
{
	ZH::list<int> L1;
	L1.push_back(0);
	L1.push_back(1);
	L1.push_back(2);
	L1.push_back(3);
	PrintList(L1);
	cout << L1.back() << endl;
	cout << L1.front() << endl;
	cout << L1.size() << endl;
	L1.clear();
	cout << L1.size() << endl;
}
 void Test6()
 {
	 ZH::list<int> L1;
	 L1.push_back(0);
	 L1.push_back(1);
	 L1.push_back(2);
	 L1.push_back(3);
	 PrintList(L1);
	 //区间删除
	 /*L1.erase(L1.begin(), L1.end());
	 PrintList(L1);*/

	 ZH::list<int> L2;
	 L2.push_back(1);
	 L2.push_back(2);
	 L2.push_back(3);
	 L2.push_back(4);
	 L2.push_back(5);
	 PrintList(L2);
	 L1.swap(L2);
	 PrintList(L1);
	 PrintList(L2);
 }

int main()
{
	Test6();
	system("pause");
	return 0;
}
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
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541