list模拟实现

个人主页:小则又沐风个人专栏:数据结构竞赛专栏C语言CLinux座右铭路虽远行则将至事虽难做则必成目录前言节点类迭代器类链表类构造函数析构函数简单的容量的接口迭代器数据的插入和删除inserteraseclear总结前言在之前的文章中,我们学习了C库中的list接口的使用,今天我们来了解一下库中的list是怎么实现的,并且我们来模拟实现一下简单的list的接口节点类我们在数据结构中就知道,list的结构就像是一个一个的火车一样,所以我们在实现我们自己list的时候我们先把这个节点来封装成一个类templateclass T struct listnode { listnode(const T xT()) { _val x; _pre nullptr; _next nullptr; } listnodeT* _pre; listnodeT* _next; T _val; };在这里我们使用的是类的模板,我们的这个节点的实现是依靠一个节点存储的数据,指向下一个节点和指向前一个结点的指针组成的需要注意的是我们这个类是自定义的类型,所以编译器自带的默认构造函数是不可以满足我们的需求的,所以我们需要自己显示的实现构造函数,这个构造函数是非常的简单的,因为我们只需要造出一个节点不需要连接,所以我们指针都是一个个空指针以上我们就把这个节点的类实现好了现在我们来实现一下这个迭代器迭代器类我们在上一篇链表的文章中我们知道这个迭代器也是一个封装好的类,这是因为如果不把他封装好的话,我们想要像和其他的迭代器使用他的话,我们解引用节点得到的并不是节点的数据,而是这个节点,所以为了符合迭代器的使用的习惯,所以我们需要把迭代器进行封装,但是我们知道的是我们在之前的迭代器的实现的时候我们不仅仅实现了普通的迭代器,我们还实现了const的迭代器所以在我们链表的迭代器的封装的过程难道我们需要把这个迭代器的实现写两份吗?并且我们知道的是这两串代码可是高度相似的这时候我们就需要来进一步高级的运用我们的模板参数了templateclass T,class ref,class ptr 在这里我的迭代器的模板参数并不是简简单单的一个,而是三个模板参数,现在我们详细介绍一下这些模板参数有什么作用我们知道我们在类实例化出对象的时候我们的模板类是需要传入模板的参数的,这时候我们就只需要const的传入的是const的参数,普通的传入普通的就行了,编译器会为我们自己实现出两份代码的所以我们只需要把这个模板来封装好就好了在我们的模板中这个ref指的是T或者是const Tptr指的是T*或者是const T*是不是恍然大悟所以我们并不需要两段代码来实现迭代器了,只需要来用通用的模板参数就可以了现在我们解决了代码重复率的问题,现在我们就正式来实现一下这个迭代器的类我们知道的是这个所谓的迭代器就是一个节点的指针typedef listnodeT node; node* _node; listiterator(const listiterator l) :_node(l._node) { }迭代器的构造函数我只写了最常用的一个ref operator*() { return _node-_val; } ptr operator-() { return _node-_val; }在这里我们就使用上了模板参数self operator() { _node _node-_next; return *this; } self operator(int) { self temp(*this); _node _node-_next; return temp; } self operator--() { _node _node-_pre; return *this; } self operator--(int) { self temp(*this); _node _node-_pre; return temp; } bool operator!(const self l) { return !(_node l._node); } bool operator(const self l) { return _node l._node; }在这里有人问了这个self是何方神圣?这是我们的迭代器本身,如果我们直接写的话我们的函数的返回值就太长了typedef listiteratorT, ref, ptr self;以上就是我们的准备工作了下面就是进入我们真正的实现链表的环节了链表类typedef listnode T node; typedef listiteratorT, T, T* iterator; typedef listiteratorT, const T, const T* const_iterator;实现的是双向循环的链表先来展示一下链表含的成员变量private: node* head; size_t _size;就是个这个第一个相当于我们的哨兵位节点,然后这个size是记录我们总共有多少个节点构造函数因为我们在之前我就已经封装好了我们的节点类,所以我们的构造函数的任务就是把节点连接并且构造出一个哨兵位节点void empty_init() { head new node; head-_next head; head-_pre head; _size 0; } list() { empty_init(); } list(int n, const T value T()) { empty_init(); while (n--) { push_back(value); } } template class Iterator list(Iterator first, Iterator last) { empty_init(); while (first ! last) { push_back(*first); first; } } list(const listT l) { empty_init(); for (auto e : l) { push_back(e); } } listT operator(const listT l) { empty_init(); swap(l); return *this; }需要解释的是如果我们的链表是一个空链表的话(只有一个哨兵位)设计的是head的next和preve都是指向自己的在这里我们都是通过复用push_back实现的所以我们的构造函数实现的是轻而易举的我们来仔细的剖析一下这个赋值构造在这里我们函数的参数并不是一个引用的传参数,所以我们的实参会进行拷贝构造,所以进入函数体内的是一个全新的链表,这时候我们把它夺舍了就行了,直接swap一下在链表的swap只需要交换一下头节点就好了,注意需要交换一下数据的个数void swap(listT l) { std::swap(head,l.head); std::swap(_size,l._size); }析构函数~list() { node* cur head-_next; while (cur ! head) { node* next cur-_next; delete cur; cur next; } delete head; }我们析构函数的存在的意义就是防止我们的内存泄漏的,所以我们需要把我们所有开辟的空间进行释放,因为我们的每一个的节点都是我们自己new出来的所以我们需要遍历链表一个个delete简单的容量的接口size_t size()const { return _size; } bool empty()const { return _size 0; } T front() { return head-_next-_val; } const T front()const { return head-_next-_val; } T back() { return head-_pre-_val; } const T back()const { return head-_pre-_val; }迭代器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); }下面就是有难度的插入的接口了数据的插入和删除void push_back(const T val) { insert(end(), val); } void pop_back() { erase(--end()); } void push_front(const T val) { insert(begin(), val); } void pop_front() { erase(begin()); }在这几个接口的实现我们可以看到是高度的复用了erase和insert的函数所以我们的重头戏就是来实现着两个函数insert// 在pos位置前插入值为val的节点 iterator insert(iterator pos, const T val) { node* cur pos._node; node* pcur cur-_pre; node* newnode new node(val); pcur-_next newnode; cur-_pre newnode; newnode-_nextcur; newnode-_pre pcur; _size; return iterator(newnode); }注意我们的函数的参数是一个迭代器加上一个数据我们insert实现的在pos的之前来插入数据的我们的目的就是在pos的前面插入一个节点这样就搞定了上面的代码就是这样的思路注意需要返回插入节点的迭代器别忘了sizeerase// 删除pos位置的节点返回该节点的下一个位置 iterator erase(iterator pos) { node* cur pos._node; node* pcur cur-_pre; node* ncur cur-_next; pcur-_next ncur; ncur-_pre pcur; delete cur; _size--; return iterator(ncur); }修改完指针后deletepos节点然后调整一下数据的个数并且返回下一个节点clearvoid clear() { auto cur begin(); while (cur ! end()) { curerase(cur); } }把链表的数据全删除并且释放节点总结本次内容围绕 C 手写链表展开从节点类、迭代器类的基础实现到链表类的封装含构造 / 析构、容量接口再到核心操作 insert、erase、clear 的实现逻辑完整复刻了 STL 链表的核心框架。在之后我们会来了解怎么来封装堆,栈,队列.谢谢大家的观看!!!