Diff: doubly_linked_list.cpp

Revision:

6:453dc852ac0f

Parent:

0:8e3b9bb1084a

--- a/doubly_linked_list.cpp	Mon Mar 14 23:38:03 2022 +0000
+++ b/doubly_linked_list.cpp	Tue Apr 12 01:39:20 2022 +0000
@@ -1,1 +1,255 @@
-//Put your DLL from P2-1 in here
\ No newline at end of file
+//=================================================================
+// Implementation for DLL module.
+//
+// Copyright 2022 Georgia Tech.  All rights reserved.
+// The materials provided by the instructor in this course are for
+// the use of the students currently enrolled in the course.
+// Copyrighted course materials may not be further disseminated.
+// This file must not be made publicly available anywhere.
+//=================================================================
+#include <stdlib.h>
+#include <stdio.h>
+#include "doubly_linked_list.h"
+
+//===========================
+/* Creating nodes and lists */
+//===========================
+
+LLNode* create_llnode(void* data) {
+    LLNode* newNode = (LLNode*)malloc(sizeof(LLNode));
+    newNode->data = data;
+    newNode->next = NULL;
+    newNode->prev = NULL;
+    return newNode;
+}
+
+DLinkedList* create_dlinkedlist(CompareFunction compare) {
+    DLinkedList* newList = (DLinkedList*)malloc(sizeof(DLinkedList));
+    newList->head = NULL;
+    newList->tail = NULL;
+    newList->size = 0;
+    newList->compare = compare;
+    return newList;
+}
+
+//============================
+/* Accessing nodes and lists */
+//============================
+
+int getSize(DLinkedList* dLinkedList){
+    int s = dLinkedList->size;
+    return s;
+
+}
+
+LLNode* getHead(DLinkedList* dLinkedList){
+    return dLinkedList->head;
+}
+
+LLNode* getTail(DLinkedList* dLinkedList){
+    return dLinkedList->tail;
+}
+
+LLNode* getNext(LLNode* node){
+    return node->next;
+}
+
+LLNode* getPrev(LLNode* node){
+    return node->prev;
+}
+
+void* getData(LLNode* node){
+    return node->data;
+}
+
+//============================
+/* Inserting nodes into lists */
+//============================
+
+void insertAfter(DLinkedList* dLinkedList, LLNode* prev_node, void* data){
+    LLNode* newNode = create_llnode(data);  //Creates new Node
+    LLNode* nextNode = getNext(prev_node);  //gets a pointer for the next node
+    if (prev_node != NULL) {
+        if (nextNode == NULL) {  //if the node passed through is the tail then inserts the new node as the new tail
+            prev_node->next = newNode;
+            newNode->prev = prev_node;
+            dLinkedList->tail = newNode;
+            dLinkedList->size = dLinkedList->size + 1;
+        }
+        else { //if the node passed through is not the tail then inserts the new node after and updates surrounding nodes
+            newNode->next = nextNode;
+            nextNode->prev = newNode;
+            prev_node->next = newNode;
+            newNode->prev = prev_node;
+            dLinkedList->size = dLinkedList->size + 1;
+        }
+    }
+    else {
+        printf("ERROR: Node is Null\n");
+    }
+}
+
+
+void insertBefore(DLinkedList* dLinkedList, LLNode* prev_node, void* data){
+    LLNode* newNode = create_llnode(data);  //Creates new node
+    LLNode* prevNode = getPrev(prev_node);  //gets a pointer for the prev node
+    if (prev_node != NULL) {
+        if (prevNode == NULL) {     // if the node passed through is the head then inserts the node as the new head
+            prev_node->prev = newNode;
+            newNode->next = prev_node;
+            dLinkedList->head = newNode;
+            dLinkedList->size = dLinkedList->size + 1;
+        }
+        else { //if the node passed through is not the head then inserts the new node before and updates surrounding nodes
+            newNode->prev = getPrev(prev_node);
+            prevNode->next = newNode;
+            prev_node->prev = newNode;
+            newNode->next = prev_node;
+            dLinkedList->size = dLinkedList->size + 1;
+        }
+    }
+    else {
+        printf("ERROR: Node is Null\n");
+    }
+}
+
+
+void insertHead(DLinkedList* dLinkedList, void* data){ //inserts data at the head
+    LLNode* newHead = create_llnode(data);
+    if (dLinkedList == NULL) { //if dLinkedList does not exist throws an error message
+        printf("Cant' do that");
+        return;
+    }
+    else if (dLinkedList->head == NULL) {
+        dLinkedList->head = newHead;
+        dLinkedList->tail = newHead;
+        dLinkedList->size = dLinkedList->size + 1;
+    }
+    else {
+        LLNode* oldHead = dLinkedList->head;
+        dLinkedList->head = newHead;
+        newHead->next = oldHead;
+        oldHead->prev = newHead;
+        dLinkedList->size = dLinkedList->size + 1;
+    }
+}
+
+void insertTail(DLinkedList* dLinkedList, void* data) { //if dLinkedList does not exist throws an error message
+    LLNode* newTail = create_llnode(data);
+    if (dLinkedList == NULL) {
+        printf("Cant' do that");
+        return;
+    }
+    else if (dLinkedList->head == NULL) {
+        dLinkedList->head = newTail;
+        dLinkedList->tail = newTail;
+        dLinkedList->size = dLinkedList->size + 1;
+    }
+    else {
+        LLNode* oldTail = dLinkedList->tail;
+        dLinkedList->tail = newTail;
+        newTail->prev = oldTail;
+        oldTail->next = newTail;
+        dLinkedList->size = dLinkedList->size + 1;
+    }
+
+}
+
+//============================
+/* Looking up nodes in lists */
+//============================
+
+LLNode* findNode(DLinkedList* dLinkedList, void* data){
+    //LLNode* findNode = create_llnode(data);
+   
+    LLNode* compNode = dLinkedList->head;
+    if (compNode == NULL) {
+        return NULL;
+    }
+    //runs through dLinkedList looking for data
+    int i;
+    for (i = 0; i < dLinkedList->size; i++) {
+        int j = dLinkedList->compare(compNode->data, data);
+        if (j == 1) {
+            return compNode;
+        }
+        else {
+            compNode = compNode->next;
+        }
+    }
+    return NULL;
+}
+
+//===========================
+/* Deleting nodes and lists */
+//===========================
+
+void deleteNode(DLinkedList* dLinkedList, LLNode* Node){
+    if (Node != NULL){
+        LLNode* PrevNode = getPrev(Node);
+        LLNode* NextNode = getNext(Node);
+        if (PrevNode == NULL && NextNode != NULL) { //if head delets noed and updates the head of the list
+            dLinkedList->head = NextNode;
+            dLinkedList->size = dLinkedList->size - 1;
+            NextNode->prev = NULL;
+        }
+        else if (NextNode == NULL && PrevNode != NULL) { //if tail delets the node and updates the tail of the list
+            dLinkedList->tail = PrevNode;
+            dLinkedList->size = dLinkedList->size - 1;
+            PrevNode->next = NULL;
+        }
+        else if (PrevNode == NULL && NextNode == NULL) {
+            dLinkedList->tail = NULL;
+            dLinkedList->head = NULL;
+            dLinkedList->size = dLinkedList->size - 1;
+        }
+        else {
+            dLinkedList->size = dLinkedList->size - 1;
+            (Node->prev)->next = NextNode;
+            (Node->next)->prev = PrevNode;
+        }
+    }
+    //free(Node->data);
+    free(Node);
+}
+
+
+void destroyList(DLinkedList* dLinkedList){
+    LLNode* startNode = dLinkedList->head;
+    LLNode* nextNode;
+    if (startNode != NULL) {
+        nextNode = startNode->next;
+    }
+    int i;
+    for (i = 0; i < getSize(dLinkedList); i++) {
+        free(startNode->data);
+        free(startNode);
+        startNode = nextNode;
+        if (startNode != NULL) {
+            nextNode = startNode->next;
+        }
+    }
+    free(dLinkedList);
+}
+
+//==================
+/* Reversing lists */
+//==================
+void reverse(DLinkedList* dLinkedList) {
+    if (dLinkedList->size > 1) {
+        LLNode* headNode = dLinkedList->head;
+        LLNode* tailNode = dLinkedList->tail;
+        LLNode* tempNode = dLinkedList->head;
+        int i = 0;
+        dLinkedList->head = tailNode;
+        dLinkedList->tail = headNode;
+        while (i < dLinkedList->size) {
+            headNode->prev = headNode->next;
+            tempNode = headNode->prev;
+            headNode = tempNode;
+            i++;
+        }
+
+        
+    }
+}
\ No newline at end of file