![](/media/cache/img/default_profile.jpg.50x50_q85.jpg)
f
Dependencies: mbed 4DGL-uLCD-SE MMA8452
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