doublely_linked_list.cpp

00001 #include <stdlib.h>
00002 #include <stdio.h>
00003 #include "doublely_linked_list.h "
00004 
00005 DLinkedList* create_dlinkedlist(void)
00006 {
00007 
00008 //    printf("create_dlinkedlist\n");
00009 
00010     DLinkedList* newList = (DLinkedList*) malloc(sizeof(DLinkedList));
00011 
00012     newList->size = 0;
00013     newList->head = NULL;
00014     newList->current = NULL;
00015     newList->tail = NULL;
00016 
00017     return newList;
00018 
00019 }
00020 
00021 LLNode* create_llnode(void* data)
00022 {
00023 
00024 //    printf("create_llnode\n");
00025 
00026     LLNode* newNode = (LLNode*) malloc(sizeof(LLNode));
00027 
00028     newNode->previous = NULL;
00029     newNode->next = NULL;
00030     newNode->data = data;
00031 
00032     return newNode;
00033 
00034 }
00035 
00036 
00037 void insertHead(DLinkedList* dLinkedList, void* data)
00038 {
00039 
00040 //    printf("insertHead\n");
00041 
00042     LLNode* newNode = create_llnode(data);
00043 
00044     if (dLinkedList->head == NULL) {
00045 
00046         dLinkedList->size++;
00047         dLinkedList->head = newNode;
00048         dLinkedList->tail = newNode;
00049 
00050     } else {
00051 
00052         dLinkedList->size++;
00053         newNode->next = dLinkedList->head;
00054         (dLinkedList->head)->previous = newNode;
00055         dLinkedList->head = newNode;
00056 
00057     }
00058 
00059 }
00060 
00061 
00062 void insertTail(DLinkedList* dLinkedList, void* data)
00063 {
00064 
00065 //    printf("insertTail\n");
00066 
00067     LLNode* newNode = create_llnode(data);
00068 
00069     if (dLinkedList->tail == NULL) {
00070 
00071         dLinkedList->size++;
00072         dLinkedList->tail = newNode;
00073         dLinkedList->head = newNode;
00074 
00075     } else {
00076 
00077         dLinkedList->size++;
00078         newNode->previous = dLinkedList->tail;
00079         (dLinkedList->tail)->next = newNode;
00080         dLinkedList->tail = newNode;
00081 
00082     }
00083 
00084 }
00085 
00086 int insertAfter(DLinkedList* dLinkedList, void* newData)
00087 {
00088 
00089 //    printf("insertAfter\n");
00090 
00091     if (dLinkedList->current == NULL) {
00092         return 0;
00093     }
00094 
00095     LLNode* newNode = create_llnode(newData);
00096 
00097     dLinkedList->size++;
00098     newNode->next = (dLinkedList->current)->next;
00099     newNode->previous = dLinkedList->current;
00100     if (newNode->next == NULL) {
00101         dLinkedList->tail = newNode;
00102     } else {
00103         (newNode->next)->previous = newNode;
00104     }
00105     (newNode->previous)->next = newNode;
00106 
00107     return 1;
00108 
00109 }
00110 
00111 int insertBefore(DLinkedList* dLinkedList, void* newData)
00112 {
00113 
00114 //    printf("insertBefore\n");
00115 
00116     if (dLinkedList->current == NULL) {
00117         return 0;
00118     }
00119 
00120     LLNode* newNode = create_llnode(newData);
00121 
00122     dLinkedList->size++;
00123     newNode->next = dLinkedList->current;
00124     newNode->previous = (dLinkedList->current)->previous;
00125     (newNode->next)->previous = newNode;
00126     if (newNode->previous == NULL) {
00127         dLinkedList->head = newNode;
00128     } else {
00129         (newNode->previous)->next = newNode;
00130     }
00131 
00132     return 1;
00133 
00134 }
00135 
00136 
00137 void* deleteBackward(DLinkedList* dLinkedList)
00138 {
00139 
00140 //    printf("deleteBackward\n");
00141 
00142     if (dLinkedList->current == NULL) {
00143         return NULL;
00144     }
00145 
00146     dLinkedList->size--;
00147 
00148     free((dLinkedList->current)->data);
00149 
00150     if ((dLinkedList->current)->previous == NULL) {
00151         dLinkedList->head = (dLinkedList->current)->next;
00152     } else {
00153         ((dLinkedList->current)->previous)->next = (dLinkedList->current)->next;
00154     }
00155 
00156     if ((dLinkedList->current)->next == NULL) {
00157         dLinkedList->tail = (dLinkedList->current)->previous;
00158     } else {
00159         ((dLinkedList->current)->next)->previous = (dLinkedList->current)->previous;
00160     }
00161 
00162     LLNode* newCurrent = (dLinkedList->current)->previous;
00163 
00164     free(dLinkedList->current);
00165     dLinkedList->current = newCurrent;
00166 
00167     if (dLinkedList->current == NULL) {
00168         return NULL;
00169     }
00170 
00171     return (dLinkedList->current)->data;
00172 
00173 }
00174 
00175 
00176 
00177 void* deleteForward(DLinkedList* dLinkedList)
00178 {
00179 
00180 //    printf("deleteForward\n");
00181 
00182     if (dLinkedList->current == NULL) {
00183         return NULL;
00184     }
00185 
00186     dLinkedList->size--;
00187 
00188     free((dLinkedList->current)->data);
00189 
00190     if ((dLinkedList->current)->previous == NULL) {
00191         dLinkedList->head = (dLinkedList->current)->next;
00192     } else {
00193         ((dLinkedList->current)->previous)->next = (dLinkedList->current)->next;
00194     }
00195 
00196     if ((dLinkedList->current)->next == NULL) {
00197         dLinkedList->tail = (dLinkedList->current)->previous;
00198     } else {
00199         ((dLinkedList->current)->next)->previous = (dLinkedList->current)->previous;
00200     }
00201 
00202     LLNode* newCurrent = (dLinkedList->current)->next;
00203 
00204     free(dLinkedList->current);
00205     dLinkedList->current = newCurrent;
00206 
00207     if (dLinkedList->current == NULL) {
00208         return NULL;
00209     }
00210 
00211     return (dLinkedList->current)->data;
00212 
00213 }
00214 
00215 
00216 void* removeBackward(DLinkedList* dLinkedList)
00217 {
00218 
00219 //    printf("removeBackward\n");
00220 
00221     if (dLinkedList->current == NULL) {
00222         return NULL;
00223     }
00224 
00225     dLinkedList->size--;
00226 
00227     if ((dLinkedList->current)->previous == NULL) {
00228         dLinkedList->head = (dLinkedList->current)->next;
00229     } else {
00230         ((dLinkedList->current)->previous)->next = (dLinkedList->current)->next;
00231     }
00232 
00233     if ((dLinkedList->current)->next == NULL) {
00234         dLinkedList->tail = (dLinkedList->current)->previous;
00235     } else {
00236         ((dLinkedList->current)->next)->previous = (dLinkedList->current)->previous;
00237     }
00238 
00239     void* oldData = (dLinkedList->current)->data;
00240 
00241     LLNode* newCurrent = (dLinkedList->current)->previous;
00242 
00243     free(dLinkedList->current);
00244     dLinkedList->current = newCurrent;
00245 
00246     return oldData;
00247 
00248 }
00249 
00250 void* removeForward(DLinkedList* dLinkedList)
00251 {
00252 
00253 //    printf("removeForward\n");
00254 
00255     if (dLinkedList->current == NULL) {
00256         return NULL;
00257     }
00258 
00259     dLinkedList->size--;
00260 
00261     if ((dLinkedList->current)->previous == NULL) {
00262         dLinkedList->head = (dLinkedList->current)->next;
00263     } else {
00264         ((dLinkedList->current)->previous)->next = (dLinkedList->current)->next;
00265     }
00266 
00267     if ((dLinkedList->current)->next == NULL) {
00268         dLinkedList->tail = (dLinkedList->current)->previous;
00269     } else {
00270         ((dLinkedList->current)->next)->previous = (dLinkedList->current)->previous;
00271     }
00272 
00273     void* oldData = (dLinkedList->current)->data;
00274 
00275     LLNode* newCurrent = (dLinkedList->current)->next;
00276 
00277     free(dLinkedList->current);
00278     dLinkedList->current = newCurrent;
00279 
00280     return oldData;
00281 
00282 }
00283 
00284 
00285 void destroyList(DLinkedList* dLinkedList)
00286 {
00287 
00288 //    printf("destroyList\n");
00289 
00290     if (dLinkedList->head != NULL) {
00291         getHead(dLinkedList);
00292         while(deleteForward(dLinkedList)) {};
00293     }
00294 
00295     free(dLinkedList);
00296 
00297 }
00298 
00299 
00300 void* getHead(DLinkedList* dLinkedList)
00301 {
00302 
00303 //    printf("getHead\n");
00304 
00305     dLinkedList->current = dLinkedList->head;
00306 
00307     if (dLinkedList->head == NULL) {
00308         return NULL;
00309     }
00310 
00311     return (dLinkedList->head)->data;
00312 
00313 }
00314 
00315 
00316 
00317 void* getTail(DLinkedList* dLinkedList)
00318 {
00319 
00320 //    printf("getTail\n");
00321 
00322     dLinkedList->current = dLinkedList->tail;
00323 
00324     if (dLinkedList->tail == NULL) {
00325         return NULL;
00326     }
00327 
00328     return (dLinkedList->tail)->data;
00329 
00330 }
00331 
00332 
00333 
00334 void* getCurrent(DLinkedList* dLinkedList)
00335 {
00336 
00337 //    printf("getCurrent\n");
00338 
00339     if (dLinkedList->current == NULL) {
00340         return NULL;
00341     }
00342 
00343     return (dLinkedList->current)->data;
00344 
00345 }
00346 
00347 
00348 
00349 void* getNext(DLinkedList* dLinkedList)
00350 {
00351 
00352 //    printf("getNext\n");
00353 
00354     if (dLinkedList->current == NULL) {
00355         return NULL;
00356     }
00357 
00358     dLinkedList->current = (dLinkedList->current)->next;
00359 
00360     if (dLinkedList->current == NULL) {
00361         return NULL;
00362     }
00363 
00364     return (dLinkedList->current)->data;
00365 
00366 }
00367 
00368 
00369 
00370 void* getPrevious(DLinkedList* dLinkedList)
00371 {
00372 
00373 //    printf("getPrevious\n");
00374 
00375     if (dLinkedList->current == NULL) {
00376         return NULL;
00377     }
00378 
00379     dLinkedList->current = (dLinkedList->current)->previous;
00380 
00381     if (dLinkedList->current == NULL) {
00382         return NULL;
00383     }
00384 
00385     return (dLinkedList->current)->data;
00386 
00387 }
00388 
00389 
00390 int getSize(DLinkedList* dLinkedList)
00391 {
00392 
00393 //    printf("getSize\n");
00394 
00395     return dLinkedList->size;
00396 
00397 }