list结构刨析与模拟实现

目录

1.引言

2.C++模拟实现

2.1模拟实现结点

2.2模拟实现list前序

1）构造函数

2）push_back函数

2.3模拟实现迭代器

1）iterator

构造函数和析构函数：

*操作符重载函数：

前置/后置++/--：

==/!=操作符重载函数：

->操作符重载函数：

2）const_iterator

2.4模拟实现list后序

3）insert函数

4）erase函数

5）头插头删尾插尾删函数

6）size函数

7）begin/end函数

8）clear函数

9）析构函数

3.完整list

---

1.引言

先来说说为什么要模拟实现库里的list？

我认为，模拟实现list有以下几个意义和好处:

1. 学习：通过自己实现一个类似于STL中的list数据结构，可以加深对数据结构和算法的理解。通过亲自编码实现，能更好地理解list的内部工作原理，以及C++语言中与数据结构相关的特性和语法。

2. 练习：编写一个类似于STL中的list可以作为练习和提升编码能力的手段。这有助于加强对C++语言的掌握，并提高面向对象编程的技能。

3. 定制化需求：有时候，STL中提供的list功能不能完全满足特定需求，此时可以通过自己实现一个list类来扩展或定制list的功能，以更好地适应特定的应用场景。

2.C++模拟实现

      提前声明，由于list不同类型的函数重载太多太杂，本篇仅仅模拟实现简单的构造，析构，操作符重载，深浅拷贝，增删查改等部分函数的介绍，感谢读者的支持！

      建议先创建一个list.hpp头文件，单独创建一个命名空间，防止已经展开了std的命名空间，实现的list与库中list发生冲突。

      我们就定义命名空间为drw，接下来完成三个部分的编写：

2.1模拟实现结点

思路：

1. 我们先来定义一个结构体__list_node来代表list中存放数据的结点，方便list中函数操作等等访问要求
2. 设置一个模板class T来接受各种类型的显式实例化
3. 这里不能将__list_node直接命名为Node是为了防止与其他同名结构体冲突
4. 设置三个成员变量，分别为:prev    next    val，用来储存前后结点以及此处结点的数值
5. 使用初始化列表完成构造和析构函数

实现：

template<class T>
struct __list_node
{__list_node<T>* prev;__list_node<T>* next;T val;__list_node(const T& t=T()):prev(nullptr),next(nullptr),val(t){}~__list_node(){prev = nullptr;next = nullptr;val = 0;}
};

2.2模拟实现list前序

      由于list同样需要模板class T来显式实例化，那么我们先设置一个class T模板参数，为什么是先呢？是因为后面还会有补充，请耐心看完~

      因为list不希望结点被外界访问，将结点进行了封装，所以可以先将__list_node重命名为Node来方便表示，并且只能在public之外重命名，list类中只有一个私有成员变量，就是Node* _head，这代表头结点。接下来完成成员函数：

1）构造函数

思路：

1. 这里我们实现两个构造函数，分别是直接构造和拷贝构造
2. 因为这两种构造都要先初始化一个头结点，我们不妨设置一个Emptyinit函数来做这个事情，方便复用
3. 在Emptyinit函数中，先new一个Node，对val不做处理，让prev指向自己，next也指向自己
4. 直接构造：就是Emptyinit函数的过程，直接复用
5. 拷贝构造：参数是const list<T>& l，除了调用Emptyinit之外还要调用push_back对新的list进行尾插拷贝，这里的push_back后续会讲解

实现：

void Emptyinit()
{Node* guard = new Node;guard->prev = guard;guard->next = guard;_head = guard;
}list()
{Emptyinit();
}list(const list<T>& l)
{Emptyinit();for (auto& e : l)//加上&防止自定义类型深拷贝{push_back(e);}
}

2）push_back函数

思路：

1. 先new一个新结点node，将t传进去初始化node
2. 再将新结点的prev设置为_head的prev，next为_head
3. 更新_head的prev以及原先_head之前结点的next

实现：

void push_back(const T& t)
{Node* newnode = new Node(t);newnode->prev = _head->prev;_head->prev->next = newnode;newnode->next = _head;_head->prev = newnode;//双向带头循环链表，需要复习！
}
void push_back(const T& t)
{insert(_head, t);
}

这里还可以直接调用insert函数，后面介绍！由于后续函数需要迭代器，这里穿插介绍模拟实现迭代器：

