链表的模拟实现

一、list的基本架构🤖

​ 首先list是很多不同空间上的结点，再将其连接起来的一个结构。为了我们再list类中可以很好地使用结点，所以我们将结点也设计成一个类，一个公开的类。

因为我们要设计成一个公开的类，所以我们使用struct来设计类。

_list_node

template<class T>
struct _list_node
{_list_node(const T& val = T()):_val(val), _prev(nullptr), _next(nullptr){}T _val;_list_node<T>* _prev;//模板这个也是需要加T的_list_node<T>* _next;
};

​ 将结点设计成类，结点的构造函数可以轻松搞定我们以前c语言版本的buynode()功能！

我们稍微解释一下，为什么上述val的缺省参数为什么写成T()，在c++中，其实认为不仅仅是自定义类型有构造函数，像int，double这种内置类型也有他们对应的构造函数。如果val的缺省参数写成0，是不准确的，因为T有可能是string类型，T()就可以解决这种问题，无论是什么类型，都能给出合理的缺省参数。

---

基本构架–双向带头循环链表

​ 那么list的框架我们可以大致确定下来。

template<class T>
class list()
{typedef _list_node<T> node;//重命名之后写listnode类型就很方便public://…………成员函数private:node* _head;}

​ 每个结点之间的连接关系，由list里面的成员函数来处理，所以list的成员数据是要由一个_head头节点即可。

---

二、list的迭代器–重点🐱‍👤

​ 我们学习了string，vector，string的数据是char，它的迭代器是char*，vector的数据是T，它的迭代器是T*，都是数据的地址。在c语言中，就支持地址的++，–，==，!=。

​ 而list的数据是很多的node，按道理来说它的迭代器应该是node*，可是自定义类型的地址不支持++，–，==，!=的，所以要想使node*也能像char*,T*那样操作，我们要将其进行封装，设计成类，然后再设计运算符重载，这样子可以像内置类型一样进行操作了。

list迭代器的基本架构

struct _list_iterator
{typedef _list_node<T> node;//为了方便使用结点类typedef _list_iterator self;//成员函数…………node* _pnode;};

​ 一般在一个类中要使用另一个类，那个这个类使类模板的话，通常会typedef，不然每次使用都要加上模板，很不方便

构造函数–node*封装

_list_iterator(node* pnode):_pnode(pnode)
{}

operator*()–得到值

T& operator*()
{return _pnode->_val;
}

operator!=()–跟另一个迭代器进行比较

bool operator!=(const self& s) const
{return (_pnode != s._pnode);//比较他们的node*地址即可
}

operator++()与operator++(int)

self& operator++()
{_pnode = _pnode->_next;return *this;
}self& operator++(int)//编译器默认使后置++
{self tmp(*this);_pnode = _pnode->_next;return tmp;
}

​ ++之后，变成下一个结点，通过结点的next即可，达到需求。

operator–()与operator–(int)

self& operator++()
{_pnode = _pnode->_next;return *this;
}self& operator++(int)
{self tmp(*this);_pnode = _pnode->_next;return tmp;
}

operator->()

​ 有些同学同能会很异或，operator->是什么意思，当node里面的数据是自定义类型时，自定义类型的地址是支持->的用法的

T* operator->()
{return &_pnode->_val;//返回自定义类型的地址
}

​ 返回数据的地址，这样就可以使用->了

其实这里编译器进行了一层优化，导致这个地方不太好理解,例如我用list创建了一个对象l, l->会去调用operator->得到地址，得到地址再

->才可以得到自定义类型的内容。

所以正确写法应该是l->->,但是这样使得可读性非常差，所以编译器优化成了一个->

---

​ 那么迭代器的的基本接口就实现完成了，但是我们要实现常量带迭代器怎么办？常规来说，是不是也要设计成一个自定义类型对不对。但是我们思考一下，常量迭代器与迭代器很多逻辑都是一致的，不同的地方是：operator*的返回值是const T&,operator->返回的是const T*,其他地方都是相同的所以，我们在写模板的时候就要这样子写了。

迭代器与常量迭代器的完整版

template<class T,class Ref,class Ptr>
struct _list_iterator
{typedef _list_node<T> node;typedef _list_iterator self;_list_iterator(node* pnode):_pnode(pnode){}Ref operator*()//T&/const T&{return _pnode->_val;}bool operator!=(const self& s) const{return (_pnode != s._pnode);}self& operator--(){_pnode = _pnode->_prev;return *this;}self& operator--(int){self tmp(*this);_pnode = _pnode->_prev;return tmp;}self& operator++(){_pnode = _pnode->_next;return *this;}self& operator++(int){self tmp(*this);_pnode = _pnode->_next;return tmp;}Ptr operator->()//T*/const T*{return &_pnode->_val;}node* _pnode;};

​ 模板类型Ref用来解决operator*的问题，模板类型Ptr用来解决operator->的问题。这样子就很好地解决了代码冗余。

三、实现list的重要接口🙊

​ 从前有一个这样的问题说：你是否能在15分钟之内，将链表的增删查改的给写成来。遇到这种情况你会怎么办？

当然了这个问题肯定不会是让你将list的代码实现背下来，然后疯狂敲，在15分钟之内敲完。那样就纯纯的码农了。

这个问题是想看你的list实现时的代码复用。

我们再把list的架构给总结一遍

template<class T>class list{typedef _list_node<T> node;public:typedef _list_iterator<T,T&,T*> iterator;typedef _list_iterator<T, const T&,const T*> const_iterator;private:node* _head;
}

构造函数–构建哨兵位

list()//list的构造是构造头节点,list初始化
:_head(nullptr)
{_head = new node(T());_head->_next = _head;_head->_prev = _head;
}

begin(),end()

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

​ const知识点，这里不做太多说明了。

注意begin()返回的是第一个结点(头节点的下一个)，而end()返回的不是最后一个结点，而是头节点，这样子就满足了左闭右开

增👹

insert–随机插–在pos的前面插入

iterator insert(iterator pos,const T& val)
{assert(pos._pnode);node* cur = pos._pnode;node* prev = cur->_prev;node* newnode = new node(val);//连接关系prev->_next = newnode;newnode->_prev = prev;newnode->_next = cur;cur->_prev = newnode;return pos;
}

​ 其实就是考一个链接关系，大家画画图就可以很清晰地解决。

注意insert有返回值，大家可以思考一下链表insert还会不会使迭代器失效。不清楚迭代器失效的可以看看博主的这篇文章：

(223条消息) C++迭代器失效你真的理解了吗，看博主用vector的代码实现给你讲清楚迭代器失效以及解决方案！（超详细）_龟龟不断向前的博客-CSDN博客

---

push_back()–尾插

​ 这里我们就可以insert进行复用了

void push_back(const T& val)//必须加上const，否则报错
{insert(end(),val);//在头节点后面的那个节点进行头插,正好就是begin
}

push_front()–头插

​ 继续复用

void push_front(const T& val)
{insert(begin(),val);
}

---

删🐱‍🚀

erase–随机删

iterator erase(iterator pos){assert(pos._pnode);//判断迭代器的节点不是空节点assert(pos != end());//内容为空了，就不能再删了node* cur = pos._pnode;node* prev = cur->_prev;node* next = cur->_next;//连接关系prev->_next = next;next->_prev = prev;delete cur;return (iterator(next));}

注意erase的返回值的写法，使用iterator构造了一个匿名对象进行了返回

返回值–删除元素的下一个元素的迭代器。

pop_back()–尾删

void pop_back()
{erase(--end());
}

pop_front()–头删

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

查改–使用迭代器即可

empty()–判断是否为空，可有迭代器

bool empty()
{return begin() == end();
}

size()–返回元素个数–使用迭代器遍历

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

析构函数~list()

​ 我们要清楚结点，以及头节点。那么我们可以设计一个clear将结点清掉，在析构函数里面再清掉头节点即可。

clear()

void clear()
{iterator it = begin();while (it != end()){it = erase(it);//erase里面已经有了清除功能了，所以咱们直接复用//而且erase的返回值让我们可以做到，就算节点释放了，我们也可以找到下一个节点}
}

​ 我们复用了erase，因为erase也有清理功能。而且erase的返回值可以实现，就先清掉了结点，我也找到了下一个结点。

~list()

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

拷贝构造

list(const list<T>& lt)//构造函数要传引用
{//this构建头节点_head = new node;_head->_next = _head;_head->_prev = _head;//开始赋值--用push_back复用for (auto& x : lt){push_back(x);}
}

​ 复用了迭代器(范围for的原理就是迭代器)和push_back。

思路：1.构建头节点 2.将元素尾插进去

赋值运算符重载

传统写法

list<T>& operator=(const list<T>& lt)
{if (this != &lt)//排除自己给自己赋值{//先clear()--留下一个头节点，然后赋值--用push_back()来复用clear();for (auto& x : lt){push_back(x);}}return *this;
}

​ 先受用clear清空数据，只留下一个头节点，再将数据尾插进去。

现代写法

可以写一个list自己的swap函数

void swap(list<T>& lt)//交换链表很简单，直接交换头节点即可
{::swap(_head, lt._head);
}

list<T>& operator=(list lt)
{swap(lt);return *this;
}

那么list的一些重要接口就实现完成啦。

四、总结一下list接口🤡

其实大家写完就可以发现：list的接口实现有大量的代码复用，除了迭代器比vector要复杂一点，其实他的代码实现是比vector要简单的。

比如：

1. push_back()
2. push_front()
3. pop_back()
4. pop_front()
5. size()
6. clear()
7. 拷贝构造
8. 赋值运算符重载

这些都有很多代码复用，当你实现了他们的基础，这些接口就非常简单了。

但是我们实现的list是无法配合库里面的find()进行使用的，这个等到大家c++越往后学就会理解，看了STL源码剖析就会理解。