list的模拟实现

前言

        list是STL中重要的容器，了解它的原理对于我们掌握它是有很多的帮助的，一般list和vector都是一起来使用的，因为它们的优缺点不同，刚好可以互补。list的优点是任意位置的插入和删除都很快，它的缺点是不支持随机访问，而vector的优点是支持随机访问，进而就可以很好的支持排序算法，二分查找，堆算法等，它的缺点是扩容要付出一定的代价，而且除了尾上的插入和删除外其他位置的插入和删除都不快（因为要挪动数据）。下面让我们一起来实现一下list吧。

目录

list的实现代码 

1.构造函数和析构函数

        1.1构造函数

        2.2析构函数 

2.operator=的重载和拷贝构造函数

        2.2拷贝构造

        2.2operator=的重载 

3.迭代器的实现

        3.1普通迭代器

        3.2const类型的迭代器

4.增删查改

        4.1尾删尾插

        4.2任意位置的插入和删除

         4.3头插头删

 5.测试代码

list的实现代码 

#include<iostream>
using namespace std;
namespace qyy
{
template<class T>
struct __list_node
{
	__list_node(const T& data = T())//构造函数函数
		:_prev(nullptr)
		, _next(nullptr)
		, _data(data)
	{ }
	__list_node<T>* _prev;//前指针
	__list_node<T>* _next;//后指针
	T _data;//数据
};

template<class T, class Ref, class Ptr>
struct __list_iterator//对链表的迭代器进行封装
{
	typedef __list_node<T> Node;
	typedef __list_iterator< T,  Ref,  Ptr> iterator;
	__list_iterator(Node* node)//构造函数
		:_node(node)
	{ }
	//对指针行为的模仿
	Ref operator* ()
	{
		return _node->_data;
	}
	Ptr operator->()
	{
		return &(_node->_data);
	}
	iterator& operator++()//前置++
	{
		_node = _node->_next;
		return *this;
	}
	iterator& operator--()//前置--
	{
		_node = _node->_prev;
		return *this;
	}
	iterator operator++(int)//后置++
	{
		//Node tmp(_node);
		iterator tmp(*this);
		_node = _node->_next;
		return tmp;
	}
	iterator operator--(int)//后置--
	{
		//Node tmp(_node);
		iterator tmp(*this);

		_node = _node->_prev;
		return tmp;
	}
	bool operator==(const iterator& it)
	{
		return _node == it._node;
	}
	bool operator!=(const iterator& it)
	{
		return _node != it._node;
	}
	
public:
	Node* _node;//存放一个节点的指针
};

template<class T>
class list//带头双向循环链表
{
public:
	typedef __list_node<T> Node;//节点的重定义
	typedef __list_iterator<T,T&,T*> iterator;//迭代器重定义
	typedef __list_iterator<T, const T&, const T*> const_iterator;
	iterator begin()
	{
		return iterator(_head->_next);
	}
	iterator end()
	{
		return iterator(_head);
	}
	const_iterator begin()const
	{
		return const_iterator(_head->_next);
	}
	const_iterator end()const
	{
		return const_iterator(_head);
	}
	list()//构造函数
		:_head(new Node)
	{
		_head->_next = _head;
		_head->_prev = _head;
	}
	list(const list<T>& l1)//拷贝构造
	{
		_head = new Node;//初始化头结点
		_head->_next = _head;
		_head-> _prev = _head;
		const_iterator it = l1.begin();
		while (it != l1.end())
		{
			push_back(it._node->_data);//将节点插入
			++it;
		}
	}