2.3模拟实现迭代器

      在使用list的时候，我们知道迭代器可以++/--，但是不能+/-，因为list迭代器属于双向迭代器但不属于随机迭代器，但每个结点存储位置是分散开的啊，这怎么实现++/--呢，于是可以定义一个迭代器结构体，将其封装成类，就可以进行这一操作了！

      设置模板template<class T>，定义__list_iterator，为了方便表示__list_node，这里也提前重命名一下为Node，设置成员变量为node

1）iterator

构造函数和析构函数：

思路：直接使用初始化列表进行赋值nullptr即可，同样赋值nullptr进行析构，因为node已经有默认构造和析构，就不需要更多的处理

实现：

__list_iterator(Node* _node):node(_node)
{ }~__list_iterator()
{node = nullptr;
}

*操作符重载函数：

思路：直接返回node代表的val即可

实现：

T& operator*()
{return node->val;
}

前置/后置++/--：

思路：++：前置就让node指向next即可，后置就拷贝tmp，让node指向next返回tmp

           --：前置node指向prev，后置拷贝tmp，node指向prev返回tmp

实现：

__list_iterator<T>& operator++()//前置
{node = node->next;return *this;
}__list_iterator<T>& operator++(int)//后置
{__list_iterator<T> tmp(*this);node = node->prev;return tmp;
}__list_iterator<T>& operator--()//前置
{node = node->next;return *this;
}__list_iterator<T>& operator--(int)//后置
{__list_iterator<T> tmp(*this);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;}

->操作符重载函数：

思路：为什么要有这个函数？是因为如果list存储的是含有多个成员变量的结构体，那么想要访问成员变量不应该仅仅有*.还应该提供->

      这里直接返回T*类型的&(node->val)即可就不进行实现展示了。

2）const_iterator

思考：const迭代器与iterator相差在哪里呢？无非就是*操作符重载函数多了一些const，其他大致相同，所以我们就不必再去大费周章重新写，这里增加一个模板参数Ref，在显式实例化的时候传T&或者const T&就可以解决这个问题：

       那么这仅仅解决了*函数的重载问题，->函数呢？这当然又需要一个模板参数Ptr，传参方法是一样的。为了简化类型，将 __list_iterator<T, Ref,Ptr> 重命名为self

演示整个迭代器：

template<class T,class Ref,class Ptr>//为什么要传Ref是因为两个结构体太累赘，这样可以简化，要传Ptr是为了给->函数的返回类型也进行模板化
struct __list_iterator
{typedef __list_node<T> Node;typedef __list_iterator<T, Ref,Ptr> self;//这里再次重定义一下方便Node* node;__list_iterator(Node* _node):node(_node){ }Ref operator*(){return node->val;}Ptr operator->()//为什么要重载访问成员操作符呢？是因为显式实例化传参也就是vector里面可能保存的是自定义类型而不是内置类型{return &(node->val);}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& it){return node != it.node;}bool operator==(const self& it){return node == it.node;}~__list_iterator(){node = nullptr;}
};

2.4模拟实现list后序

3）insert函数

思路：

1. insert函数就是在迭代器位置为pos的地方插入数据
2. 开辟一个新结点newnode，将数据传入初始化，记录一下pos的前一个结点地址prev
3. 让prev的next指向newnode，newnode的prev指向prev，newnode的next指向pos，pos的prev指向newnode，返回newnode

实现：

iterator insert(iterator pos, const T& t)
{//无需断言Node* prev = pos.node->prev;Node* newnode = new Node(t);prev->next = newnode;newnode->prev = prev;newnode->next = pos.node;pos.node->prev = newnode;return newnode;
}

4）erase函数

思路：

1. 判断一下pos是否合法，不能删除头结点
2. 记录一下前一个和后一个结点地址，分别为prev和next
3. 让prev的next指向next，next的prev指向prev
4. 释放掉pos结点，返回next的地址，这是防止迭代器失效的措施

实现：

iterator 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;return next;
}

5）头插头删尾插尾删函数

思路：

1. 由于实现了insert和erase，这里直接复用就方便多了

实现：

void push_back(const T& t)
{insert(_head, t);
}void pop_back()
{erase(_head->prev);
}void push_front(const T& t)
{insert(_head->next, t);
}void pop_front()
{erase(_head->next);
}

6）size函数

思路：

1. 要计算链表中的结点个数，但不能算入头结点
2. 定义size_t sz，从头结点的下一个开始遍历，到指针指向_head结束

实现：

size_t size()
{size_t sz = 0;iterator it = begin();while (it != end()){sz++;it++;}return sz;
}

7）begin/end函数

思路：

