Diff: doubly_linked_list.cpp

Revision:

0:294bc2018c3a

Child:

1:c24e4dd27d48

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/doubly_linked_list.cpp	Wed Oct 12 15:03:24 2016 +0000
@@ -0,0 +1,379 @@
+#include <stdlib.h>
+#include <stdio.h>
+#include "doubly_linked_list.h"
+
+
+/**
+ * create_llnode
+ *
+ * Helper function that creates a node by allocating memory for it on the heap,
+ * and initializing any pointers in it to NULL.
+ *
+ * @param data A void pointer to data the user is adding to the doublely linked list.
+ * @return The llnode
+ */
+LLNode* create_llnode(void* data) {
+    LLNode* newNode = (LLNode*)malloc(sizeof(LLNode));
+    newNode->data = data;
+    newNode->previous = NULL;
+    newNode->next = NULL;
+    return newNode;
+}
+
+
+/**
+ * create_dlinkedlist
+ *
+ * Creates a doublely liked list by allocating memory for it on the heap. Initialize the size to zero, as well as head and tail to NULL.
+ *
+ * @return An empty dlinkedlist
+ */
+DLinkedList* create_dlinkedlist(void) {
+    DLinkedList* newList = (DLinkedList*)malloc(sizeof(DLinkedList));
+    newList->head = NULL;
+    newList->tail = NULL;
+    newList->current = NULL;
+    newList->size = 0;
+    return newList;
+}
+
+/**
+ * insertHead
+ *
+ * insert the data to the head of the doublely linked list
+ *
+ * @param data A void pointer to data the user is adding to the doublely linked list.
+ * 
+ */
+
+void insertHead(DLinkedList* dLinkedList, void* data){
+  LLNode* newNode = create_llnode(data);
+  if(dLinkedList->head == NULL){
+    dLinkedList->size++;
+    dLinkedList->head = newNode;
+    dLinkedList->current = newNode;
+    dLinkedList->tail = newNode;
+  }else{
+    dLinkedList->size++;
+    newNode->next = dLinkedList->head;
+    (dLinkedList->head)->previous = newNode;
+    dLinkedList->head = newNode;
+  }
+}
+
+/**
+ * insertEnd
+ *
+ * insert the data to the tail of the doublely linked list
+ *
+ * @param data A void pointer to data the user is adding to the doublely linked list.
+ * 
+ */
+
+void insertTail(DLinkedList* dLinkedList, void* data){
+  LLNode* newNode = create_llnode(data);
+  if(dLinkedList->tail == NULL){
+    dLinkedList->size++;
+    dLinkedList->head = newNode;
+    dLinkedList->current = newNode;
+    dLinkedList->tail = newNode;
+  }else{
+    dLinkedList->size++;
+    newNode->previous = dLinkedList->tail;
+    (dLinkedList->tail)->next = newNode;
+    dLinkedList->tail = newNode;
+  }
+}
+
+/**
+ * insertAfter
+ *
+ * insert the new data to the doublely linked list right after the current pointer
+ *
+ * @param newData A void pointer to the new data that the user want to add after data
+ * @return 1 if insert the new data successfully
+ *         0 if not
+ */
+
+int insertAfter(DLinkedList* dLinkedList, void* newData){
+  if(dLinkedList->current == NULL){
+    return 0;
+  }else{
+    LLNode* newNode = create_llnode(newData);
+    newNode->previous =  dLinkedList->current;
+    newNode->next =  (dLinkedList->current)->next;
+    if(dLinkedList->current == dLinkedList->tail){
+      dLinkedList->tail = newNode;
+    }else{
+      ((dLinkedList->current)->next)->previous = newNode;    
+    }
+    (dLinkedList->current)->next = newNode;
+    dLinkedList->size++;
+    return 1;     
+  }
+
+}
+/**
+ * insertBefore
+ *
+ * insert the new data to the doublely linked list right before the current pointer
+ *
+ * @param newData A void pointer to the new data that the user want to add after data
+ * @return 1 if insert the new data successfully
+ *         0 if not
+ */
+
+int insertBefore(DLinkedList* dLinkedList, void* newData){
+  if(dLinkedList->current == NULL){
+    return 0;
+  }else{
+    LLNode* newNode = create_llnode(newData);
+    newNode->next = dLinkedList->current;
+    newNode->previous = (dLinkedList->current)->previous;
+    if(dLinkedList->current == dLinkedList->head){
+      dLinkedList->head = newNode;
+    }else{
+      ((dLinkedList->current)->previous)->next = newNode;
+    }
+    (dLinkedList->current)->previous = newNode;
+    dLinkedList->size++;
+    return 1;
+  }
+}
+
+/**
+ * deleteBackward
+ *
+ * delete the node the current pointer is pointed at, and move the pointer backwards
+ *
+ * @param  free_func The function that the user created to free the data.
+ * @return 1 if deleted successfully
+ *         0 if not
+ */
+
+void* deleteBackward(DLinkedList* dLinkedList, dll_op free_func){
+  if(dLinkedList->current != NULL){
+    LLNode* deleteNode = dLinkedList->current;
+    if((dLinkedList->current)->next != NULL){
+      ((dLinkedList->current)->next)->previous = (dLinkedList->current)->previous;   
+    }
+    if((dLinkedList->current)->previous != NULL){
+      ((dLinkedList->current)->previous)->next = (dLinkedList->current)->next;
+    }
+    if((dLinkedList->current) == (dLinkedList->tail)){
+      dLinkedList->tail = (dLinkedList->current)->previous;
+    }
+    if((dLinkedList->current) == (dLinkedList->head)){
+      dLinkedList->head = (dLinkedList->current)->next;
+    }
+    if((dLinkedList->current)->previous != NULL){
+      dLinkedList->current = (dLinkedList->current)->previous;
+    }else{
+      dLinkedList->current = NULL;
+    }
+    free_func(deleteNode->data);
+    free(deleteNode);
+    dLinkedList->size--;
+    if(dLinkedList->current != NULL){
+      return (dLinkedList->current)->data;
+    }else{
+      return NULL;
+    }
+  }else{
+    return NULL;
+  }
+}
+
+
+/**
+ * deleteForward
+ *
+ * delete the node the current pointer is pointed at, and move the pointer to the next
+ *
+ * @param  free_func The function that the user created to free the data.
+ * @return 1 if deleted successfully
+ *         0 if not
+ */
+
+void* deleteForward(DLinkedList* dLinkedList, dll_op free_func){
+  if(dLinkedList->current != NULL){
+    LLNode* deleteNode = dLinkedList->current;
+    if((dLinkedList->current)->next != NULL){
+      ((dLinkedList->current)->next)->previous = (dLinkedList->current)->previous;
+    }
+    if((dLinkedList->current)->previous != NULL){
+      ((dLinkedList->current)->previous)->next = (dLinkedList->current)->next;
+    }
+    if((dLinkedList->current) == (dLinkedList->tail)){
+      dLinkedList->tail = (dLinkedList->current)->previous;
+    }
+    if((dLinkedList->current) == (dLinkedList->head)){
+      dLinkedList->head = (dLinkedList->current)->next;
+    }
+    if((dLinkedList->current)->next != NULL){
+      dLinkedList->current = (dLinkedList->current)->next;
+    }else{
+      dLinkedList->current = NULL;
+    }
+    free_func(deleteNode->data);
+    free(deleteNode);
+    dLinkedList->size--;
+    if(dLinkedList->current != NULL){
+      return (dLinkedList->current)->data;
+    }else{
+      return NULL;
+    }
+  }else{
+    return NULL;
+  }
+}
+
+
+/**
+ * traverseList
+ *
+ * traverse the list and do something on each pieae of data
+ *
+ * @param  do_func The function to perform on each piece of data.
+ *
+ */
+
+void traverseList(DLinkedList* dLinkedList, dll_op do_func){
+  if(dLinkedList->head != NULL){
+    LLNode* thisNode = dLinkedList->head;
+    do{
+      do_func(thisNode->data);
+      thisNode = thisNode->next;
+    }while(thisNode != NULL);
+  }else{
+    if(dLinkedList->head == NULL){
+        printf("Null head\n");
+    }
+     if(dLinkedList->tail == NULL){
+        printf("Null tail\n");
+    }
+      if(dLinkedList->current == NULL){
+        printf("Null current\n");
+    }
+  }
+}
+
+
+/**
+ * destroyList
+ *
+ * Destroy the doublely linked list. Everything in the linked list including list structure,
+ * nodes and data are all freed from the heap.
+ *
+ * @param  do_func The function to perform on each piece of data.
+ *
+ */
+
+void destroyList(DLinkedList* dLinkedList, dll_op free_func){
+  if(dLinkedList->head != NULL){
+    getHead(dLinkedList);
+    while(deleteForward(dLinkedList,free_func)){};
+  }
+  free(dLinkedList);
+}
+
+
+/**
+ * getHead
+ *
+ * return the data contained in the head of the doublely linked list, and set the current pointer
+ * to head
+ * @return the head data or  NULL if head == NULL
+ */
+
+void* getHead(DLinkedList* dLinkedList){
+  if(dLinkedList->head != NULL){
+    dLinkedList->current = dLinkedList->head;
+    return (dLinkedList->head)->data;
+  }else{
+    return NULL;
+  }
+}
+
+/**
+ * getTail
+ *
+ * return the data contained in the tail of the doublely linked list, and set the current pointer
+ * to tail
+ * @return the tail data or  NULL if tail == NULL
+ */
+void* getTail(DLinkedList* dLinkedList){
+  if(dLinkedList->tail != NULL){
+    dLinkedList->current = dLinkedList->tail;
+    return (dLinkedList->tail)->data;
+  }else{
+    return NULL;
+  }
+}
+
+/**
+ * getTail
+ *
+ * return the data the current pointer is pointing at
+ * @return the current data or  NULL if current == NULL
+ */
+
+void* getCurrent(DLinkedList* dLinkedList){
+  if((dLinkedList->current) == NULL){
+    return NULL;
+  }else {
+    return (dLinkedList->current)->data;
+  }
+}
+
+/**
+ * getNext
+ *
+ * return the next data the current pointer is pointing at, and move the current pointer to next
+ * @return the next data or  NULL if current == NULL
+ */
+
+void* getNext(DLinkedList* dLinkedList){
+  if(dLinkedList->current == NULL){
+    return NULL;
+  }else if((dLinkedList->current)->next == NULL){
+    dLinkedList->current = NULL;
+    return NULL;
+  }else {
+    dLinkedList->current = dLinkedList->current->next;
+    return dLinkedList->current->data;
+  }
+}
+
+/**
+ * getPrevious
+ *
+ * return the previous data the current pointer is pointing at, and move the current pointer to 
+ * previous
+ * @return the previous data or  NULL if current == NULL
+ */
+
+void* getPrevious(DLinkedList* dLinkedList){
+  if(dLinkedList->current == NULL){
+    return NULL;
+  }else if((dLinkedList->current)->previous == NULL){
+    dLinkedList->current = NULL;
+    return NULL;
+  }else {
+    dLinkedList->current = dLinkedList->current->previous;
+    return dLinkedList->current->data;
+  }
+}
+
+
+/**
+ * getSize
+ *
+ * @return  the size
+ */
+
+int getSize(DLinkedList* dLinkedList){
+  return dLinkedList->size;
+}
+
+