c++中的链表list的模拟实现

分类:热门推荐日期:2024-05-02浏览:1评论:0

拖更了半个月，我终于来填c++的坑啦。上次我们说的vetcor不知道小伙伴还记得多少呢？今天我们要讲list的模拟实现。

目录

  • 架构
    • 结点
    • list表的结构
    • 构造函数
    • 尾插push_back()
    • 尾删pop_back()
    • 计算个数：size()
    • 判断空empty()
    • ※迭代器问题
      • 普通迭代器
        • 迭代器主体
        • begin()和end()
        • operator*()
        • 前置++ operator++()
        • 后置++ operator++(int)
        • 前置-- operator--()
        • 后置-- operator--(int)
        • 重载不等于 operator!=(const Self& rhs)
        • 重载箭头 operator->()
        • const迭代器问题
          • 解决方法一：创建新的类。
          • 解决方法二：模板
          • 在某个位置前插入 insert()
          • 删除某位置的值 erase()
          • 清空链表 clear()
          • 拷贝构造
          • 析构函数
          • 问题
          • 实现整体代码

            架构

            我们之前也写过c语言版本的链表，当时很麻烦，还要传二级指针。但是现在不用了引用就能解决。我们先把大体的架构搭出来。

            结点

            list是一个个的结点指针链接，而且我们看手册的时候，会发现ist是一个双向带头的链表。所以我们先写节点的代码加粗样式。

            templatestruct ListNode
{//为什么要用struct？其实用class也ok，但是要整个public，因为节点我希望你可以随时申请，所以不能弄成私有。
	ListNode(const T& val=T())
		:_prev(nullptr)
		,_next(nullptr)
		,data(val)
	{}
	ListNode* _prev;
	//为什么是ListNode*的指针呢？因为我们将来要指向
	//ListNode类型的节点。
	ListNode* _next;
	T data;
};

            list表的结构

            我们也说了是双向带头链表，所以list一定要有头结点。

            templateclass list
	{public:
		typedef ListNode Node;
	private:
		Node* _head;//头结点是一个节点指针类型。
		size_t _size;//因为库中有size这个接口，这里存一个会方便一点。
	};

            构造函数

            在我们之前实现过得带头双向链表，在刚开始的时候，就是对头结点进行处理，让头结点的前后指针指向自己。

            list()
		{_head = new Node;//给头一个空间
			_head->_prev = _head;
			_head->_next = _head;
			_size = 0;
		}

            尾插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
}

            尾删pop_back()

            尾删也是老朋友了。话不多说如图：

            简单叙述过程：就是先找到尾巴，然后保存一起来(方便我们删除)。然后将指针链接到尾删的前一个值。

            void pop_back()
{Node* tail = _head->_prev;//保存
	_head->_prev = tail->_prev;//更改指向
	tail->_prev->_next = _head;
	delete tail;//删除节点
	_size--;//别忘了修改个数
}

            计算个数：size()

            这个就很简单了，因为我们内置了个数，所以直接返回就好了。

            size_t size()
{return _size;
}

            判断空empty()

            bool empty()
{return _size == 0;
}

            ※迭代器问题

            链表的迭代器很麻烦，不像vector那样用下标访问就可以的我们先把迭代器的主体写出来，分析一下，我们都需要什么吧。

            bit::list::const it = lt2.begin();
