当前位置:首页 > 服务端 > 链表(list)——C++实现

链表(list)——C++实现

2022年11月08日 21:28:16服务端12

C++内list采用双向链表,重新实现自己的list

  1 /************************************************************************/
  2 /*对list的实现,采用的是双向链表,C++标准库中使用的也是双向链表 */
  3 /************************************************************************/
  4 
  5 #ifndef LIST_H
  6 #define  LIST_H
  7 
  8 namespace stl
  9 {
 10     template <typename Object> 
 11     class List
 12     {
 13     //public members
 14     public:
 15         //构造函数
 16         List() : theSize(0)
 17         {
 18             init();
 19         }
 20 
 21         //拷贝构造函数
 22         List(const List & L)
 23         {
 24             //需要深层次的拷贝
 25             init();
 26             this->operator=(L);
 27         }
 28 
 29         //重载赋值运算符
 30         const List & operator = (const List & L)
 31         {
 32             if (this == &L)
 33             {
 34                 return *this;
 35             }
 36             //形参List是const类型的,因此只能调用const版本的函数
 37             //将元素一个个拷贝,不拷贝节点,节点在init函数中
 38             for (const_iterator from = L.begin(); from != L.cend(); ++from)
 39             {
 40                 push_back(*L);
 41             }
 42             return *this;
 43         }
 44 
 45         bool operator == (const List & L)
 46         {
 47             return head == L.head && tail == L.tail && theSize == L.theSize;
 48         }
 49 
 50         //析构函数
 51         ~List()
 52         {
 53             //删除元素
 54             Node* temp = head->next;
 55             Node* tempNext = temp->next;
 56             while (temp != tail)
 57             {
 58                 delete temp;
 59                 temp = tempNext;
 60             }
 61             //删除头结点和尾节点
 62             delete head;
 63             delete tail;
 64         }
 65 
 66         void init()
 67         {
 68             head = new Node;
 69             tail = new Node;
 70             head->next = tail;
 71             tail->prev = head;
 72         }
 73 
 74     public:
 75         /************************************************************************/
 76         /* 说   明:迭代器类的定义
 77         /* 时   间:2016.10.27
 78         /************************************************************************/
 79         class const_iterator
 80         {
 81         public:
 82             //构造函数,带默认值为NULL
 83             const_iterator(Node* n = NULL)
 84                 :current(n){ }
 85 
 86             //重载取引用操作符,解引用操作符是无参的
 87             const Object& operator * () const
 88             {
 89                 retrieve();
 90             }
 91 
 92             //重载++,返回的还是迭代器,current发生了改变,不能申明为const
 93             //返回增加后的引用
 94             const_iterator & operator ++ ()
 95             {
 96                 current = current->next;
 97                 return *this;
 98             }
 99 
100             //后置,为了与内部保持一致,返回之前的值
101             const_iterator & operator ++ (int)
102             {
103                 const_iterator ret = *this;
104                 ++*this;
105                 return ret;
106             }
107 
108             bool operator == (const const_iterator & iter) const
109             {
110                 return current == iter.current;
111             }
112 
113             bool operator != (const const_iterator & iter) const
114             {
115                 return ! (this->operator== (iter));
116             }
117         protected:
118             //定义一个Node*的变量来保存迭代器的位置,申明为protected是为了派生类能访问到
119             Node* current;
120 
121             //返回迭代器所指节点数据对象的引用,不改变const_iterator的任何数据,定义为const
122             //该函数只在内部使用,申明为protected为了派生类能使用
123             const Object & retrieve() const
124             {
125                 return current->data;
126             }
127             const_iterator( Node* p ) : current(p) { }
128 
129             //为了能访问List<Object>的成员变量,将其申明为const_iterator的友元
130             friend class List<Object>;
131         };
132 
133 
134         //从const_iterator继承过来
135         class iterator : public const_iterator
136         {
137         public:
138             iterator();
139             ~iterator();
140             //重载取引用操作符,解引用操作符是无参的
141             Object& operator * () const
142             {
143                 retrieve();
144             }
145 
146             iterator & operator ++ ()
147             {
148                 current = current->next;
149                 return *this;
150             }
151 
152             //后置,为了与内部保持一致,返回之前的值
153             iterator & operator ++ (int)
154             {
155                 const_iterator ret = *this;
156                 ++*this;
157                 return ret;
158             }
159         protected:
160             iterator(Node* p) : const_iterator (p) { }
161         };
162 
163         /************************************************************************/
164         /* 函数名:begin end成员
165         /* 时   间:2016.10.27
166         /************************************************************************/
167         iterator begin()
168         {
169             return iterator(head->next);
170         }
171 
172         iterator end()
173         {
174             return iterator(tail);
175         }
176 
177         const_iterator cbegin() const
178         {
179             return const_iterator(head->next);
180         }
181 
182         const_iterator cend() const
183         {
184             return const_iterator(tail);
185         }
186 
187 
188         /************************************************************************/
189         /* 说   明:赋值和swap
190         /* 时   间:2016.10.27
191         /************************************************************************/
192 
193         /************************************************************************/
194         /* 说   明:容器大小操作
195         /* 时   间:2016.10.27
196         /************************************************************************/
197         //size函数
198         int Size() const
199         {
200             return theSize;
201         }
202 
203         bool Empty() const
204         {
205             return Size() == 0;
206         }
207 
208 
209 
210         /************************************************************************/
211         /* 说   明:向容器添加元素
212         /* 时   间:2016.10.27
213         /************************************************************************/
214         void push_back(const Object& obj)
215         {
216             insert(end(), obj);
217         }
218 
219 
220         void push_front(Object obj)
221         {
222             insert(begin(), obj);
223         }
224 
225         iterator insert(iterator it, const Object &  obj)
226         {
227             Node* p = it.current;
228             Node* node = new Node(obj, p->prev, p);
229             p->prev->next = node;
230             p->prev = node;
231             //大小加一
232             ++theSize;
233             return iterator(node);
234             //牛掰写法:return iterator(p->prev = p->prev->next = new Node(obj, p->prev, p));
235         }
236 
237         /************************************************************************/
238         /* 说   明:访问元素
239         /* 时   间:2016.10.27
240         /************************************************************************/
241         Object & front() const
242         {
243             return head->next->data;
244         }
245 
246         const Object & front() const
247         {
248             return head->next->data;
249         }
250 
251         Object & back() const
252         {
253             return tail->prev->data;
254         }
255 
256         const Object & back() const
257         {
258             return tail->prev->data;
259         }
260 
261         /************************************************************************/
262         /* 说   明:删除元素
263         /* 时   间:2016.10.27
264         /************************************************************************/
265         void pop_front()
266         {
267             Node* temp = head->next;
268             temp->next->prev = head;
269             head->next = temp->next;
270             delete temp;
271             theSize--;
272         }
273 
274         void pop_back()
275         {
276             erase(--end());
277         }
278 
279         iterator erase(iterator itr)
280         {
281             Node* temp = itr.current;
282             iterator ret = ++itr;
283             temp->prev->next = temp->next;
284             temp->next->prev = temp->prev;
285             delete temp;
286             theSize--;
287             return ret;
288         }
289 
290         iterator erase(iterator itr1, iterator itr2)
291         {
292             iterator to  = ++itr2;
293             for (iterator i = itr1; i != to; )
294             {
295                 i = erase( i );
296             }
297             return i;
298         }
299 
300     private:
301         //定义节点
302         struct  Node
303         {
304             Object data;
305             Node* prev;
306             Node* next;
307             //结构体的构造函数
308             Node(Object obj = Object(), Node* p = NULL, Node* n = NULL)
309                 :data(obj), prev(p), next(n){ }
310         };
311         Node* head;   //头结点
312         Node* tail;      //尾节点
313         int theSize;
314     };
315 }
316 #endif

 

