File content as of revision 6:453dc852ac0f:

//=================================================================
// 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++;
        }

        
    }
}