	list<T>& operator=(list<T> l1)//现代写法
	{
		if (this != &l1)
		{
			swap(_head, l1._head);
		}
		return *this;
	}
	list<T> operator=(const list<T> l1)const
	{
		clear();
		const_iterator it = l1.begin();
		while (it != l1.end())
		{
			push_back(it._node->_data);//将节点插入
			++it;
		}
		return *this;
	}
	~list()
	{
		clear();//删除头结点以外的其他节点
		delete _head;//删除头结点
	}
	void clear()//除了头结点剩下的节点全部删除
	{
		if (begin() != end())//判断不能删除头结点
		{
			iterator it = begin();
			while (it != end())
			{
				it = erase(it);//删除当前节点之后迭代器就会 失效，所以要用it来接收下一个节点的迭代器
			}
		}
	}
	void push_back(const T& data)//尾插
	{
		//Node* tail = _head->_prev;

		//Node* newNode = new Node(data);//申请节点
		三个节点的相互链接
		//tail->_next = newNode;
		//newNode->_prev = tail;

		//_head->_prev = newNode;
		//newNode->_next = _head;
		insert(end(), data);//调用任意节点的插入来实现头删
	}
	void pop_back()//尾删
	{
		//assert(_head->_next != _head);//除了头结点还有其他节点——因为头结点是不可以被删除的
		//Node* tail = _head->_prev;//找到尾节点
		断开链接
		//Node* newtail = tail->_prev;//找新的尾节点
		进行头尾链接
		//newtail->_next = _head;
		//_head->_prev = newtail;
		//delete tail;//删除尾节点
		//调用erase进行尾删
		erase(--end());
	}
	void push_front(const T&data)//头插
	{
		//Node* newHead = new Node(data);//申请新的节点
		//Node* oldHead = _head->_next;
		进行链接
		//_head->_next = newHead;
		//newHead->_prev = _head;

		//newHead->_next = oldHead;
		//oldHead->_prev = newHead;
		//调用任意节点的插入和删除
		insert(begin(), data);
	}
	void pop_front()//头删
	{
		//assert(_head->_next != _head);//除了头结点还有其他节点——因为头结点是不可以被删除的
		//Node* head = _head->_next;//找到头节点
		断开链接
		//Node* newHead = head->_next;//找新的尾节点
		进行链接
		//newHead->_prev = _head;
		//_head->_next= newHead;
		//delete head;//删除尾节点
		//调用erase进行头删
		erase(begin());
	}
	
	void insert(iterator  pos, const T& data)//
	{
		//申请新节点
		Node* newNode = new Node(data);
		Node* prev = pos._node->_prev;//迭代器前一个节点
		Node* next =pos._node;//迭代器当前节点
		prev->_next = newNode;
		newNode->_prev = prev;
		next->_prev = newNode;
		newNode->_next = next;
	}
	iterator erase(iterator pos)//删除pos位置的值
	{
		assert(pos._node !=_head);//不能删除头结点
		Node* cur = pos._node;
		Node* prev = pos._node->_prev;
		Node* next = pos._node->_next;
		//断开当前迭代器所在节点的位置，将迭代器前后节点进行链接
		prev->_next = next;
		next->_prev = prev;
		//保存下一个位置的迭代器
		iterator  it1= ++pos;//记录下一个位置的迭代器
		//删除当前迭代器的节点

		delete cur;
		cur = nullptr;
		return it1;//返回下一个位置的迭代器
	}
private:
	Node* _head;//头结点
};
}

1.构造函数和析构函数

        1.1构造函数

        构造函数主要完成的是对头结点的初始化，如下：

template<class T>//先定义结点类
struct __list_node
{
	__list_node(const T& data = T())//构造函数函数
		:_prev(nullptr)
		, _next(nullptr)
		, _data(data)
	{ }
	__list_node<T>* _prev;//前指针
	__list_node<T>* _next;//后指针
	T _data;//数据
};
template<class T>//构造函数多头结点进行初始化
list()//构造函数
		:_head(new Node)
{
	_head->_next = _head;
	_head->_prev = _head;
}

        2.2析构函数 

        析构函数主要完成对资源的清理，这里通过调用clear对链表的节点进行删除。最后在删除头结点。 

~list()
{
	clear();//删除头结点以外的其他节点
	delete _head;//删除头结点
}

2.operator=的重载和拷贝构造函数

        2.2拷贝构造

        这里是通过对头结点进行初始化，之后调用push_back函数尾插数据，完成的拷贝构造。 

list(const list<T>& l1)//拷贝构造
{
	_head = new Node;//初始化头结点
	_head->_next = _head;
	_head-> _prev = _head;
	const_iterator it = l1.begin();
	while (it != l1.end())
	{
			push_back(it._node->_data);//将节点插入
			++it;
	}
}

        2.2operator=的重载 

        operator=赋值有两种写法，一种是传统写法另一种是现代写法，如下：

