doubly_linked_list.cpp

00001 //=================================================================
00002 // Implementation for DLL module.
00003 //
00004 // Copyright 2021 Georgia Tech.  All rights reserved.
00005 // The materials provided by the instructor in this course are for
00006 // the use of the students currently enrolled in the course.
00007 // Copyrighted course materials may not be further disseminated.
00008 // This file must not be made publicly available anywhere.
00009 //=================================================================
00010 #include <stdlib.h>
00011 #include <stdio.h>
00012 #include "doubly_linked_list.h"
00013 
00014 LLNode* create_llnode(void* data) {
00015   LLNode* node = (LLNode*)malloc(sizeof(LLNode));
00016   node -> prev = NULL;
00017   node -> next = NULL;
00018   node -> data = data;
00019   return node;
00020   }
00021 
00022 
00023 DLinkedList* create_dlinkedlist(void) {
00024     DLinkedList* newList = (DLinkedList*)malloc(sizeof(DLinkedList));
00025     newList->head = NULL;
00026     newList->tail = NULL;
00027     newList->size = 0;
00028     return newList;
00029 }
00030 
00031 int getSize(DLinkedList* dLinkedList){
00032   return dLinkedList -> size;
00033 }
00034 
00035 LLNode* getHead(DLinkedList* dLinkedList){
00036   return dLinkedList -> head;
00037 }
00038 
00039 LLNode* getTail(DLinkedList* dLinkedList){
00040   return dLinkedList -> tail;
00041 }
00042 
00043 LLNode* getNext(LLNode* node){
00044   return node -> next;
00045 }
00046 
00047 LLNode* getPrev(LLNode* node){
00048   return node -> prev;
00049 }
00050 
00051 void* getData(LLNode* node){
00052   return node -> data;
00053 }
00054 
00055 void insertAfter(DLinkedList* dLinkedList, LLNode* prev_node, void* data){
00056   if (prev_node == NULL) {
00057     printf("the given previous node cannot be NULL");
00058     return;
00059   }
00060   LLNode* newNode = create_llnode(data); //creates new node
00061   LLNode* nextNode = prev_node -> next; //creates next for new node
00062   //previous node is passed as argument
00063   if (nextNode != NULL) { //if prev_node is not the tail...
00064     newNode -> next = nextNode; //update next of new node
00065     nextNode -> prev = newNode; //update prev of next_node
00066   } else { //if prev_node is the tail
00067     dLinkedList -> tail = newNode; //update tail of linked list
00068   } // execute no matter what
00069   newNode -> prev = prev_node; //update prev of new node
00070   prev_node -> next = newNode; //update next of prev_node
00071   (dLinkedList -> size)++; //update size of linked list
00072   return;
00073 }
00074 
00075 void insertBefore(DLinkedList* dLinkedList, LLNode* next_node, void* data){
00076   if (next_node == NULL) {
00077     printf("the given next node cannot be NULL");
00078     return;
00079   }
00080   LLNode* newNode = create_llnode(data); //creates new node
00081   LLNode* prevNode = next_node -> prev; //creates prev for new node
00082   //next node is passed as argument
00083   if (prevNode != NULL) { //if next_node is not the head...
00084     newNode -> prev = prevNode; //update prev of new node
00085     prevNode -> next = newNode; //update next of prev node
00086   } else { //if next_node is the head
00087     dLinkedList -> head = newNode; //update head of linked list
00088   } // execute no matter what
00089   newNode -> next = next_node; //update next of new node
00090   next_node -> prev = newNode; //update prev of next_node
00091   (dLinkedList -> size)++; //update size of linked list
00092   return;
00093 }
00094 
00095 void insertHead(DLinkedList* dLinkedList, void* data) {
00096   if (dLinkedList -> head == NULL) {
00097     LLNode* newNode = create_llnode(data);
00098     dLinkedList -> head = newNode;
00099     dLinkedList -> tail = newNode;
00100     (dLinkedList -> size)++;
00101   } else {
00102     insertBefore(dLinkedList, dLinkedList -> head, data);
00103   }
00104 }
00105 
00106 void insertTail(DLinkedList* dLinkedList, void* data) {
00107   if (dLinkedList -> head == NULL ){
00108     LLNode* newNode = create_llnode(data);
00109     dLinkedList -> head = newNode;
00110     dLinkedList -> tail = newNode;
00111     (dLinkedList -> size)++;
00112   } else {
00113     insertAfter(dLinkedList, dLinkedList->tail, data);
00114   }
00115 }
00116 
00117 void deleteNode(DLinkedList* dLinkedList, LLNode* Node){
00118   //LLNode* prevNode = Node -> prev;
00119   //LLNode* nextNode = Node -> next;
00120   if (dLinkedList -> size == 1){
00121       free(Node->data);
00122       free(Node);
00123       (dLinkedList->size)--;
00124       return;
00125   }
00126   if (dLinkedList -> head == Node) {
00127     Node -> next -> prev = NULL;
00128     dLinkedList -> head = Node -> next;
00129   } else if (dLinkedList -> tail == Node) {
00130     Node -> prev -> next = NULL;
00131     dLinkedList -> tail = Node -> prev;
00132   } else {
00133     Node -> prev -> next = Node -> next;
00134     Node -> next -> prev = Node -> prev;
00135   }
00136   (dLinkedList -> size)--;
00137   free(Node -> data);
00138   free(Node);
00139   return;
00140 }
00141 
00142 void destroyList(DLinkedList* dLinkedList){
00143     if ((dLinkedList -> size) == 1) {
00144         deleteNode(dLinkedList, dLinkedList -> head);
00145         free(dLinkedList);
00146         return;
00147     }     
00148   LLNode* curr = dLinkedList -> head;
00149   if (curr == NULL) {
00150     free(dLinkedList);
00151     return;
00152   }
00153   LLNode* next = curr -> next;
00154   while (next != NULL) {
00155     deleteNode(dLinkedList, curr);
00156     curr = next;
00157     next = curr -> next;
00158   }
00159   free(dLinkedList);
00160   return;
00161 }
00162 
00163 void reverse(DLinkedList* dLinkedList){
00164   if (dLinkedList -> size <= 1){
00165     return;
00166   }
00167   LLNode* curr = dLinkedList -> head;
00168   LLNode* start = dLinkedList -> head;
00169   LLNode* dummy;
00170   while (curr != NULL){
00171     dummy = curr -> prev;
00172     curr -> prev = curr -> next;
00173     curr -> next = dummy;
00174     curr = curr -> prev;
00175   }
00176   dLinkedList -> head = dLinkedList -> tail;
00177   dLinkedList -> tail = start;
00178   return;
00179 }