Diff: doubly_linked_list.cpp

Revision:

1:4421c1e849e9

Parent:

0:95264f964374

--- a/doubly_linked_list.cpp	Mon Mar 29 21:17:26 2021 -0400
+++ b/doubly_linked_list.cpp	Fri Apr 09 20:44:48 2021 +0000
@@ -12,11 +12,13 @@
 #include "doubly_linked_list.h"
 
 LLNode* create_llnode(void* data) {
+  LLNode* node = (LLNode*)malloc(sizeof(LLNode));
+  node -> prev = NULL;
+  node -> next = NULL;
+  node -> data = data;
+  return node;
+  }
 
-    // Your code here
-  
-    return NULL; // replace this
-}
 
 DLinkedList* create_dlinkedlist(void) {
     DLinkedList* newList = (DLinkedList*)malloc(sizeof(DLinkedList));
@@ -27,45 +29,27 @@
 }
 
 int getSize(DLinkedList* dLinkedList){
-
-  // Your code here
-
-  return 0;
+  return dLinkedList -> size;
 }
 
 LLNode* getHead(DLinkedList* dLinkedList){
-
-  // Your code here
-
-  return NULL; // replace this
+  return dLinkedList -> head;
 }
 
 LLNode* getTail(DLinkedList* dLinkedList){
-
-  // Your code here
-
-  return NULL; // replace this
+  return dLinkedList -> tail;
 }
 
 LLNode* getNext(LLNode* node){
-
-  // Your code here
-
-  return NULL; // replace this
+  return node -> next;
 }
 
 LLNode* getPrev(LLNode* node){
-
-  // Your code here
-
-  return NULL; // replace this
+  return node -> prev;
 }
 
 void* getData(LLNode* node){
-
-  // Your code here
-
-  return NULL; // replace this
+  return node -> data;
 }
 
 void insertAfter(DLinkedList* dLinkedList, LLNode* prev_node, void* data){
@@ -73,9 +57,18 @@
     printf("the given previous node cannot be NULL");
     return;
   }
-
-  // Your code here
-
+  LLNode* newNode = create_llnode(data); //creates new node
+  LLNode* nextNode = prev_node -> next; //creates next for new node
+  //previous node is passed as argument
+  if (nextNode != NULL) { //if prev_node is not the tail...
+    newNode -> next = nextNode; //update next of new node
+    nextNode -> prev = newNode; //update prev of next_node
+  } else { //if prev_node is the tail
+    dLinkedList -> tail = newNode; //update tail of linked list
+  } // execute no matter what
+  newNode -> prev = prev_node; //update prev of new node
+  prev_node -> next = newNode; //update next of prev_node
+  (dLinkedList -> size)++; //update size of linked list
   return;
 }
 
@@ -84,44 +77,103 @@
     printf("the given next node cannot be NULL");
     return;
   }
-
-  // Your code here
-
+  LLNode* newNode = create_llnode(data); //creates new node
+  LLNode* prevNode = next_node -> prev; //creates prev for new node
+  //next node is passed as argument
+  if (prevNode != NULL) { //if next_node is not the head...
+    newNode -> prev = prevNode; //update prev of new node
+    prevNode -> next = newNode; //update next of prev node
+  } else { //if next_node is the head
+    dLinkedList -> head = newNode; //update head of linked list
+  } // execute no matter what
+  newNode -> next = next_node; //update next of new node
+  next_node -> prev = newNode; //update prev of next_node
+  (dLinkedList -> size)++; //update size of linked list
   return;
 }
 
-void insertHead(DLinkedList* dLinkedList, void* data){
-  if(dLinkedList->head == NULL){
+void insertHead(DLinkedList* dLinkedList, void* data) {
+  if (dLinkedList -> head == NULL) {
     LLNode* newNode = create_llnode(data);
-    dLinkedList->head = newNode;
-    dLinkedList->tail = newNode;
-    dLinkedList->size++; 
-  }else{
-    insertBefore(dLinkedList, dLinkedList->head, data);
+    dLinkedList -> head = newNode;
+    dLinkedList -> tail = newNode;
+    (dLinkedList -> size)++;
+  } else {
+    insertBefore(dLinkedList, dLinkedList -> head, data);
+  }
+}
+
+void insertTail(DLinkedList* dLinkedList, void* data) {
+  if (dLinkedList -> head == NULL ){
+    LLNode* newNode = create_llnode(data);
+    dLinkedList -> head = newNode;
+    dLinkedList -> tail = newNode;
+    (dLinkedList -> size)++;
+  } else {
+    insertAfter(dLinkedList, dLinkedList->tail, data);
   }
 }
 
-void insertTail(DLinkedList* dLinkedList, void* data){
-
-  // Your code here
-
-}
-
 void deleteNode(DLinkedList* dLinkedList, LLNode* Node){
-
-  // Your code here
-
+  //LLNode* prevNode = Node -> prev;
+  //LLNode* nextNode = Node -> next;
+  if (dLinkedList -> size == 1){
+      free(Node->data);
+      free(Node);
+      (dLinkedList->size)--;
+      return;
+  }
+  if (dLinkedList -> head == Node) {
+    Node -> next -> prev = NULL;
+    dLinkedList -> head = Node -> next;
+  } else if (dLinkedList -> tail == Node) {
+    Node -> prev -> next = NULL;
+    dLinkedList -> tail = Node -> prev;
+  } else {
+    Node -> prev -> next = Node -> next;
+    Node -> next -> prev = Node -> prev;
+  }
+  (dLinkedList -> size)--;
+  free(Node -> data);
+  free(Node);
+  return;
 }
 
 void destroyList(DLinkedList* dLinkedList){
-
-  // Your code here
-
+    if ((dLinkedList -> size) == 1) {
+        deleteNode(dLinkedList, dLinkedList -> head);
+        free(dLinkedList);
+        return;
+    }     
+  LLNode* curr = dLinkedList -> head;
+  if (curr == NULL) {
+    free(dLinkedList);
+    return;
+  }
+  LLNode* next = curr -> next;
+  while (next != NULL) {
+    deleteNode(dLinkedList, curr);
+    curr = next;
+    next = curr -> next;
+  }
+  free(dLinkedList);
+  return;
 }
 
-void reverse(DLinkedList* dLinkedList)
-{
-
-  // Your code here
-
-}     
+void reverse(DLinkedList* dLinkedList){
+  if (dLinkedList -> size <= 1){
+    return;
+  }
+  LLNode* curr = dLinkedList -> head;
+  LLNode* start = dLinkedList -> head;
+  LLNode* dummy;
+  while (curr != NULL){
+    dummy = curr -> prev;
+    curr -> prev = curr -> next;
+    curr -> next = dummy;
+    curr = curr -> prev;
+  }
+  dLinkedList -> head = dLinkedList -> tail;
+  dLinkedList -> tail = start;
+  return;
+}