list 实现链表封装节点的底层逻辑：如何克服不连续无法正常访问挑战

胖咕噜的稞达鸭

发布于 2025-10-22 14:59:37

2300

代码可运行

文章被收录于专栏：C++初阶高阶C++初阶高阶

运行总次数：0

代码可运行

list 功能实现

关于迭代器的申明：功能：iterator/reverse_iterator/const_iterator/const_reverse_iterator 性质：单向：forward_list/unordered_map… 只能迭代器++ 双向：list/map/set… 迭代器++/– 随机：vector/string/deque… 迭代器++/–/+/-

list的遍历

#include<iostream>
#include<list>
#include<algorithm>
using namespace std;


void test_list1()
{
	list<int>It;
	It.push_back(1);
	It.push_back(2);
	It.push_back(3);
	It.push_back(4);
	It.push_back(5);

	list<int>::iterator it = It.begin();
	while(it!=It.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;
	//能用迭代器遍历就可以用迭代器
	for (auto e : It)
	{
		cout << e << " ";
	}
	cout << endl;

	//sort(It.begin(), It.end());//不支持,要求随机迭代器
	string s("dadadaddwdxsxswx");
		cout << s << endl;
		sort(s.begin(), s.end());//算法进行排序
		cout << s << endl;//按照ASCII码表进行排序
}

插入（emplace_back和push_back的区别）

struct A
{
public:
	//普通构造函数：带默认参数，初始化成员_a1,_a2
	A(int a1 = 1, int a2 = 1)//如果不传递参数则默认使用a1=1,a2=1
		:_a1(a1)
		, _a2(a2)
	{ 
		cout << "A(int a1=1,int a2=1)" << endl;
	}
	//拷贝构造函数：用已有的对象aa初始化新对象
	A(const A& aa)
		:_a1(aa._a1)
		,_a2(aa._a2)
	{
		cout << "A(const A& aa)" << endl;
	}

	int _a1;
	int _a2;
};
void test_list2()
{
	list<A>It;//定义一个存储A类型对象的list容器
	A aa1(1, 1);//调用普通构造函数，创建aa1对象，打印A(int a1=1,int a2=1)
	It.push_back(aa1);//push_back接收对象，会先拷贝aa1生成临时对象，再将临时对象插入容器
	//调用拷贝构造函数打印出A(const A& aa)
	It.push_back(A(2, 2));//调用普通构造函数创建临时对象A（2,2)  打印出A（int a1-1,int a2=1)
	//再调用拷贝构造函数，将临时对象拷贝到容器，打印：A（const A& aa)
	//It.push_back(3, 3);//这样写会报错

	It.emplace_back(aa1);//直接在容器内部构造对象，通过拷贝构造初始化打印A(const A& aa)
	It.emplace_back(A(2, 2));//调用普通构造函数创建A（2，2），打印A（int a1=1,int a2=1)
	//再调用拷贝构造函数，在容器内部构造，打印A（const A& aa)
	It.emplace_back(3, 3);//直接传构造A对象的参数emplace_back
	//直接在容器内部调用普通构造函数参数（3，3）打印出A(int a1=1,int a2=1)
	cout << endl;
	/*list<int>It;
	It.push_back(1);
	It.emplace_back(1);
	It.emplace_back(2);
	It.emplace_back(3);
	It.emplace_back(4);
	It.emplace_back(5);*/

	//for (auto e : It)
	//{
	//	cout << e << " ";
	//}
	//cout << endl;
}

看注释了解~

插入，删除和查找

void test_list3()
{
	list<int>It;
	It.push_back(1);
	It.push_back(2);
	It.push_back(3);
	It.push_back(4);
	It.push_back(5);

	auto it = It.begin();
	int k = 3;
	while (k--)
	{
		++it;
	}
	It.insert(it, 30);//在第三个位置插入30
	for (auto e : It)
	{
		cout << e << " ";
	}
	cout << endl;

	int x = 0;
	cin >> x;
	//find是用算法实现的
	it = find(It.begin(), It.end(), x);//在迭代器区间内部找到输入的x值并且删除
	if (it != It.end())
	{
		It.erase(it);
	}
	for (auto e : It)
	{
		cout << e << " ";
	}
	cout << endl;
}

排序和逆置

void test_list4()
{
	list<int>It;
	It.push_back(1);
	It.push_back(2);
	It.push_back(3);
	It.push_back(4);
	It.push_back(5);

	for (auto e : It)
	{
		cout << e << " ";
	}
	cout << endl;
	//It.reverse();//逆置方式1

	//reverse(It.begin(), It.end());//逆置方式2
	It.sort();//排序，升序
	//降序 仿函数
	//less<int>ls;//升序
	//greater<int>gt;//降序
	It.sort(greater<int>());

	for (auto e : It)
	{
		cout << e << " ";
	}
	cout << endl;
}

链表接连

void test_list5()
{
	//一个链表节点转移给另一个链表
	std::list<int>mylist1, mylist2;
	std::list<int>::iterator it;

	for (int i = 1; i <= 4; i++)
		mylist1.push_back(i);//mylist1:1 2 3 4 
	for (int i = 1; i <= 3; ++i)
		mylist2.push_back(i * 10);//mylst2:10 20 30

	it = mylist1.begin();
	++it;

	mylist1.splice(it, mylist2);//mylist1:1 10 20 30 2 3 4 
	                            //mylist2:empty
	                            //it 指向2的位置

	//用来调整当前节点的数据顺序
	list<int>It;
	It.push_back(1);
	It.push_back(2);
	It.push_back(3);
	It.push_back(4);
	It.push_back(5);

	for (auto e : It)
	{
		cout << e << " ";
	}
	cout << endl;
	int x = 0;
	cin >> x;
	it = find(It.begin(), It.end(), x);//找到x的数据
	if (it != It.end())
	{
		//It.splice(It.begin(),It,it);//从It上截取it指向的位置的数据插入到It.begin()的位置
		It.splice(It.begin(), It, it, It.end());//在It上截取it指向位置的数据一直截取到整段数据结束，插入到It.begin的位置
	}
	for (auto e : It)
	{
		cout << e << " ";
	}
	cout << endl;
}

底层实现

刚刚我们已经认识到了list的常见的几个接口接着来实现list的模拟实现这里我们先来打一个结构：实现链表需要一个哨兵位，哨兵位指向一个一个的单独节点，这里的单独节点我们将用一个类模板定义一个结构来搭建。这里我们定义一个名为list_node 的类，用于表示链表的节点，每一个节点都有自己存储的数据T_data，类型由模板参数T决定。前驱节点的指针list_node<T>* _prev，后继节点的指针list_node<T>* _next，实现双向链表的结构。在命名空间Keda下，定义一个双向链表的节点类list_node和list的框架，利用模板实现泛型，可以存储任意类型的数据。然后实现一个无参数的初始化，也就是让_head的前驱指针和后继指针都指向_head;

#pragma once
namespace Keda
{
	template<class T>
	struct list_node
	{
		T_data;
		list_node<T>* _next;
		list_node<T>* _prev;

		list_node(const T& data=T())//也可以考虑提供默认构造,缺省参数要给T的匿名对象
				:_data(data)
				,_next(nullptr)
				,_prev(nullptr)
		{}
		
	};
	template<class T>
	class list
	{
		typedef list_node<T>Node;//用来简化，将类名缩短，用于后续编码
	public:
		typedef list_iterator<T>iterator;
		iterator begin()
		{
			return _head->_next;
		}
		iterator end()
		{
			return _head;
		}
		
		list(）
		{
			_head=new node{T());//需要实现合适的默认构造，传参要传匿名对象，适用于多种类型
			_head->next=_head;
			_head->prev=_head;
		}
	private:
		Node* _head;//哨兵位的头节点
	};
}

迭代器设计遍历链表：

实现逻辑：逐步解析

为什么用原生指针访问下一个节点在list中做不到？

下标加上[]不是所有容器都可以支持其遍历，迭代器可以完美的兼容所有容器，这里是链表构造，++下一个节点遍历不到，因为节点和节点之间的地址是不连续的，所以考虑用运算符重载进行封装。用原生的指针解引用就是当前节点，++之后是下一个位置，比如说vector和string，但是链表做不到，所以链表要遍历拿到下一个节点位置，就需要用一个类去封装，然后operator* 操作挖掘到下一个节点的位置。

这里为什么用struct封装类，用class可以吗？

struct纯公有，就可以不断去访问_next,_prev等，如果用class ，属于私有，还要用友元函数，无形增加了很多不必要的麻烦。

实现逻辑逐步解析

声明一个结构体list_iterator用于实现链表的迭代器，再声明一个指针_node,指向list_node<T>类型的节点（即迭代器当前指向的链表节点）重载解引用运算符* ，这个运算符的作用是当对迭代器执行*操作时，返回当前节点中存储的数据的引用（T&可以直接修改容器中的元素，避免拷贝开销） Self& operator++重载前置递增运算符++，返回自身引用以支持连续递增操作

实现一个list_operator(Node* node)构造函数声明，参数Node* node是一个指针，指向list_node<T>类型的节点，当创建一个list_iterator迭代器对象时，必须给他指定一个链表节点，构造函数会让这个迭代器指向指定的节点，这样迭代器后续就会基于这个节点去遍历，访问元素了。

template<class T>
struct list_iterator
{
	typedef list_node<T> Node;//定义一个别名便于后续代码简写
	typedef list_iterator<T> Self;//方便在结构体内部引用自身类型
	Node* _node;//声明一个指针_node，指向list_node<T>类型的节点（迭代器当前指向的链表节点）

	list_iterator(Node*node)
		:_node(node)
	{}

  T& operator*()//重载解引用运算符* 
  {
  		return _node->_data;
  	}
	Self& operator++()const
	{
	   _node=_node->_next;
	   return *this;
	}
	Self& operator--()const
	{
		_node=_node->prev;
		return *this;
	}
	Self operator--(int)
	{
		Self tmp(*this);
		_node=_node->_prev;
		return tmp;
	}
	Self operator++(int)
	{
		Self tmp(*this);
		_node = _node->_next;
		return tmp;
	}
}

list_node(const T& data=T())//也可以考虑提供默认构造,缺省参数要给T的匿名对象这样设置的逻辑是什么？

1.对于内置类型（int,double等）：T()就是0，0.0，或者nullptr， 2.如果是自定义类型就要调用默认构造，string,vector等

重载迭代器比较等于与否

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

迭代器还要模拟实现operator->，因为它模拟的是指针

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

	struct AA
	{
		int _a1 = 1;
		int _a2 = 1;
	};

	void test_list1()
	{
		list<int>It;
		It.push_back(1);
		It.push_back(2);
		It.push_back(3);
		It.push_back(4);
		It.push_back(5);

		list<int>::iterator it = It.begin();
		while (it != It.end())
		{
			cout << *it << " ";
			++it;
		}
		cout << endl;

		list<AA>Ita;
		Ita.push_back(AA());
		Ita.push_back(AA());
		Ita.push_back(AA());
		Ita.push_back(AA());

		list<AA>::iterator ita = Ita.begin();
		while (ita != Ita.end())
		{
			//cout << (*ita)._a1 << ": " << (*ita)._a2 << endl;
			cout << ita->_a1 << ": " << ita->_a2 << endl;
			++ita;
		}
		cout << endl;

	}
}

为什么这么奇怪？实际上这有两个箭头，cout<<ita.operator->()->_a1<<" :" <<ita.operator->()->_a2<<endl;ita.operator->()实现的是调用返回AA*，再去解引用返回AA中_a1和_a2的值，所以这里做了特殊处理，本来是两个，为了可读性，省略了一个。

实现const_iterator和iterator的操作

频繁定义可修改的普通迭代器iterator和不可修改的const_iterator迭代器，会让整个代码都显得冗余，所以在这里看看库里面的源代码是如何实现的？

typedef _list_iterator<T,T&, T*>//这个是针对普通迭代器来说
typedef _list_iterator<T,const T&,const T*>//const_iterator

template<class T,class Ref,class Ptr>

typedef Ptr pointer;
typedef Ref reference;

reference operator* (){return (*node).data;}
pointer operator*()const {return &(operator*());}

假设数据类型是T,同一个类模板，增加两个模板参数来实现，这样就不用写两个类了。

链表尾插

void push_back（const <T>& x)
{
	Node* newnode=new node(x);
	Node* tail=_head->_prev;

	tail->_next=newnode;
	newnode->_prev=tail;
	_head->_prev=newnode;
	newnode->_next=_head;

	++_size;
}

void insert(iterator pos,const <T>& x)
{
	Node* cur=pos._node;
	Node* prev=cur->_prev;

	Node* newnode=new node(x);
	//prev newnode cur
	cur->_prev=newnode;
	newnode->_next=cur;
	newnode->_prev=prev;
	prev->_next=newnode;

	++_size;
}

实现头插尾插可以直接复用insert

void push_front(const<T>& x){	insert(begin(),x);}
void push_back(const <T>& x) {	insert(end(),x);}

删除节点的指针

void erase(iterator pos)
{
	assert(pos!=end());//删除不可以删除掉哨兵位的头节点
	Node* prev=pos._node->prev;
	Node* next=pos._node->next;

	prev->_next=next;
	next->_prev=prev;
	delete pos._node;

	--_size;
}

尾删头删

void pop_back()
{
	erase(--end());//end()是链表的最后一个节点，前置--删除掉
}

void pop_front()
{
	erase(begin());
}

总结：本节最重要的就是迭代器对节点的指针进行封装实现，需要认真了解。

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-10-07，如有侵权请联系 cloudcommunity@tencent.com 删除

指针

list

对象

链表

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

登录后参与评论

0 条评论

热度