//传统写法--
list<T>& operator=(const list<T> l1)
{
	if (this != &l1)//防止对象自己给自己赋值
	{
		clear();//先清理之前链表中的内容,然后通过调用push_back将l1中的内容插入
		const_iterator it = l1.begin();
		while (it != l1.end())
		{
		    push_back(it._node->_data);//将节点插入
			++it;
		}
		return *this;
	}
}
//现代写法
list<T>& operator=(list<T> l1)//现代写法
{
	if (this != &l1)//先拷贝构造一个对象,然后调用STL中的swap函数交换this指向的头结点的指针和 
	{               //l1中头结点指针，出了作用域临时对象l1就会被析构，不要担心内存泄漏的问题
		swap(_head, l1._head);
	}
return *this;
}

3.迭代器的实现

        list的迭代器比较特殊，他不是原生的指针，而是将节点的指针进行封装，然后重载operator*，operator++,operator--等与指针相关的操作符来模拟指针的行为。 

        3.1普通迭代器

    template<class T>
	struct __list_node
	{
		__list_node(const T & data = T())//构造函数函数
			:_prev(nullptr)
			,_next(nullptr)
			,_data(data)
		{ }
		__list_node<T>* _prev;//前指针
		__list_node<T>* _next;//后指针
		T _data;//数据
	};
	template<class T>
	struct __list_iterator//对链表的节点进行封装
	{
		typedef __list_node<T> Node;
		__list_iterator(Node*node)//构造函数
			:_node(node)
		{ }
		//对指针行为的模仿
		T& operator* ()
		{
			return _node->_data;
		}
		__list_iterator<T>& operator++()//前置++
		{
			_node = _node->_next;
			return *this;
		}
		__list_iterator<T>& operator--()//前置--
		{
			_node = _node->_prev;
			return *this;
		}
		__list_iterator<T> operator++(int)//后置++
		{
			Node tmp(_node);
			_node = _node->_next;
			return tmp;
		}
		__list_iterator<T> operator--(int)//后置--
		{
			Node tmp(_node);
			_node = _node->_prev;
			return tmp;
		}
		bool operator==(const __list_iterator<T>&it)
		{
			return _node == it._node;
		}
		bool operator!=(const __list_iterator<T>& it)
		{
			return _node != it._node;
		}
		T* operator->()
		{
			return &(_node->_data);
		}
	public:
		Node  *_node;//存放一个节点的指针
	};
	

        注意：实现operator->的意义，如果有下面的这种情况，list存的不是一个内置类型而是一个自定义类型，这时想要通过迭代器去访问里面的成员，就会用来operator->,如下：

    class Date
	{
	public:
		Date()
			:_year(0)
			, _month(1)
			, _day(1)
		{ }
	public:
		int _year;
		int _month;
		int _day;
	};
    void TestList2()
	{
		list <Date> l1;
		Date d1, d2;
		l1.push_back(d1);
		l1.push_back(d2);
		list<Date>::iterator it = l1.begin();
		cout << it->_year << it->_month << it->_day;//访问list中存放的Date
	}

         其实 it->_year是it->_node->_year,只是编译器对其进行了简化。

        3.2const类型的迭代器

        const类型的对象只能使用const类型的迭代器，那么const类型的迭代器如何实现呢、需要再重新封装吗，像上面那样，可以，但是没有必要，因为那样代码的冗余度就会很高，我们只需要给模板增加两个参数就可以了。template<class T, class Ref, class Ptr>。实现如下：

template<class T, class Ref, class Ptr>
struct __list_iterator//对链表的迭代器进行封装
{
	typedef __list_node<T> Node;
	typedef __list_iterator< T,  Ref,  Ptr> iterator;
	__list_iterator(Node* node)//构造函数
		:_node(node)
	{ }
	//对指针行为的模仿
	Ref operator* ()
	{
		return _node->_data;
	}
	Ptr operator->()
	{
		return &(_node->_data);
	}
	iterator& operator++()//前置++
	{
		_node = _node->_next;
		return *this;
	}
	iterator& operator--()//前置--
	{
		_node = _node->_prev;
		return *this;
	}
	iterator operator++(int)//后置++
	{
		//Node tmp(_node);
		iterator tmp(*this);
		_node = _node->_next;
		return tmp;
	}
	iterator operator--(int)//后置--
	{
		//Node tmp(_node);
		iterator tmp(*this);

		_node = _node->_prev;
		return tmp;
	}
	bool operator==(const iterator& it)
	{
		return _node == it._node;
	}
	bool operator!=(const iterator& it)
	{
		return _node != it._node;
	}
	
public:
	Node* _node;//存放一个节点的指针
};

        这样看，貌似看不出来这两个参数有什么用，这两个参数一个代表T*，一个代表T&，这样就可以解决代码冗余的问题，在实例化的时候给模板不同的参数就可以实例化不同的内容