1. 直接将_head的下一个结点或者_head返回，因为end代表最后一个元素的下一个位置

实现：

iterator begin()
{return _head->next;
}iterator end()
{return _head;
}const_iterator begin()const
{return _head->next;
}const_iterator end()const
{return _head;
}

8）clear函数

思路：

1. clear函数是将list中的每一个结点进行释放删除，相当于清空链表
2. 用循环实现即可，但是要注意迭代器的失效问题！erase之后的迭代器要及时更新

实现：

void clear()
{iterator it = begin();while (it != end()){it=erase(it);//迭代器失效了！！！要注意！！！}
}

9）析构函数

思路：

1. 调用clear函数之后释放掉头结点就完成了析构

实现：

~list()
{clear();delete _head;_head = nullptr;
}

3.完整list

这里给出完整的实现代码：

#pragma once
#include<iostream>
#include<assert.h>
using namespace std;
namespace drw
{template<class T>struct __list_node{__list_node<T>* prev;__list_node<T>* next;T val;__list_node(const T& t=T()):prev(nullptr),next(nullptr),val(t){}~__list_node(){prev = nullptr;next = nullptr;val = 0;}};template<class T,class Ref,class Ptr>//为什么要传Ref是因为两个结构体太累赘，这样可以简化，要传Ptr是为了给->函数的返回类型也进行模板化struct __list_iterator{typedef __list_node<T> Node;typedef __list_iterator<T, Ref,Ptr> self;//这里再次重定义一下方便Node* node;__list_iterator(Node* _node):node(_node){ }Ref operator*(){return node->val;}Ptr operator->()//为什么要重载访问成员操作符呢？是因为显式实例化传参也就是vector里面可能保存的是自定义类型而不是内置类型{return &(node->val);}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& it){return node != it.node;}bool operator==(const self& it){return node == it.node;}~__list_iterator(){node = nullptr;}};//这样实现太过于累赘，最好再添加一个模版参数来实现//template<class T>//struct __const_list_iterator//{//	typedef __list_node<T> Node;//	Node* node;//	__const_list_iterator(Node* _node)//		:node(_node)//	{//	}//	const T& operator*()const//	{//		return node->val;//	}//__const_list_iterator<T>& operator++()//前置//{//	node = node->next;//	return *this;//}//__const_list_iterator<T>& operator++(int)//后置//{//	__const_list_iterator<T> tmp(*this);//	node = node->next;//	return tmp;//}//	bool operator!=(const __const_list_iterator<T>& it)//	{//		return node != it.node;//	}//	bool operator==(const __const_list_iterator<T>& it)//	{//		return node == it.node;//	}//	~__const_list_iterator()//	{//		node = nullptr;//	}//};template<class T>class list{typedef __list_node<T> Node;public:/*typedef __list_iterator<T> iterator;typedef __const_list_iterator<T> const_iterator;*///typedef const __list_iterator<T> const_iterator;//不能这样使用 const迭代器那么迭代器就不能改变了typedef __list_iterator<T, T&, T*> iterator;typedef __list_iterator<T, const T&, const T*> const_iterator;void Emptyinit(){Node* guard = new Node;guard->prev = guard;guard->next = guard;_head = guard;}list(){Emptyinit();}list(const list<T>& l){Emptyinit();for (auto& e : l)//加上&防止自定义类型深拷贝{push_back(e);}}list<T>& operator=(list<T> l){swap(_head, l._head);return *this;}//void push_back(const T& t)//{//	Node* newnode = new Node(t);//	newnode->prev = _head->prev;//	_head->prev->next = newnode;//	newnode->next = _head;//	_head->prev = newnode;//双向带头循环链表，需要复习！//}void push_back(const T& t){insert(_head, t);}void pop_back(){erase(_head->prev);}void push_front(const T& t){insert(_head->next, t);}void pop_front(){erase(_head->next);}iterator begin(){return _head->next;}iterator end(){return _head;}const_iterator begin()const{return _head->next;}const_iterator end()const{return _head;}iterator insert(iterator pos, const T& t){//无需断言Node* prev = pos.node->prev;Node* newnode = new Node(t);prev->next = newnode;newnode->prev = prev;newnode->next = pos.node;pos.node->prev = newnode;return newnode;}iterator 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;return next;}size_t size(){size_t sz = 0;iterator it = begin();while (it != end()){sz++;it++;}return sz;}void clear(){iterator it = begin();while (it != end()){it=erase(it);//迭代器失效了！！！要注意！！！}}~list(){clear();delete _head;_head = nullptr;}private:Node* _head;};
}