Diff: doubly_linked_list.cpp

Revision:

1:05e3f86df6d5

Parent:

0:95264f964374

--- a/doubly_linked_list.cpp	Mon Mar 29 21:17:26 2021 -0400
+++ b/doubly_linked_list.cpp	Sat Apr 17 02:34:03 2021 +0000
@@ -13,115 +13,217 @@
 
 LLNode* create_llnode(void* data) {
 
-    // Your code here
-  
-    return NULL; // replace this
+    LLNode* newNode = (LLNode*)malloc(sizeof(LLNode));
+    newNode->data = data;
+    //implement extra if there are more than one node,,, next and prev
+    newNode->next = NULL; //nodes.prev and .next are not set here and can only be changed through accessing the node
+    newNode->prev = NULL; //must has created linked list to be stored
+    return newNode; 
 }
 
-DLinkedList* create_dlinkedlist(void) {
+DLinkedList* create_dlinkedlist(void) { //creates a new linkedlist, must be deallocated after list is deleted
     DLinkedList* newList = (DLinkedList*)malloc(sizeof(DLinkedList));
-    newList->head = NULL;
-    newList->tail = NULL;
+    newList->head = NULL; //The list is only created
+    newList->tail = NULL; //There hasnt been anything stored in the list yet
     newList->size = 0;
     return newList;
 }
 
-int getSize(DLinkedList* dLinkedList){
+int getSize(DLinkedList* dLinkedList){ //returns size of list, returns 0 if there is currently nothing in the list and null if there is no list
 
-  // Your code here
+  int Rsize = dLinkedList->size; 
+  return Rsize;
+}
 
-  return 0;
+LLNode* getHead(DLinkedList* dLinkedList){//returns head of list, returns null if head is not set
+
+  struct llnode_t* Rhead = dLinkedList->head;
+  return Rhead;
 }
 
-LLNode* getHead(DLinkedList* dLinkedList){
+LLNode* getTail(DLinkedList* dLinkedList){//returns tail of list, returns null if tail is not set
+
 
-  // Your code here
+  struct llnode_t* Rtail = dLinkedList->tail;
+  return Rtail;
+}
 
-  return NULL; // replace this
+LLNode* getNext(LLNode* node){  //returns node.next of current node, returns null if next has not been set
+
+  struct llnode_t* Rnext = node->next;
+  return Rnext;
 }
 
-LLNode* getTail(DLinkedList* dLinkedList){
+LLNode* getPrev(LLNode* node){//returns node.prev of current node, returns null if prev has not been set
 
-  // Your code here
-
-  return NULL; // replace this
+  struct llnode_t* Rprev = node->prev;
+  return Rprev;
 }
 
-LLNode* getNext(LLNode* node){
-
-  // Your code here
-
-  return NULL; // replace this
-}
-
-LLNode* getPrev(LLNode* node){
+void* getData(LLNode* node){ //returns node.data of current node, returns null if data has not been set yet for current node
 
-  // Your code here
-
-  return NULL; // replace this
+  if(node==NULL){
+    return NULL;
+  }
+void* Rdata = node->data;  
+return Rdata;
 }
-
-void* getData(LLNode* node){
-
-  // Your code here
-
-  return NULL; // replace this
+LLNode* getNode(DLinkedList* dLinkedList, int pos){ //included new return function for accessing node
+    if(dLinkedList->size == 0){ //size has to be greater than 0 in order to access node, returns error if no list present
+      printf("Empty List, Returning NULL \n");
+      return NULL;
+    }
+    else if(pos > (dLinkedList->size-1)){ //the selected position must also be selected from within the size parameters of the list
+      printf("Position is out of size parameters \n");
+      return NULL;
+    } 
+    pos = dLinkedList->size - pos - 1; //returns tail if pos = 0
+    LLNode* node = dLinkedList->head;
+    while(pos > 0){ //moves through the list of nodes until it reaches the selected node
+      node = node->next;
+      pos--;
+    }
+  return node;
 }
 
 void insertAfter(DLinkedList* dLinkedList, LLNode* prev_node, void* data){
+
   if (prev_node == NULL) {
-    printf("the given previous node cannot be NULL");
+    printf("the given previous node cannot be NULL\n");
+    //Thrown Error, function needs to be used on non empty list
     return;
   }
+  else{
+    LLNode* newNode = create_llnode(data); //created holder node to be inserted into list
 
-  // Your code here
+    dLinkedList->size++;  //increments the size of the list due to adding extra node
+
+    if(prev_node->next != NULL){  //if prev_node.next is null then it is on the tail and doesnt need a node.next 
+      (prev_node->next)->prev = newNode;
+      newNode->next = (prev_node->next);
+    }
 
+    prev_node->next = newNode; //adjusts side nodes to point to correct positions 
+    newNode->prev = prev_node;
+    if(prev_node == dLinkedList->tail){ //setting new tail if node is places after tail
+      dLinkedList->tail = newNode;
+    }
+  }
   return;
 }
 
 void insertBefore(DLinkedList* dLinkedList, LLNode* next_node, void* data){
+  
   if (next_node == NULL) {
-    printf("the given next node cannot be NULL");
+    printf("the given next node cannot be NULL\n"); //Thrown Error, function needs to be used on non empty list
+    //cannt be NULL, but it was then (dLinkedList->head = newNode;)
     return;
   }
+  else{
+    LLNode* newNode = create_llnode(data);
+    dLinkedList->size++; //increments the size of the list due to adding extra node
 
-  // Your code here
-
+    if(next_node->prev != NULL){ //if next_node.prev is null then it is on the head and doesnt need a node.prev 
+      (next_node->prev)->next = newNode;
+      newNode->prev = (next_node->prev);
+    }
+    next_node->prev = newNode; //adjusts side nodes to point to correct positions 
+    newNode->next = next_node;
+    if(next_node == dLinkedList->head){ //setting new head if node is being placed before head
+      dLinkedList->head = newNode;
+    }
+  }
   return;
 }
 
 void insertHead(DLinkedList* dLinkedList, void* data){
-  if(dLinkedList->head == NULL){
-    LLNode* newNode = create_llnode(data);
+  //using insertbefore method to place new node at the head of the linkedlist
+  if(dLinkedList->head == NULL){ //if there is no current head of list, then there are no nodes in list
+    LLNode* newNode = create_llnode(data); //creates new head and tail of list 
     dLinkedList->head = newNode;
     dLinkedList->tail = newNode;
     dLinkedList->size++; 
   }else{
-    insertBefore(dLinkedList, dLinkedList->head, data);
+    insertBefore(dLinkedList, dLinkedList->head, data); //inserts new node before head to become new head
   }
 }
 
 void insertTail(DLinkedList* dLinkedList, void* data){
-
-  // Your code here
-
+  //using insertafter method to place new node at the tail of the linkedlist 
+ if(dLinkedList->tail == NULL){ //if there are no current tail of list, then there are no nodes within list
+    LLNode* newNode = create_llnode(data); //create new head and tail of list and increments size
+    dLinkedList->head = newNode;
+    dLinkedList->tail = newNode;
+    dLinkedList->size++; 
+  }else{
+    insertAfter(dLinkedList, dLinkedList->tail, data); //inserts new node after tail to become new tail
+  }
 }
 
 void deleteNode(DLinkedList* dLinkedList, LLNode* Node){
+  // need to free up node infomation
+  if(dLinkedList->size != 0){ //first checks if there are nodes to delete within list
 
-  // Your code here
+    if(dLinkedList->size > 1){ //adjusts side nodes and selects new heaed for list
+      if(Node == dLinkedList->head){
+        dLinkedList->head = Node->next;
+        (dLinkedList->head)->prev = NULL;
+        
+      }
+      else if(Node == dLinkedList->tail){  //adusts side nodes and selects new tail for list
+        dLinkedList->tail = Node->prev;
+        (dLinkedList->tail)->next = NULL;
+      }
+      else{ //adjusts side nodes if selected node is within bounds
+        (Node->next)->prev = Node->prev;
+        (Node->prev)->next = Node->next;
+      }
+    }
 
+    else{ //currently only 1 node within list, delete node and remove list.head and tail do to no nodes being within the list
+      dLinkedList->head = NULL;
+      dLinkedList->tail = NULL;
+    }
+    free(Node->data); //frees data in node and node position
+    free(Node);
+    dLinkedList->size--; //deincrments list size
+  }
+  return;
 }
 
 void destroyList(DLinkedList* dLinkedList){
-
-  // Your code here
-
+  LLNode* current; 
+  for(int i =0;i<(dLinkedList->size);i++){
+     current = getNode(dLinkedList,i); //increments through the list and deallocates each node.data and node 
+    free(current->data);
+    free(current);
+  }
+  free(dLinkedList); //finally deallocates the list 
+  return;
 }
 
 void reverse(DLinkedList* dLinkedList)
 {
+  int n = dLinkedList->size;  //gets size to use for while to move through list
+  LLNode* holderNode = dLinkedList->head; //set holder node
+  dLinkedList->tail = dLinkedList->head;
+  while(n>1){ //adjusting all nodes.prev nodes
+    holderNode->prev = holderNode->next;
+    holderNode = holderNode->prev;
+    n--;
+  }
+  n = dLinkedList->size;
+  dLinkedList->head = holderNode;
+  holderNode = dLinkedList->tail;
+  while(n>1){ //adjusting all nodes.next node
+    (holderNode->prev)->next = holderNode;
+    holderNode = holderNode->prev;
+    n--;
+  }
+  (dLinkedList->head)->prev = NULL; //adjust head and tail of list as to not allow for extra nodes on ends
+  (dLinkedList->tail)->next = NULL;
+  return;
+}     
 
-  // Your code here
 
-}     
+