4.增删查改

        4.1尾删尾插

	void push_back(const T& data)//尾插
	{
		Node* tail = _head->_prev;

		Node* newNode = new Node(data);//申请节点
		//三个节点的相互链接
		tail->_next = newNode;
		newNode->_prev = tail;

		_head->_prev = newNode;
		newNode->_next = _head;
		
	}
	void pop_back()//尾删
	{
		assert(_head->_next != _head);//除了头结点还有其他节点——因为头结点是不可以被删除的
		Node* tail = _head->_prev;//找到尾节点
		//断开链接
		Node* newtail = tail->_prev;//找新的尾节点
		//进行头尾链接
		newtail->_next = _head;
		_head->_prev = newtail;
		delete tail;//删除尾节点
	}

        4.2任意位置的插入和删除

    void insert(iterator  pos, const T& data)//
	{
		//申请新节点
		Node* newNode = new Node(data);
		Node* prev = pos._node->_prev;//迭代器前一个节点
		Node* next =pos._node;//迭代器当前节点
		prev->_next = newNode;
		newNode->_prev = prev;
		next->_prev = newNode;
		newNode->_next = next;
	}
	iterator erase(iterator pos)//删除pos位置的值
	{
		assert(pos._node !=_head);//不能删除头结点
		Node* cur = pos._node;
		Node* prev = pos._node->_prev;
		Node* next = pos._node->_next;
		//断开当前迭代器所在节点的位置，将迭代器前后节点进行链接
		prev->_next = next;
		next->_prev = prev;
		//保存下一个位置的迭代器
		iterator  it1= ++pos;//记录下一个位置的迭代器
		//删除当前迭代器的节点

		delete cur;
		cur = nullptr;
		return it1;//返回下一个位置的迭代器
	}

         4.3头插头删

        头插头删可以复用上面的insert和erase，如下：文章来源地址https://www.toymoban.com/news/detail-490978.html

	void push_front(const T&data)//头插
	{
		insert(begin(), data);
	}
	void pop_front()//头删
	{
		erase(begin());
	}

 5.测试代码

#include<assert.h>
#include"list.hpp"
 void Print(const qyy::list<int>& l1);
 //测试
void TestList()
{
	qyy::list<int>l1;
	//头删
	l1.push_back(1);
	l1.push_back(2);
	l1.push_back(3);
	l1.push_back(4);
	l1.push_back(5);
	for (auto& e : l1)
	{
		cout << e << " ";
	}
	cout << endl;
	Print(l1);
	//尾删
	l1.pop_back();
	l1.pop_back();
	l1.pop_back();
	l1.pop_back();
	l1.pop_back();


}
void Print(const qyy::list<int>   &l3)
{
	qyy::list<int>::const_iterator it = l3.begin();
	while (it != l3.end())
	{
		//*it = 1;
		cout << *it << " ";
		it++;
	}
	cout << endl;
}
void TestList2()
{
	qyy::list<int> l2;
	//头插
	l2.push_front(1);
	l2.push_front(2);
	l2.push_front(3);
	l2.push_front(4);
	l2.push_front(5);
	l2.push_front(6);
	for (auto& e : l2)
	{
		cout << e << " ";
	}
	//头删
	l2.pop_front();
	l2.pop_front();
	l2.pop_front();
	l2.pop_front();
	l2.pop_front();
	l2.pop_front();
	//l2.pop_front();
	//l2.clear();
}
void TestList3()
{
	qyy::list<int> l3;
    //头插
	l3.push_back(1);
	l3.push_back(2);
	l3.push_back(3);
	l3.push_back(4);
	l3.push_back(5);
	for (auto& e : l3)
		cout << e << " ";
	qyy::list<int> l4(l3);
	l3 = l4;//测试operator=
}

到了这里，关于list的模拟实现的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！