20120918-LIST类定义《数据结构与算法分析》

简介:

LIST类结构

复制代码
  1 template <typename Object>
  2 class List
  3 {
  4     private:
  5         struct Node//所有都是公有的
  6         {
  7             Object data;
  8             Node *prev;
  9             Node *next;
 10 
 11             Node(const Object & d = Object(),Node *p = NUll,Node *n = Null):
 12             data(d) , prev(p) , next(n)
 13             {
 14             }
 15         };
 16     public:
 17         class const_iterator
 18         {
 19                 public:
 20                     const_iterator() : current(NULL){}
 21                     const Object & operator* () const
 22                     {
 23                         return retrieve();
 24                     }
 25                     const_iterator & operator++ ( ) const
 26                     {
 27                         current = current->next;
 28                         return *this;
 29                     }
 30                     const_iterator & operator++( int )
 31                     {
 32                         const_iterator old = *this;
 33                         ++(*this);
 34                         return old;
 35                     }
 36                     bool operator == (const const_iterator * rhs) const
 37                     {
 38                         return current == rhs.current;
 39                     }
 40                     bool operator != (const const_iterator & rhs) const
 41                     {
 42                         return !(*this == rhs);
 43                     }
 44 
 45             protected:
 46                 Node *current;
 47 
 48                 Object & retrieve() cosnt
 49                 {
 50                     return current->data;
 51                 }
 52                 const_iterator(Node *p) : current(p)
 53                 {
 54                 }
 55                 friend class List<Object>;
 56         };
 57         class iterator : public const_iterator
 58         {
 59             public:
 60                 iterator()
 61                 {
 62                 }
 63                 Object & operator* ()
 64                 {
 65                     return retrieve();
 66                 }
 67                 const Object & operator* () const
 68                 {
 69                     return const_iterator::operator*();
 70                 }
 71                 iterator & operator++()
 72                 {
 73                     iterator old = *this;
 74                     ++(*this);
 75                     return old;
 76                 }
 77 
 78             protected:
 79                 iterator(Node *p) : const_iterator(p)
 80                 {
 81                 }
 82 
 83                 friend class List<object>;
 84         };
 85     public:
 86         List()
 87         {
 88             init();
 89         }
 90         List(const List & rhs)
 91         {
 92             init();
 93             *this = rhs;
 94         }
 95         ~List()
 96         {
 97             clear();
 98             delete head;
 99             delete tail;
100         }
101         const List & operator =(const List & rhs)
102         {
103             if(this == &rhs)
104                 return *this;
105             clear();
106             for(const_iterator itr = rhs.begin();itr!=rhs.end();++itr)
107                 push_back(*itr);
108             return *this;
109         }
110         void init()
111         {
112             theSize = 0;
113             head = new Node;
114             tail = new Node;
115             head->next = tail;
116             tail->prev = head;
117         }
118 
119         iterator begin()
120         {
121             return iterator(head->next);
122         }
123         const_iterator begin() const
124         {
125             return const_iterator(head->next);
126         }
127         iterator end()
128         {
129             return iterator(tail);
130         }
131         const_iterator end() const
132         {
133             return const_iterator(tail);
134         }
135 
136         int size() const
137         {
138             return theSize;
139         }
140         bool empty() const
141         {
142             return size() == 0;
143         }
144         void clear()
145         {
146             while(!empty())
147                 pop_front();
148         }
149         Object & front()
150         {
151             return *begin();
152         }
153         const Object & front() const
154         {
155             return *begin();
156         }
157         Object & back()
158         {
159             return *--end();
160         }
161         const Object & back() const
162         {
163             return *--end();
164         }
165         void push_front(const Object & x)
166         {
167             insert(begin(),x);
168         }
169         void push_back(const Object & x)
170         {
171             insert(end(),x);
172         }
173         void pop_front()
174         {
175             erase(begin());
176         }
177         viod pop_back()
178         {
179             erase(end());
180         }
181 
182         iterator insert(iterator itr,const Object & x)
183         {
184         }
185         iteratro erase(iterator itr )
186         {
187         }
188         iterator erase(iterator start,iterator end)
189         {
190         }
191 
192 private:
193     int theSize;
194     Node *head;
195     Node *tail;
196 
197     void init()
198     {
199     }
200 }
复制代码
本文转自博客园xingoo的博客,原文链接:20120918-LIST类定义《数据结构与算法分析》,如需转载请自行联系原博主。
相关文章
|
3月前
|
消息中间件 NoSQL Redis
redis数据结构-List
redis数据结构-List
44 1
|
3月前
|
存储 安全 Java
【Java集合类面试二十五】、有哪些线程安全的List?
线程安全的List包括Vector、Collections.SynchronizedList和CopyOnWriteArrayList,其中CopyOnWriteArrayList通过复制底层数组实现写操作,提供了最优的线程安全性能。
|
3月前
|
Java
【Java集合类面试二十三】、List和Set有什么区别?
List和Set的主要区别在于List是一个有序且允许元素重复的集合,而Set是一个无序且元素不重复的集合。
|
3月前
|
Java
【Java集合类面试二十六】、介绍一下ArrayList的数据结构?
ArrayList是基于可动态扩展的数组实现的,支持快速随机访问,但在插入和删除操作时可能需要数组复制而性能较差。
|
3月前
|
存储 Java
Java学习笔记 List集合的定义、集合的遍历、迭代器的使用
Java学习笔记 List集合的定义、集合的遍历、迭代器的使用
|
3月前
|
编译器
【Bug记录】list模拟实现const迭代器类
【Bug记录】list模拟实现const迭代器类
|
6天前
|
存储 消息中间件 NoSQL
Redis数据结构:List类型全面解析
Redis数据结构——List类型全面解析:存储多个有序的字符串,列表中每个字符串成为元素 Eelement,最多可以存储 2^32-1 个元素。可对列表两端插入(push)和弹出(pop)、获取指定范围的元素列表等,常见命令。 底层数据结构:3.2版本之前,底层采用**压缩链表ZipList**和**双向链表LinkedList**;3.2版本之后,底层数据结构为**快速链表QuickList** 列表是一种比较灵活的数据结构,可以充当栈、队列、阻塞队列,在实际开发中有很多应用场景。
|
17天前
|
存储 算法 Java
Set接口及其主要实现类(如HashSet、TreeSet)如何通过特定数据结构和算法确保元素唯一性
Java Set因其“无重复”特性在集合框架中独树一帜。本文解析了Set接口及其主要实现类(如HashSet、TreeSet)如何通过特定数据结构和算法确保元素唯一性,并提供了最佳实践建议,包括选择合适的Set实现类和正确实现自定义对象的hashCode()与equals()方法。
30 4
|
26天前
|
设计模式 安全 容器
数据结构第一篇【探究List和ArrayList之间的奥秘 】
数据结构第一篇【探究List和ArrayList之间的奥秘 】
21 5
|
18天前
|
人工智能 算法 前端开发
无界批发零售定义及无界AI算法,打破传统壁垒,累积数据流量
“无界批发与零售”是一种结合了批发与零售的商业模式,通过后端逻辑、数据库设计和前端用户界面实现。该模式支持用户注册、登录、商品管理、订单处理、批发与零售功能,并根据用户行为计算信用等级,确保交易安全与高效。