00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022 #ifndef DLLIST_H
00023 #define DLLIST_H
00024
00025 #include <iostream>
00026 #include <assert.h>
00027
00028 template <class tVARTYPE> class DLList;
00029
00030
00031
00032 template <class tVARTYPE> class DLLNode
00033 {
00034 friend class DLList<tVARTYPE>;
00035
00036 protected :
00037 DLLNode<tVARTYPE>* m_pNext;
00038 DLLNode<tVARTYPE>* m_pPrev;
00039
00040 public :
00041 tVARTYPE m_data;
00042
00043 DLLNode(const tVARTYPE& val)
00044 {
00045 m_data = val;
00046
00047 m_pNext = NULL;
00048 m_pPrev = NULL;
00049 }
00050 virtual ~DLLNode() {}
00051
00052 };
00053 template <class tVARTYPE> class DLList
00054 {
00055
00056 public:
00057
00058 DLList();
00059 virtual ~DLList();
00060
00061 void clear();
00062
00063 void insertAtBeginning(const tVARTYPE& val);
00064 void insertAtEnd(const tVARTYPE& val);
00065 void insertBefore(const tVARTYPE& val, DLLNode<tVARTYPE>* pThisNode);
00066 void insertAfter(const tVARTYPE& val, DLLNode<tVARTYPE>* pThisNode);
00067 DLLNode<tVARTYPE>* deleteNode(DLLNode<tVARTYPE>* pNode);
00068 void moveToEnd(DLLNode<tVARTYPE>* pThisNode);
00069
00070 DLLNode<tVARTYPE>* next(DLLNode<tVARTYPE>* pNode) const;
00071 DLLNode<tVARTYPE>* prev(DLLNode<tVARTYPE>* pNode) const;
00072
00073 DLLNode<tVARTYPE>* nodeNum(int iNum) const;
00074
00075 int getLength() const
00076 {
00077 return m_iLength;
00078 }
00079
00080 DLLNode<tVARTYPE>* head() const
00081 {
00082 return m_pHead;
00083 }
00084
00085 DLLNode<tVARTYPE>* tail() const
00086 {
00087 return m_pTail;
00088 }
00089
00090 protected:
00091 int m_iLength;
00092
00093 DLLNode<tVARTYPE>* m_pHead;
00094 DLLNode<tVARTYPE>* m_pTail;
00095 };
00096
00097
00098
00099
00100
00101 template <class tVARTYPE>
00102 inline DLList<tVARTYPE>::DLList()
00103 {
00104 m_iLength = 0;
00105
00106 m_pHead = NULL;
00107 m_pTail = NULL;
00108 }
00109
00110
00111
00112
00113 template <class tVARTYPE>
00114 inline DLList<tVARTYPE>::~DLList()
00115 {
00116 clear();
00117 }
00118
00119
00120 template <class tVARTYPE>
00121 inline void DLList<tVARTYPE>::clear()
00122 {
00123 DLLNode<tVARTYPE>* pCurrNode;
00124 DLLNode<tVARTYPE>* pNextNode;
00125
00126 pCurrNode = m_pHead;
00127 while (pCurrNode != NULL)
00128 {
00129 pNextNode = pCurrNode->m_pNext;
00130 delete pCurrNode;
00131 pCurrNode = pNextNode;
00132 }
00133
00134 m_iLength = 0;
00135
00136 m_pHead = NULL;
00137 m_pTail = NULL;
00138 }
00139
00140
00141
00142 template <class tVARTYPE>
00143 inline void DLList<tVARTYPE>::insertAtBeginning(const tVARTYPE& val)
00144 {
00145 DLLNode<tVARTYPE>* pNode;
00146
00147 assert((m_pHead == NULL) || (m_iLength > 0));
00148
00149 pNode = new DLLNode<tVARTYPE>(val);
00150
00151 if (m_pHead != NULL)
00152 {
00153 m_pHead->m_pPrev = pNode;
00154 pNode->m_pNext = m_pHead;
00155 m_pHead = pNode;
00156 }
00157 else
00158 {
00159 m_pHead = pNode;
00160 m_pTail = pNode;
00161 }
00162
00163 m_iLength++;
00164 }
00165
00166
00167
00168 template <class tVARTYPE>
00169 inline void DLList<tVARTYPE>::insertAtEnd(const tVARTYPE& val)
00170 {
00171 DLLNode<tVARTYPE>* pNode;
00172
00173 assert((m_pHead == NULL) || (m_iLength > 0));
00174
00175 pNode = new DLLNode<tVARTYPE>(val);
00176
00177 if (m_pTail != NULL)
00178 {
00179 m_pTail->m_pNext = pNode;
00180 pNode->m_pPrev = m_pTail;
00181 m_pTail = pNode;
00182 }
00183 else
00184 {
00185 m_pHead = pNode;
00186 m_pTail = pNode;
00187 }
00188
00189 m_iLength++;
00190 }
00191
00192
00193
00194 template <class tVARTYPE>
00195 inline void DLList<tVARTYPE>::insertBefore(const tVARTYPE& val, DLLNode<tVARTYPE>* pThisNode)
00196 {
00197 DLLNode<tVARTYPE>* pNode;
00198
00199 assert((m_pHead == NULL) || (m_iLength > 0));
00200
00201 if ((pThisNode == NULL) || (pThisNode->m_pPrev == NULL))
00202 {
00203 insertAtBeginning(val);
00204 return;
00205 }
00206
00207 pNode = new DLLNode<tVARTYPE>(val);
00208
00209 pThisNode->m_pPrev->m_pNext = pNode;
00210 pNode->m_pPrev = pThisNode->m_pPrev;
00211 pThisNode->m_pPrev = pNode;
00212 pNode->m_pNext = pThisNode;
00213
00214 m_iLength++;
00215 }
00216
00217
00218
00219 template <class tVARTYPE>
00220 inline void DLList<tVARTYPE>::insertAfter(const tVARTYPE& val, DLLNode<tVARTYPE>* pThisNode)
00221 {
00222 DLLNode<tVARTYPE>* pNode;
00223
00224 assert((m_pHead == NULL) || (m_iLength > 0));
00225
00226 if ((pThisNode == NULL) || (pThisNode->m_pNext == NULL))
00227 {
00228 insertAtEnd(val);
00229 return;
00230 }
00231
00232 pNode = new DLLNode<tVARTYPE>(val);
00233
00234 pThisNode->m_pNext->m_pPrev = pNode;
00235 pNode->m_pNext = pThisNode->m_pNext;
00236 pThisNode->m_pNext = pNode;
00237 pNode->m_pPrev = pThisNode;
00238
00239 m_iLength++;
00240 }
00241
00242
00243 template <class tVARTYPE>
00244 inline DLLNode<tVARTYPE>* DLList<tVARTYPE>::deleteNode(DLLNode<tVARTYPE>* pNode)
00245 {
00246 DLLNode<tVARTYPE>* pPrevNode;
00247 DLLNode<tVARTYPE>* pNextNode;
00248
00249 assert(pNode != NULL);
00250
00251 pPrevNode = pNode->m_pPrev;
00252 pNextNode = pNode->m_pNext;
00253
00254 if ((pPrevNode != NULL) && (pNextNode != NULL))
00255 {
00256 pPrevNode->m_pNext = pNextNode;
00257 pNextNode->m_pPrev = pPrevNode;
00258 }
00259 else if (pPrevNode != NULL)
00260 {
00261 pPrevNode->m_pNext = NULL;
00262 m_pTail = pPrevNode;
00263 }
00264 else if (pNextNode != NULL)
00265 {
00266 pNextNode->m_pPrev = NULL;
00267 m_pHead = pNextNode;
00268 }
00269 else
00270 {
00271 m_pHead = NULL;
00272 m_pTail = NULL;
00273 }
00274
00275 delete pNode;
00276
00277 m_iLength--;
00278
00279 return pNextNode;
00280 }
00281
00282
00283 template <class tVARTYPE>
00284 inline void DLList<tVARTYPE>::moveToEnd(DLLNode<tVARTYPE>* pNode)
00285 {
00286 DLLNode<tVARTYPE>* pPrevNode;
00287 DLLNode<tVARTYPE>* pNextNode;
00288
00289 assert(pNode != NULL);
00290
00291 if (getLength() == 1)
00292 {
00293 return;
00294 }
00295
00296 if (pNode == m_pTail)
00297 {
00298 return;
00299 }
00300
00301 pPrevNode = pNode->m_pPrev;
00302 pNextNode = pNode->m_pNext;
00303
00304 if ((pPrevNode != NULL) && (pNextNode != NULL))
00305 {
00306 pPrevNode->m_pNext = pNextNode;
00307 pNextNode->m_pPrev = pPrevNode;
00308 }
00309 else if (pPrevNode != NULL)
00310 {
00311 pPrevNode->m_pNext = NULL;
00312 m_pTail = pPrevNode;
00313 }
00314 else if (pNextNode != NULL)
00315 {
00316 pNextNode->m_pPrev = NULL;
00317 m_pHead = pNextNode;
00318 }
00319 else
00320 {
00321 m_pHead = NULL;
00322 m_pTail = NULL;
00323 }
00324
00325 pNode->m_pNext = NULL;
00326 m_pTail->m_pNext = pNode;
00327 pNode->m_pPrev = m_pTail;
00328 m_pTail = pNode;
00329 }
00330
00331
00332 template <class tVARTYPE>
00333 inline DLLNode<tVARTYPE>* DLList<tVARTYPE>::next(DLLNode<tVARTYPE>* pNode) const
00334 {
00335 assert(pNode != NULL);
00336
00337 return pNode->m_pNext;
00338 }
00339
00340
00341 template <class tVARTYPE>
00342 inline DLLNode<tVARTYPE>* DLList<tVARTYPE>::prev(DLLNode<tVARTYPE>* pNode) const
00343 {
00344 assert(pNode != NULL);
00345
00346 return pNode->m_pPrev;
00347 }
00348
00349
00350 template <class tVARTYPE>
00351 inline DLLNode<tVARTYPE>* DLList<tVARTYPE>::nodeNum(int iNum) const
00352 {
00353 DLLNode<tVARTYPE>* pNode;
00354 int iCount;
00355
00356 iCount = 0;
00357 pNode = m_pHead;
00358
00359 while (pNode != NULL)
00360 {
00361 if (iCount == iNum)
00362 {
00363 return pNode;
00364 }
00365
00366 iCount++;
00367 pNode = pNode->m_pNext;
00368 }
00369
00370 return NULL;
00371 }
00372
00373
00374 #endif //LINKEDLIST_H