absence_thelab

view src/common/linkedlist.h @ 0:1cffe3409164

find changesets by author, revision, files, or words in the commit message
initial commit
author John Tsiombikas <nuclear@member.fsf.org>
date Thu, 23 Oct 2014 01:46:07 +0300
parents
children
line source
1 #ifndef _LINKEDLIST_H_
2 #define _LINKEDLIST_H_
3
4 template <class T>
5 struct ListNode {
6 T data;
7 ListNode<T> *next, *prev;
8 };
9
10
11 template <class T>
12 class LinkedList {
13 private:
14 ListNode<T> *head, *tail;
15 int size;
16
17 public:
18
19 LinkedList();
20 ~LinkedList();
21
22 inline ListNode<T> *Begin();
23 inline ListNode<T> *End();
24
25 void PushBack(ListNode<T> *node);
26 void PushBack(T data);
27
28 void Insert(ListNode<T> *pos, ListNode<T> *node);
29 void Insert(ListNode<T> *pos, T data);
30
31 void Remove(ListNode<T> *node);
32 ListNode<T> *Erase(ListNode<T> *node);
33
34 ListNode<T> *Find(T key);
35
36 int CountNodes();
37 inline int Size() const;
38
39 void operator =(LinkedList &rhs);
40 };
41
42
43 /////////// implementation //////////
44 template <class T>
45 LinkedList<T>::LinkedList() {
46 head = tail = 0;
47 size = 0;
48 }
49
50
51 template <class T>
52 LinkedList<T>::~LinkedList() {
53
54 while(head) {
55 Erase(head);
56 }
57 }
58
59 template <class T>
60 ListNode<T> *LinkedList<T>::Begin() {
61 return head;
62 }
63
64 template <class T>
65 ListNode<T> *LinkedList<T>::End() {
66 return tail;
67 }
68
69 template <class T>
70 void LinkedList<T>::PushBack(ListNode<T> *node) {
71
72 if(!head) { // empty list
73 head = tail = node;
74 node->next = node->prev = 0;
75 } else {
76 tail->next = node;
77 node->prev = tail;
78 tail = node;
79 node->next = 0;
80 }
81
82 size++;
83 }
84
85 template <class T>
86 void LinkedList<T>::PushBack(T data) {
87
88 ListNode<T> *node = new ListNode<T>;
89 node->data = data;
90
91 if(!head) { // empty list
92 head = tail = node;
93 node->next = node->prev = 0;
94 } else {
95 tail->next = node;
96 node->prev = tail;
97 tail = node;
98 node->next = 0;
99 }
100
101 size++;
102 }
103
104 template <class T>
105 void LinkedList<T>::Insert(ListNode<T> *pos, ListNode<T> *node) {
106
107 if(!head) {
108 head = tail = node;
109 node->next = node->prev = 0;
110 } else {
111 node->prev = pos->prev;
112 pos->prev = node;
113 node->next = pos;
114 if(head == pos) head = node; else node->prev->next = node;
115 }
116
117 size++;
118 }
119
120 template <class T>
121 void LinkedList<T>::Insert(ListNode<T> *pos, T data) {
122
123 ListNode<T> *node = new ListNode<T>;
124 node->data = data;
125
126 if(!head) {
127 head = tail = node;
128 node->next = node->prev = 0;
129 } else {
130 node->prev = pos->prev;
131 pos->prev = node;
132 node->next = pos;
133 if(head == pos) head = node; else node->prev->next = node;
134 }
135
136 size++;
137 }
138
139 template <class T>
140 void LinkedList<T>::Remove(ListNode<T> *node) {
141
142 if(!node) return; // e.g. Remove(head) on an empty list
143
144 if(node->prev) {
145 node->prev->next = node->next;
146 } else {
147 head = node->next;
148 }
149
150 if(node->next) {
151 node->next->prev = node->prev;
152 } else {
153 tail = node->prev;
154 }
155
156 size--;
157 }
158
159 template <class T>
160 ListNode<T> *LinkedList<T>::Erase(ListNode<T> *node) {
161
162 if(!node) return 0; // e.g. Erase(head) on an empty list
163
164 if(node->prev) {
165 node->prev->next = node->next;
166 } else {
167 head = node->next;
168 }
169
170 if(node->next) {
171 node->next->prev = node->prev;
172 } else {
173 tail = node->prev;
174 }
175
176 ListNode<T> *destr = node;
177 node = node->next;
178
179 delete destr;
180
181 size--;
182
183 return node;
184 }
185
186 template <class T>
187 ListNode<T> *LinkedList<T>::Find(T key) {
188
189 ListNode<T> *iter = head;
190 while(iter) {
191 if(iter->data == key) return iter;
192 iter = iter->next;
193 }
194
195 return 0; // null pointer if not found
196 }
197
198 template <class T>
199 int LinkedList<T>::CountNodes() {
200
201 size = 0;
202
203 ListNode<T> *iter = head;
204 while(iter) {
205 size++;
206 iter = iter->next;
207 }
208
209 return size;
210 }
211
212 template <class T>
213 int LinkedList<T>::Size() const {
214 return size;
215 }
216
217
218 template <class T>
219 void LinkedList<T>::operator =(LinkedList<T> &rhs) {
220
221 ListNode<T> *src = rhs.Begin();
222 while(src) {
223 PushBack(src->data);
224 src = src->next;
225 }
226 }
227
228
229 #endif // _LINKEDLIST_H_