Dylan Frausto / Mbed 2 deprecated mberdl_shell_rev_b

f

Dependencies:   mbed 4DGL-uLCD-SE MMA8452

doubly_linked_list.cpp@6:453dc852ac0f, 2022-04-12 (annotated)

Committer:
dfrausto3
Date:
Tue Apr 12 01:39:20 2022 +0000
Revision:
6:453dc852ac0f
Parent:
0:8e3b9bb1084a 
f

Who changed what in which revision?

UserRevisionLine numberNew contents of line
dfrausto3 6:453dc852ac0f 1 //=================================================================
dfrausto3 6:453dc852ac0f 2 // Implementation for DLL module.
dfrausto3 6:453dc852ac0f 3 //
dfrausto3 6:453dc852ac0f 4 // Copyright 2022 Georgia Tech. All rights reserved.
dfrausto3 6:453dc852ac0f 5 // The materials provided by the instructor in this course are for
dfrausto3 6:453dc852ac0f 6 // the use of the students currently enrolled in the course.
dfrausto3 6:453dc852ac0f 7 // Copyrighted course materials may not be further disseminated.
dfrausto3 6:453dc852ac0f 8 // This file must not be made publicly available anywhere.
dfrausto3 6:453dc852ac0f 9 //=================================================================
dfrausto3 6:453dc852ac0f 10 #include <stdlib.h>
dfrausto3 6:453dc852ac0f 11 #include <stdio.h>
dfrausto3 6:453dc852ac0f 12 #include "doubly_linked_list.h"
dfrausto3 6:453dc852ac0f 13
dfrausto3 6:453dc852ac0f 14 //===========================
dfrausto3 6:453dc852ac0f 15 /* Creating nodes and lists */
dfrausto3 6:453dc852ac0f 16 //===========================
dfrausto3 6:453dc852ac0f 17
dfrausto3 6:453dc852ac0f 18 LLNode* create_llnode(void* data) {
dfrausto3 6:453dc852ac0f 19 LLNode* newNode = (LLNode*)malloc(sizeof(LLNode));
dfrausto3 6:453dc852ac0f 20 newNode->data = data;
dfrausto3 6:453dc852ac0f 21 newNode->next = NULL;
dfrausto3 6:453dc852ac0f 22 newNode->prev = NULL;
dfrausto3 6:453dc852ac0f 23 return newNode;
dfrausto3 6:453dc852ac0f 24 }
dfrausto3 6:453dc852ac0f 25
dfrausto3 6:453dc852ac0f 26 DLinkedList* create_dlinkedlist(CompareFunction compare) {
dfrausto3 6:453dc852ac0f 27 DLinkedList* newList = (DLinkedList*)malloc(sizeof(DLinkedList));
dfrausto3 6:453dc852ac0f 28 newList->head = NULL;
dfrausto3 6:453dc852ac0f 29 newList->tail = NULL;
dfrausto3 6:453dc852ac0f 30 newList->size = 0;
dfrausto3 6:453dc852ac0f 31 newList->compare = compare;
dfrausto3 6:453dc852ac0f 32 return newList;
dfrausto3 6:453dc852ac0f 33 }
dfrausto3 6:453dc852ac0f 34
dfrausto3 6:453dc852ac0f 35 //============================
dfrausto3 6:453dc852ac0f 36 /* Accessing nodes and lists */
dfrausto3 6:453dc852ac0f 37 //============================
dfrausto3 6:453dc852ac0f 38
dfrausto3 6:453dc852ac0f 39 int getSize(DLinkedList* dLinkedList){
dfrausto3 6:453dc852ac0f 40 int s = dLinkedList->size;
dfrausto3 6:453dc852ac0f 41 return s;
dfrausto3 6:453dc852ac0f 42
dfrausto3 6:453dc852ac0f 43 }
dfrausto3 6:453dc852ac0f 44
dfrausto3 6:453dc852ac0f 45 LLNode* getHead(DLinkedList* dLinkedList){
dfrausto3 6:453dc852ac0f 46 return dLinkedList->head;
dfrausto3 6:453dc852ac0f 47 }
dfrausto3 6:453dc852ac0f 48
dfrausto3 6:453dc852ac0f 49 LLNode* getTail(DLinkedList* dLinkedList){
dfrausto3 6:453dc852ac0f 50 return dLinkedList->tail;
dfrausto3 6:453dc852ac0f 51 }
dfrausto3 6:453dc852ac0f 52
dfrausto3 6:453dc852ac0f 53 LLNode* getNext(LLNode* node){
dfrausto3 6:453dc852ac0f 54 return node->next;
dfrausto3 6:453dc852ac0f 55 }
dfrausto3 6:453dc852ac0f 56
dfrausto3 6:453dc852ac0f 57 LLNode* getPrev(LLNode* node){
dfrausto3 6:453dc852ac0f 58 return node->prev;
dfrausto3 6:453dc852ac0f 59 }
dfrausto3 6:453dc852ac0f 60
dfrausto3 6:453dc852ac0f 61 void* getData(LLNode* node){
dfrausto3 6:453dc852ac0f 62 return node->data;
dfrausto3 6:453dc852ac0f 63 }
dfrausto3 6:453dc852ac0f 64
dfrausto3 6:453dc852ac0f 65 //============================
dfrausto3 6:453dc852ac0f 66 /* Inserting nodes into lists */
dfrausto3 6:453dc852ac0f 67 //============================
dfrausto3 6:453dc852ac0f 68
dfrausto3 6:453dc852ac0f 69 void insertAfter(DLinkedList* dLinkedList, LLNode* prev_node, void* data){
dfrausto3 6:453dc852ac0f 70 LLNode* newNode = create_llnode(data); //Creates new Node
dfrausto3 6:453dc852ac0f 71 LLNode* nextNode = getNext(prev_node); //gets a pointer for the next node
dfrausto3 6:453dc852ac0f 72 if (prev_node != NULL) {
dfrausto3 6:453dc852ac0f 73 if (nextNode == NULL) { //if the node passed through is the tail then inserts the new node as the new tail
dfrausto3 6:453dc852ac0f 74 prev_node->next = newNode;
dfrausto3 6:453dc852ac0f 75 newNode->prev = prev_node;
dfrausto3 6:453dc852ac0f 76 dLinkedList->tail = newNode;
dfrausto3 6:453dc852ac0f 77 dLinkedList->size = dLinkedList->size + 1;
dfrausto3 6:453dc852ac0f 78 }
dfrausto3 6:453dc852ac0f 79 else { //if the node passed through is not the tail then inserts the new node after and updates surrounding nodes
dfrausto3 6:453dc852ac0f 80 newNode->next = nextNode;
dfrausto3 6:453dc852ac0f 81 nextNode->prev = newNode;
dfrausto3 6:453dc852ac0f 82 prev_node->next = newNode;
dfrausto3 6:453dc852ac0f 83 newNode->prev = prev_node;
dfrausto3 6:453dc852ac0f 84 dLinkedList->size = dLinkedList->size + 1;
dfrausto3 6:453dc852ac0f 85 }
dfrausto3 6:453dc852ac0f 86 }
dfrausto3 6:453dc852ac0f 87 else {
dfrausto3 6:453dc852ac0f 88 printf("ERROR: Node is Null\n");
dfrausto3 6:453dc852ac0f 89 }
dfrausto3 6:453dc852ac0f 90 }
dfrausto3 6:453dc852ac0f 91
dfrausto3 6:453dc852ac0f 92
dfrausto3 6:453dc852ac0f 93 void insertBefore(DLinkedList* dLinkedList, LLNode* prev_node, void* data){
dfrausto3 6:453dc852ac0f 94 LLNode* newNode = create_llnode(data); //Creates new node
dfrausto3 6:453dc852ac0f 95 LLNode* prevNode = getPrev(prev_node); //gets a pointer for the prev node
dfrausto3 6:453dc852ac0f 96 if (prev_node != NULL) {
dfrausto3 6:453dc852ac0f 97 if (prevNode == NULL) { // if the node passed through is the head then inserts the node as the new head
dfrausto3 6:453dc852ac0f 98 prev_node->prev = newNode;
dfrausto3 6:453dc852ac0f 99 newNode->next = prev_node;
dfrausto3 6:453dc852ac0f 100 dLinkedList->head = newNode;
dfrausto3 6:453dc852ac0f 101 dLinkedList->size = dLinkedList->size + 1;
dfrausto3 6:453dc852ac0f 102 }
dfrausto3 6:453dc852ac0f 103 else { //if the node passed through is not the head then inserts the new node before and updates surrounding nodes
dfrausto3 6:453dc852ac0f 104 newNode->prev = getPrev(prev_node);
dfrausto3 6:453dc852ac0f 105 prevNode->next = newNode;
dfrausto3 6:453dc852ac0f 106 prev_node->prev = newNode;
dfrausto3 6:453dc852ac0f 107 newNode->next = prev_node;
dfrausto3 6:453dc852ac0f 108 dLinkedList->size = dLinkedList->size + 1;
dfrausto3 6:453dc852ac0f 109 }
dfrausto3 6:453dc852ac0f 110 }
dfrausto3 6:453dc852ac0f 111 else {
dfrausto3 6:453dc852ac0f 112 printf("ERROR: Node is Null\n");
dfrausto3 6:453dc852ac0f 113 }
dfrausto3 6:453dc852ac0f 114 }
dfrausto3 6:453dc852ac0f 115
dfrausto3 6:453dc852ac0f 116
dfrausto3 6:453dc852ac0f 117 void insertHead(DLinkedList* dLinkedList, void* data){ //inserts data at the head
dfrausto3 6:453dc852ac0f 118 LLNode* newHead = create_llnode(data);
dfrausto3 6:453dc852ac0f 119 if (dLinkedList == NULL) { //if dLinkedList does not exist throws an error message
dfrausto3 6:453dc852ac0f 120 printf("Cant' do that");
dfrausto3 6:453dc852ac0f 121 return;
dfrausto3 6:453dc852ac0f 122 }
dfrausto3 6:453dc852ac0f 123 else if (dLinkedList->head == NULL) {
dfrausto3 6:453dc852ac0f 124 dLinkedList->head = newHead;
dfrausto3 6:453dc852ac0f 125 dLinkedList->tail = newHead;
dfrausto3 6:453dc852ac0f 126 dLinkedList->size = dLinkedList->size + 1;
dfrausto3 6:453dc852ac0f 127 }
dfrausto3 6:453dc852ac0f 128 else {
dfrausto3 6:453dc852ac0f 129 LLNode* oldHead = dLinkedList->head;
dfrausto3 6:453dc852ac0f 130 dLinkedList->head = newHead;
dfrausto3 6:453dc852ac0f 131 newHead->next = oldHead;
dfrausto3 6:453dc852ac0f 132 oldHead->prev = newHead;
dfrausto3 6:453dc852ac0f 133 dLinkedList->size = dLinkedList->size + 1;
dfrausto3 6:453dc852ac0f 134 }
dfrausto3 6:453dc852ac0f 135 }
dfrausto3 6:453dc852ac0f 136
dfrausto3 6:453dc852ac0f 137 void insertTail(DLinkedList* dLinkedList, void* data) { //if dLinkedList does not exist throws an error message
dfrausto3 6:453dc852ac0f 138 LLNode* newTail = create_llnode(data);
dfrausto3 6:453dc852ac0f 139 if (dLinkedList == NULL) {
dfrausto3 6:453dc852ac0f 140 printf("Cant' do that");
dfrausto3 6:453dc852ac0f 141 return;
dfrausto3 6:453dc852ac0f 142 }
dfrausto3 6:453dc852ac0f 143 else if (dLinkedList->head == NULL) {
dfrausto3 6:453dc852ac0f 144 dLinkedList->head = newTail;
dfrausto3 6:453dc852ac0f 145 dLinkedList->tail = newTail;
dfrausto3 6:453dc852ac0f 146 dLinkedList->size = dLinkedList->size + 1;
dfrausto3 6:453dc852ac0f 147 }
dfrausto3 6:453dc852ac0f 148 else {
dfrausto3 6:453dc852ac0f 149 LLNode* oldTail = dLinkedList->tail;
dfrausto3 6:453dc852ac0f 150 dLinkedList->tail = newTail;
dfrausto3 6:453dc852ac0f 151 newTail->prev = oldTail;
dfrausto3 6:453dc852ac0f 152 oldTail->next = newTail;
dfrausto3 6:453dc852ac0f 153 dLinkedList->size = dLinkedList->size + 1;
dfrausto3 6:453dc852ac0f 154 }
dfrausto3 6:453dc852ac0f 155
dfrausto3 6:453dc852ac0f 156 }
dfrausto3 6:453dc852ac0f 157
dfrausto3 6:453dc852ac0f 158 //============================
dfrausto3 6:453dc852ac0f 159 /* Looking up nodes in lists */
dfrausto3 6:453dc852ac0f 160 //============================
dfrausto3 6:453dc852ac0f 161
dfrausto3 6:453dc852ac0f 162 LLNode* findNode(DLinkedList* dLinkedList, void* data){
dfrausto3 6:453dc852ac0f 163 //LLNode* findNode = create_llnode(data);
dfrausto3 6:453dc852ac0f 164
dfrausto3 6:453dc852ac0f 165 LLNode* compNode = dLinkedList->head;
dfrausto3 6:453dc852ac0f 166 if (compNode == NULL) {
dfrausto3 6:453dc852ac0f 167 return NULL;
dfrausto3 6:453dc852ac0f 168 }
dfrausto3 6:453dc852ac0f 169 //runs through dLinkedList looking for data
dfrausto3 6:453dc852ac0f 170 int i;
dfrausto3 6:453dc852ac0f 171 for (i = 0; i < dLinkedList->size; i++) {
dfrausto3 6:453dc852ac0f 172 int j = dLinkedList->compare(compNode->data, data);
dfrausto3 6:453dc852ac0f 173 if (j == 1) {
dfrausto3 6:453dc852ac0f 174 return compNode;
dfrausto3 6:453dc852ac0f 175 }
dfrausto3 6:453dc852ac0f 176 else {
dfrausto3 6:453dc852ac0f 177 compNode = compNode->next;
dfrausto3 6:453dc852ac0f 178 }
dfrausto3 6:453dc852ac0f 179 }
dfrausto3 6:453dc852ac0f 180 return NULL;
dfrausto3 6:453dc852ac0f 181 }
dfrausto3 6:453dc852ac0f 182
dfrausto3 6:453dc852ac0f 183 //===========================
dfrausto3 6:453dc852ac0f 184 /* Deleting nodes and lists */
dfrausto3 6:453dc852ac0f 185 //===========================
dfrausto3 6:453dc852ac0f 186
dfrausto3 6:453dc852ac0f 187 void deleteNode(DLinkedList* dLinkedList, LLNode* Node){
dfrausto3 6:453dc852ac0f 188 if (Node != NULL){
dfrausto3 6:453dc852ac0f 189 LLNode* PrevNode = getPrev(Node);
dfrausto3 6:453dc852ac0f 190 LLNode* NextNode = getNext(Node);
dfrausto3 6:453dc852ac0f 191 if (PrevNode == NULL && NextNode != NULL) { //if head delets noed and updates the head of the list
dfrausto3 6:453dc852ac0f 192 dLinkedList->head = NextNode;
dfrausto3 6:453dc852ac0f 193 dLinkedList->size = dLinkedList->size - 1;
dfrausto3 6:453dc852ac0f 194 NextNode->prev = NULL;
dfrausto3 6:453dc852ac0f 195 }
dfrausto3 6:453dc852ac0f 196 else if (NextNode == NULL && PrevNode != NULL) { //if tail delets the node and updates the tail of the list
dfrausto3 6:453dc852ac0f 197 dLinkedList->tail = PrevNode;
dfrausto3 6:453dc852ac0f 198 dLinkedList->size = dLinkedList->size - 1;
dfrausto3 6:453dc852ac0f 199 PrevNode->next = NULL;
dfrausto3 6:453dc852ac0f 200 }
dfrausto3 6:453dc852ac0f 201 else if (PrevNode == NULL && NextNode == NULL) {
dfrausto3 6:453dc852ac0f 202 dLinkedList->tail = NULL;
dfrausto3 6:453dc852ac0f 203 dLinkedList->head = NULL;
dfrausto3 6:453dc852ac0f 204 dLinkedList->size = dLinkedList->size - 1;
dfrausto3 6:453dc852ac0f 205 }
dfrausto3 6:453dc852ac0f 206 else {
dfrausto3 6:453dc852ac0f 207 dLinkedList->size = dLinkedList->size - 1;
dfrausto3 6:453dc852ac0f 208 (Node->prev)->next = NextNode;
dfrausto3 6:453dc852ac0f 209 (Node->next)->prev = PrevNode;
dfrausto3 6:453dc852ac0f 210 }
dfrausto3 6:453dc852ac0f 211 }
dfrausto3 6:453dc852ac0f 212 //free(Node->data);
dfrausto3 6:453dc852ac0f 213 free(Node);
dfrausto3 6:453dc852ac0f 214 }
dfrausto3 6:453dc852ac0f 215
dfrausto3 6:453dc852ac0f 216
dfrausto3 6:453dc852ac0f 217 void destroyList(DLinkedList* dLinkedList){
dfrausto3 6:453dc852ac0f 218 LLNode* startNode = dLinkedList->head;
dfrausto3 6:453dc852ac0f 219 LLNode* nextNode;
dfrausto3 6:453dc852ac0f 220 if (startNode != NULL) {
dfrausto3 6:453dc852ac0f 221 nextNode = startNode->next;
dfrausto3 6:453dc852ac0f 222 }
dfrausto3 6:453dc852ac0f 223 int i;
dfrausto3 6:453dc852ac0f 224 for (i = 0; i < getSize(dLinkedList); i++) {
dfrausto3 6:453dc852ac0f 225 free(startNode->data);
dfrausto3 6:453dc852ac0f 226 free(startNode);
dfrausto3 6:453dc852ac0f 227 startNode = nextNode;
dfrausto3 6:453dc852ac0f 228 if (startNode != NULL) {
dfrausto3 6:453dc852ac0f 229 nextNode = startNode->next;
dfrausto3 6:453dc852ac0f 230 }
dfrausto3 6:453dc852ac0f 231 }
dfrausto3 6:453dc852ac0f 232 free(dLinkedList);
dfrausto3 6:453dc852ac0f 233 }
dfrausto3 6:453dc852ac0f 234
dfrausto3 6:453dc852ac0f 235 //==================
dfrausto3 6:453dc852ac0f 236 /* Reversing lists */
dfrausto3 6:453dc852ac0f 237 //==================
dfrausto3 6:453dc852ac0f 238 void reverse(DLinkedList* dLinkedList) {
dfrausto3 6:453dc852ac0f 239 if (dLinkedList->size > 1) {
dfrausto3 6:453dc852ac0f 240 LLNode* headNode = dLinkedList->head;
dfrausto3 6:453dc852ac0f 241 LLNode* tailNode = dLinkedList->tail;
dfrausto3 6:453dc852ac0f 242 LLNode* tempNode = dLinkedList->head;
dfrausto3 6:453dc852ac0f 243 int i = 0;
dfrausto3 6:453dc852ac0f 244 dLinkedList->head = tailNode;
dfrausto3 6:453dc852ac0f 245 dLinkedList->tail = headNode;
dfrausto3 6:453dc852ac0f 246 while (i < dLinkedList->size) {
dfrausto3 6:453dc852ac0f 247 headNode->prev = headNode->next;
dfrausto3 6:453dc852ac0f 248 tempNode = headNode->prev;
dfrausto3 6:453dc852ac0f 249 headNode = tempNode;
dfrausto3 6:453dc852ac0f 250 i++;
dfrausto3 6:453dc852ac0f 251 }
dfrausto3 6:453dc852ac0f 252
dfrausto3 6:453dc852ac0f 253
dfrausto3 6:453dc852ac0f 254 }
dfrausto3 6:453dc852ac0f 255 }