作者:oscarwin
来源链接:https://www.cnblogs.com/liuteng/p/6006533.html

版权声明:
1、JavaClub(https://www.javaclub.cn)以学习交流为目的,由作者投稿、网友推荐和小编整理收藏优秀的IT技术及相关内容,包括但不限于文字、图片、音频、视频、软件、程序等,其均来自互联网,本站不享有版权,版权归原作者所有。

2、本站提供的内容仅用于个人学习、研究或欣赏,以及其他非商业性或非盈利性用途,但同时应遵守著作权法及其他相关法律的规定,不得侵犯相关权利人及本网站的合法权利。
3、本网站内容原作者如不愿意在本网站刊登内容,请及时通知本站(javaclubcn@163.com),我们将第一时间核实后及时予以删除。


本文链接:https://www.javaclub.cn/server/68597.html

标签: List
分享给朋友:

“链表(list)——C++实现” 的相关文章

数组转LIst的几种方法

第一种方式 /** * 针对数组类型转换 * 分别是int[]、long[]、double[],其他数据类型比如short[]、byte[]、char[],在JDK1.8中暂不支持 */ List<...

flutter开发之必须掌握的dart知识点:list,set,map

要说,List在我的开发使用中,确实是最为频繁的了,那么如何使用list,也就成了一个问题,list提供的方法又有哪些 这些都是需要掌握理解的。 首先第一个, 对于固定长度的list,如何删除添加元素呢 void main() {...

HTML5中datalist标签的使用

HTML5中datalist标签的使用

datalist是html5中出现的新标签,它需要配合input输入框来使用,它的作用就是定义了input可能要输入的值(可以被快捷选择), 定义一个datalist的标签需要给他一个id,input就是根据id来与其绑定的,datalist中的opti...

java 集合hashmap hashset arraylist 详解以及常见面试题

java 集合hashmap hashset arraylist 详解以及常见面试题

   今天复习了一下自认为java 中很重要的一部分集合,这篇文章主要从底层源码进行分析这几种集合的区别与联系,他们的用法不多讲,用法不难;大多数东西我也是从各位大神的博客上或者书上扒下来的,小菜鸟在复习,写下来主要是一:是为了想留下点东西 二:我发现在写的过程中我...

Java 集合Collection与List的详解

Java 集合Collection与List的详解

1.什么是集合 存储对象的容器,面向对象语言对事物的体现都是以对象的形式,所以为了方便对多个对象的操作,存储对象,集合是存储对象最常用的一种方式。 集合的出现就是为了持有对象。集合中可以存储任意类型的对象,而且长度可变。在程序中有可能无法预先知道需要多少个对象,那么用数组来...

Java集合 ArrayList原理及使用

Java集合 ArrayList原理及使用

本文主要讲解了ArrayList原理,从底层数组着手,讲解了ArrayList定义时到底发生了什么,再添加元素时,扩容规则如何,删除元素时,数组的元素的移动方式以及一些常用方法的用途 ArrayList是集合的一种实现,实现了接口List,List接口继承了Colle...

Java集合List实现原理

Java集合List实现原理

一、集合类结构 Java中的集合包含多种数据结构,如链表、队列、哈希表等。从类的继承结构来说,可以分为两大类,一类是继承自Collection接口,这类集合包含List、Set和Queue等集合类。另一类是继承自Map接口,这主要包含了哈希表相关的集合类。 1.继承Coll...

java list集合合并

import java.util.ArrayList; import java.util.List; public class test { public static void main(String[] args) throws...

mysql show processlist命令 详解

SHOW PROCESSLIST显示哪些线程正在运行。您也可以使用mysqladmin processlist语句得到此信息。如果您有SUPER权限,您可以看到所有线程。否则,您只能看到您自己的线程(也就是,与您正在使用的MySQL账户相关的线程)。请参见13.5.5.3节,“KILL...

Java中Vector和ArrayList的区别

      首先看这两类都实现List接口,而List接口一共有三个实现类,分别是ArrayList、Vector和LinkedList。List用于存放多个元素,能够维护元素的次序,并且允许元素的重复。3个具体实现类的相关区别如下:...

发表评论

访客

◎欢迎参与讨论,请在这里发表您的看法和观点。