while (it != lt2.end())
{std::cout << *it << " ";
	it++;
}

            我们平时访问数据的时候就这些，例如：迭代器本身、*星号、begin()、end()、自增++。那怎么写呢？

            普通迭代器

            问题：迭代器本身怎么写，还用T* 吗？写在list中码？(一定要思考这个问题！)

            答案：不不不，我问你的自增，你在增谁？增加的list还是迭代器？我们要写operator++()，你一定要明白是谁在++。如果你把迭代器写到list中，你operator++()自增的是谁？一定要把这个问题想清楚。

            自增的迭代器本身。那么我们的自增就不能写到list中，也就表示迭代器不能写在list中。那么我们就需要另外写一个类封装了。OK！开写！

            迭代器主体

            我们要遍历这个list链表的时候，我们一定要有这个地方的节点指针，我们才能访问这里的数据对吧，所以里面的成员变量是Node* _node;

            templateclass List_Iterator
{public:
	typedef ListNode Node;
	Node* _node;
	List_Iterator(Node* node)
		:_node(node)
	{}
};

            begin()和end()

            begin()和end()多好写，begin()是返回数据的开始和end()返回头结点(有效数据的下一个)。

            问题：你写在哪？list类？还是iterator类？

            答：思考一下，你的数据在哪？你的数据在list 里面对吧，我要访问遍历数据，我去哪里拿数据？list中，那么你的begin()和end()一定不能写在iterator。begin()和end()应该写在list中。

            templateclass list
	{public:
		typedef ListNode Node;
		iterator begin()
		{//这里存在单参数构造函数的隐式类型转换
			//按道理 return iterator(_head->next);
			//应该是这样的，匿名对象，但是单参数的构造函数可以进行隐式类型转换。
			return _head->_next;
		}
		iterator end()
		{return _head;
		}
	private:
		Node* _head;//头结点是一个节点指针类型。
		size_t _size;//因为库中有size这个接口，这里存一个会方便一点。
	};

            operator*()

            因为我们遍历一般都是要打印出它的值，所星号也是必不可少的。星号表示解压用。那么我们只需要返回当前节点的值就可以了。

            T& operator* ()
{return _node->data;
}

            前置++ operator++()

            自增很简单，我们只需要下一个节点的指针就好，那么我们怎么找到下一个节点呢？是不是当前节点的_next?那就更简单了。

            List_Iterator& operator++()
{//this->_node= this->_node->_next;
	_node= _node->_next;
	return *this;
}

            后置++ operator++(int)

            后置++，就是我们创建一个临时变量，然后返回临时变量，但是让实际已经指向下一个节点了。注：不能返回引用，因为是临时变量。

            List_Iterator operator++(int)
{List_Iterator tmp(*this);
	_node = _node->_next;
	return tmp;
}

            前置-- operator–()

            为什么要重载自减呢？是因为有些地方我们还是有需要的，所以就直写了。

            List_Iterator & operator--()
{_node= _node->_prev;
	return *this;
}

            后置-- operator–(int)

            List_Iterator operator--(int)
{Self tmp(*this);
	_node = _node->_prev;
	return tmp;
}

            重载不等于 operator!=(const Self& rhs)

            问题：在比较的时候，我们比的是节点指针还是数值呢？

            答：节点指针！数值可能重复。

            bool operator!=(const Self& rhs )
{return rhs._node != _node;
}

            重载箭头 operator->()

            为什么要重载operator->？我们一直用int内置类型来作为样例，这没有问题，但是我想问你，你的list只存int吗？没有自定义类型吗？如果我希望能存一个student类呢？可能你说(*it).成员变量也可以啊，但是你觉得方便吗？所以我们要重载->。

            箭头的运算符重载：

            从图上我们能发现，他隐藏了一个箭头，他应该是it.operator->()->_a1;但是事实上只有意见箭头，就表明了，他隐藏了一个箭头。

            T* operator->()
{return &_node->data;
}

            const迭代器问题

            以上，我们用的都是普通的迭代器，那么const迭代器怎么写呢？你会说，我知道了！只要让他不改变不就好了？OK！说干就干。显示就是，依然改了，并没有用。

            解决方法一：创建新的类。

            问题就出在了你迭代器本身，你的返回值依然是普通的，我依然可以改。那你突然灵光一现，我在写一个const_ListIterator类就好了！好说干就干。你用了一下，真好用。但是你有没有发现代码很冗余？唯独只有operator*()和operator->()的返回值改变了，因为在拿取值的时候，我们要返回const类型的。

            templateclass List_ConstIterator
{public:
	typedef ListNode Node;
	typedef List_ConstIterator 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;
	}
};

            解决方法二：模板

            我们上面也说只是两个成员函数的返回类型不同，那么我们在处理返回类型不同的时候怎么做的呢？对！就是模板！模板是不是可以传不同类型呀？那么我们就只需要改一下。

            list类中：

            templateclass List_Iterator
{public:
	typedef ListNode 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;
	}
};

            在某个位置前插入 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
}

            删除某位置的值 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;*/
		}

            清空链表 clear()

            注意，我们清空的链表，不需要清头指针，所以直接用迭代器，pop_back()就可以了。

            void clear()
{iterator it = begin();
	while (it != end())
	{it = erase(it);
	}
	_size = 0;
}

            拷贝构造

            拷贝构造这里有几个问题。

            问题1：直接push_back()可以吗？

            答：不可以。你的头指针没有初始化，都是空，插入直接空指针访问。所以你需要初始化。

            问题2：用我注释部分的迭代器可以吗？

            答：不行，如果你传进来是一个const类型的迭代器呢？普通迭代器类型不匹配，除非你用auto。

            //lt1(lt2)
list(const list& 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++;
	//}
}

            析构函数

            释放空间，并且还有头结点！！！有些小伙伴以为只用释放各个数据的节点就可以了，但是头结点也是你开出来的空间啊，所以也要记得释放。

            ~list()
{clear();//复用
	delete _head;
}

            问题

            如果我什么都写了，只有拷贝构造没有写，下面图代码对吗？

            答：不对，因为传值传参回去调用拷贝构造，没有写拷贝构造就是浅拷贝，当函数结束 临时对象会被析构。但是浅拷贝导致本对象被析构，当整体结束的时候会导致二次析构。

            实现整体代码

            #pragma once
#include#include
namespace bit {templatestruct ListNode
	{ListNode(const T& val=T())
			:_prev(nullptr)
			,_next(nullptr)
			,data(val)
		{}
		ListNode* _prev;//为什么是ListNode*的指针呢？因为我们将来要指向
		//ListNode类型的节点。
		ListNode* _next;
		T data;
	};
	templateclass List_Iterator
	{public:
		typedef ListNode 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 List_ConstIterator
	//{//public:
	//	typedef ListNode Node;
	//	typedef List_ConstIterator 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;
	//	}
	//};
	templateclass list
	{public:
		typedef ListNode Node;
		typedef List_Iterator iterator;
		typedef List_Iterator const_iterator;
		//typedef List_Iterator iterator;
		//typedef List_ConstIterator 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& 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;
	};
}

相关推荐

关于我们常见问题广告服务免责声明联系我们
Powered By Z-BlogPHP 1.7.3 Theme By 优美主题
Copyright Your WebSite.Some Rights Reserved. 浙ICP备2023018783号