list的模拟实现

前言

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

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，如下：

	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=
}