dllist.h
1/*
2 * dllist.h
3 *
4 * Copyright 2007 Joey Durham <joey@engineering.ucsb.edu>
5 *
6 * This program is free software; you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License as published by
8 * the Free Software Foundation; either version 2 of the License, or
9 * (at your option) any later version.
10 *
11 * This program is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU General Public License for more details.
15 *
16 * You should have received a copy of the GNU General Public License
17 * along with this program; if not, write to the Free Software
18 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
19 */
20
21
22#ifndef DLLIST_H
23#define DLLIST_H
24
25#include <iostream>
26#include <assert.h>
27
28template <class tVARTYPE> class DLList;
29
30
31
32template <class tVARTYPE> class DLLNode
33{
34 friend class DLList<tVARTYPE>;
35
36 protected :
37 DLLNode<tVARTYPE>* m_pNext;
38 DLLNode<tVARTYPE>* m_pPrev;
39
40 public :
41 tVARTYPE m_data;
42
43 DLLNode(const tVARTYPE& val)
44 {
45 m_data = val;
46
47 m_pNext = NULL;
48 m_pPrev = NULL;
49 }
50 virtual ~DLLNode() {}
51
52};
53template <class tVARTYPE> class DLList
54{
55
56public:
57
58 DLList();
59 virtual ~DLList();
60
61 void clear();
62
63 void insertAtBeginning(const tVARTYPE& val);
64 void insertAtEnd(const tVARTYPE& val);
65 void insertBefore(const tVARTYPE& val, DLLNode<tVARTYPE>* pThisNode);
66 void insertAfter(const tVARTYPE& val, DLLNode<tVARTYPE>* pThisNode);
67 DLLNode<tVARTYPE>* deleteNode(DLLNode<tVARTYPE>* pNode);
68 void moveToEnd(DLLNode<tVARTYPE>* pThisNode);
69
70 DLLNode<tVARTYPE>* next(DLLNode<tVARTYPE>* pNode) const;
71 DLLNode<tVARTYPE>* prev(DLLNode<tVARTYPE>* pNode) const;
72
73 DLLNode<tVARTYPE>* nodeNum(int iNum) const;
74
75 int getLength() const
76 {
77 return m_iLength;
78 }
79
80 DLLNode<tVARTYPE>* head() const
81 {
82 return m_pHead;
83 }
84
85 DLLNode<tVARTYPE>* tail() const
86 {
87 return m_pTail;
88 }
89
90protected:
91 int m_iLength;
92
93 DLLNode<tVARTYPE>* m_pHead;
94 DLLNode<tVARTYPE>* m_pTail;
95};
96
97
98
99//constructor
100//resets local vars
101template <class tVARTYPE>
103{
104 m_iLength = 0;
105
106 m_pHead = NULL;
107 m_pTail = NULL;
108}
109
110
111//Destructor
112//resets local vars
113template <class tVARTYPE>
115{
116 clear();
117}
118
119
120template <class tVARTYPE>
121inline void DLList<tVARTYPE>::clear()
122{
123 DLLNode<tVARTYPE>* pCurrNode;
124 DLLNode<tVARTYPE>* pNextNode;
125
126 pCurrNode = m_pHead;
127 while (pCurrNode != NULL)
128 {
129 pNextNode = pCurrNode->m_pNext;
130 delete pCurrNode;
131 pCurrNode = pNextNode;
132 }
133
134 m_iLength = 0;
135
136 m_pHead = NULL;
137 m_pTail = NULL;
138}
139
140
141//inserts at the tail of the list
142template <class tVARTYPE>
143inline void DLList<tVARTYPE>::insertAtBeginning(const tVARTYPE& val)
144{
145 DLLNode<tVARTYPE>* pNode;
146
147 assert((m_pHead == NULL) || (m_iLength > 0));
148
149 pNode = new DLLNode<tVARTYPE>(val);
150
151 if (m_pHead != NULL)
152 {
153 m_pHead->m_pPrev = pNode;
154 pNode->m_pNext = m_pHead;
155 m_pHead = pNode;
156 }
157 else
158 {
159 m_pHead = pNode;
160 m_pTail = pNode;
161 }
162
163 m_iLength++;
164}
165
166
167//inserts at the tail of the list
168template <class tVARTYPE>
169inline void DLList<tVARTYPE>::insertAtEnd(const tVARTYPE& val)
170{
171 DLLNode<tVARTYPE>* pNode;
172
173 assert((m_pHead == NULL) || (m_iLength > 0));
174
175 pNode = new DLLNode<tVARTYPE>(val);
176
177 if (m_pTail != NULL)
178 {
179 m_pTail->m_pNext = pNode;
180 pNode->m_pPrev = m_pTail;
181 m_pTail = pNode;
182 }
183 else
184 {
185 m_pHead = pNode;
186 m_pTail = pNode;
187 }
188
189 m_iLength++;
190}
191
192
193//inserts before the specified node
194template <class tVARTYPE>
195inline void DLList<tVARTYPE>::insertBefore(const tVARTYPE& val, DLLNode<tVARTYPE>* pThisNode)
196{
197 DLLNode<tVARTYPE>* pNode;
198
199 assert((m_pHead == NULL) || (m_iLength > 0));
200
201 if ((pThisNode == NULL) || (pThisNode->m_pPrev == NULL))
202 {
203 insertAtBeginning(val);
204 return;
205 }
206
207 pNode = new DLLNode<tVARTYPE>(val);
208
209 pThisNode->m_pPrev->m_pNext = pNode;
210 pNode->m_pPrev = pThisNode->m_pPrev;
211 pThisNode->m_pPrev = pNode;
212 pNode->m_pNext = pThisNode;
213
214 m_iLength++;
215}
216
217
218//inserts after the specified node
219template <class tVARTYPE>
220inline void DLList<tVARTYPE>::insertAfter(const tVARTYPE& val, DLLNode<tVARTYPE>* pThisNode)
221{
222 DLLNode<tVARTYPE>* pNode;
223
224 assert((m_pHead == NULL) || (m_iLength > 0));
225
226 if ((pThisNode == NULL) || (pThisNode->m_pNext == NULL))
227 {
228 insertAtEnd(val);
229 return;
230 }
231
232 pNode = new DLLNode<tVARTYPE>(val);
233
234 pThisNode->m_pNext->m_pPrev = pNode;
235 pNode->m_pNext = pThisNode->m_pNext;
236 pThisNode->m_pNext = pNode;
237 pNode->m_pPrev = pThisNode;
238
239 m_iLength++;
240}
241
242
243template <class tVARTYPE>
245{
246 DLLNode<tVARTYPE>* pPrevNode;
247 DLLNode<tVARTYPE>* pNextNode;
248
249 assert(pNode != NULL);
250
251 pPrevNode = pNode->m_pPrev;
252 pNextNode = pNode->m_pNext;
253
254 if ((pPrevNode != NULL) && (pNextNode != NULL))
255 {
256 pPrevNode->m_pNext = pNextNode;
257 pNextNode->m_pPrev = pPrevNode;
258 }
259 else if (pPrevNode != NULL)
260 {
261 pPrevNode->m_pNext = NULL;
262 m_pTail = pPrevNode;
263 }
264 else if (pNextNode != NULL)
265 {
266 pNextNode->m_pPrev = NULL;
267 m_pHead = pNextNode;
268 }
269 else
270 {
271 m_pHead = NULL;
272 m_pTail = NULL;
273 }
274
275 delete pNode;
276
277 m_iLength--;
278
279 return pNextNode;
280}
281
282
283template <class tVARTYPE>
285{
286 DLLNode<tVARTYPE>* pPrevNode;
287 DLLNode<tVARTYPE>* pNextNode;
288
289 assert(pNode != NULL);
290
291 if (getLength() == 1)
292 {
293 return;
294 }
295
296 if (pNode == m_pTail)
297 {
298 return;
299 }
300
301 pPrevNode = pNode->m_pPrev;
302 pNextNode = pNode->m_pNext;
303
304 if ((pPrevNode != NULL) && (pNextNode != NULL))
305 {
306 pPrevNode->m_pNext = pNextNode;
307 pNextNode->m_pPrev = pPrevNode;
308 }
309 else if (pPrevNode != NULL)
310 {
311 pPrevNode->m_pNext = NULL;
312 m_pTail = pPrevNode;
313 }
314 else if (pNextNode != NULL)
315 {
316 pNextNode->m_pPrev = NULL;
317 m_pHead = pNextNode;
318 }
319 else
320 {
321 m_pHead = NULL;
322 m_pTail = NULL;
323 }
324
325 pNode->m_pNext = NULL;
326 m_pTail->m_pNext = pNode;
327 pNode->m_pPrev = m_pTail;
328 m_pTail = pNode;
329}
330
331
332template <class tVARTYPE>
334{
335 assert(pNode != NULL);
336
337 return pNode->m_pNext;
338}
339
340
341template <class tVARTYPE>
343{
344 assert(pNode != NULL);
345
346 return pNode->m_pPrev;
347}
348
349
350template <class tVARTYPE>
351inline DLLNode<tVARTYPE>* DLList<tVARTYPE>::nodeNum(int iNum) const
352{
353 DLLNode<tVARTYPE>* pNode;
354 int iCount;
355
356 iCount = 0;
357 pNode = m_pHead;
358
359 while (pNode != NULL)
360 {
361 if (iCount == iNum)
362 {
363 return pNode;
364 }
365
366 iCount++;
367 pNode = pNode->m_pNext;
368 }
369
370 return NULL;
371}
372
373
374#endif //LINKEDLIST_H
Definition dllist.h:33
Definition dllist.h:54