Robbie Huey / Mbed 2 deprecated baseline

baseline features - a little buggy

Dependencies:   mbed wave_player 4DGL-uLCD-SE MMA8452

doubly_linked_list.cpp@2:cf4e61c051a4, 2021-04-10 (annotated)

Committer:
robbiehuey
Date:
Sat Apr 10 02:08:02 2021 +0000
Revision:
2:cf4e61c051a4
Parent:
1:4421c1e849e9 
hi

Who changed what in which revision?

UserRevisionLine numberNew contents of line
DCchico 0:95264f964374 1 //=================================================================
DCchico 0:95264f964374 2 // Implementation for DLL module.
DCchico 0:95264f964374 3 //
DCchico 0:95264f964374 4 // Copyright 2021 Georgia Tech. All rights reserved.
DCchico 0:95264f964374 5 // The materials provided by the instructor in this course are for
DCchico 0:95264f964374 6 // the use of the students currently enrolled in the course.
DCchico 0:95264f964374 7 // Copyrighted course materials may not be further disseminated.
DCchico 0:95264f964374 8 // This file must not be made publicly available anywhere.
DCchico 0:95264f964374 9 //=================================================================
DCchico 0:95264f964374 10 #include <stdlib.h>
DCchico 0:95264f964374 11 #include <stdio.h>
DCchico 0:95264f964374 12 #include "doubly_linked_list.h"
DCchico 0:95264f964374 13
DCchico 0:95264f964374 14 LLNode* create_llnode(void* data) {
robbiehuey 1:4421c1e849e9 15 LLNode* node = (LLNode*)malloc(sizeof(LLNode));
robbiehuey 1:4421c1e849e9 16 node -> prev = NULL;
robbiehuey 1:4421c1e849e9 17 node -> next = NULL;
robbiehuey 1:4421c1e849e9 18 node -> data = data;
robbiehuey 1:4421c1e849e9 19 return node;
robbiehuey 1:4421c1e849e9 20 }
DCchico 0:95264f964374 21
DCchico 0:95264f964374 22
DCchico 0:95264f964374 23 DLinkedList* create_dlinkedlist(void) {
DCchico 0:95264f964374 24 DLinkedList* newList = (DLinkedList*)malloc(sizeof(DLinkedList));
DCchico 0:95264f964374 25 newList->head = NULL;
DCchico 0:95264f964374 26 newList->tail = NULL;
DCchico 0:95264f964374 27 newList->size = 0;
DCchico 0:95264f964374 28 return newList;
DCchico 0:95264f964374 29 }
DCchico 0:95264f964374 30
DCchico 0:95264f964374 31 int getSize(DLinkedList* dLinkedList){
robbiehuey 1:4421c1e849e9 32 return dLinkedList -> size;
DCchico 0:95264f964374 33 }
DCchico 0:95264f964374 34
DCchico 0:95264f964374 35 LLNode* getHead(DLinkedList* dLinkedList){
robbiehuey 1:4421c1e849e9 36 return dLinkedList -> head;
DCchico 0:95264f964374 37 }
DCchico 0:95264f964374 38
DCchico 0:95264f964374 39 LLNode* getTail(DLinkedList* dLinkedList){
robbiehuey 1:4421c1e849e9 40 return dLinkedList -> tail;
DCchico 0:95264f964374 41 }
DCchico 0:95264f964374 42
DCchico 0:95264f964374 43 LLNode* getNext(LLNode* node){
robbiehuey 1:4421c1e849e9 44 return node -> next;
DCchico 0:95264f964374 45 }
DCchico 0:95264f964374 46
DCchico 0:95264f964374 47 LLNode* getPrev(LLNode* node){
robbiehuey 1:4421c1e849e9 48 return node -> prev;
DCchico 0:95264f964374 49 }
DCchico 0:95264f964374 50
DCchico 0:95264f964374 51 void* getData(LLNode* node){
robbiehuey 1:4421c1e849e9 52 return node -> data;
DCchico 0:95264f964374 53 }
DCchico 0:95264f964374 54
DCchico 0:95264f964374 55 void insertAfter(DLinkedList* dLinkedList, LLNode* prev_node, void* data){
DCchico 0:95264f964374 56 if (prev_node == NULL) {
DCchico 0:95264f964374 57 printf("the given previous node cannot be NULL");
DCchico 0:95264f964374 58 return;
DCchico 0:95264f964374 59 }
robbiehuey 1:4421c1e849e9 60 LLNode* newNode = create_llnode(data); //creates new node
robbiehuey 1:4421c1e849e9 61 LLNode* nextNode = prev_node -> next; //creates next for new node
robbiehuey 1:4421c1e849e9 62 //previous node is passed as argument
robbiehuey 1:4421c1e849e9 63 if (nextNode != NULL) { //if prev_node is not the tail...
robbiehuey 1:4421c1e849e9 64 newNode -> next = nextNode; //update next of new node
robbiehuey 1:4421c1e849e9 65 nextNode -> prev = newNode; //update prev of next_node
robbiehuey 1:4421c1e849e9 66 } else { //if prev_node is the tail
robbiehuey 1:4421c1e849e9 67 dLinkedList -> tail = newNode; //update tail of linked list
robbiehuey 1:4421c1e849e9 68 } // execute no matter what
robbiehuey 1:4421c1e849e9 69 newNode -> prev = prev_node; //update prev of new node
robbiehuey 1:4421c1e849e9 70 prev_node -> next = newNode; //update next of prev_node
robbiehuey 1:4421c1e849e9 71 (dLinkedList -> size)++; //update size of linked list
DCchico 0:95264f964374 72 return;
DCchico 0:95264f964374 73 }
DCchico 0:95264f964374 74
DCchico 0:95264f964374 75 void insertBefore(DLinkedList* dLinkedList, LLNode* next_node, void* data){
DCchico 0:95264f964374 76 if (next_node == NULL) {
DCchico 0:95264f964374 77 printf("the given next node cannot be NULL");
DCchico 0:95264f964374 78 return;
DCchico 0:95264f964374 79 }
robbiehuey 1:4421c1e849e9 80 LLNode* newNode = create_llnode(data); //creates new node
robbiehuey 1:4421c1e849e9 81 LLNode* prevNode = next_node -> prev; //creates prev for new node
robbiehuey 1:4421c1e849e9 82 //next node is passed as argument
robbiehuey 1:4421c1e849e9 83 if (prevNode != NULL) { //if next_node is not the head...
robbiehuey 1:4421c1e849e9 84 newNode -> prev = prevNode; //update prev of new node
robbiehuey 1:4421c1e849e9 85 prevNode -> next = newNode; //update next of prev node
robbiehuey 1:4421c1e849e9 86 } else { //if next_node is the head
robbiehuey 1:4421c1e849e9 87 dLinkedList -> head = newNode; //update head of linked list
robbiehuey 1:4421c1e849e9 88 } // execute no matter what
robbiehuey 1:4421c1e849e9 89 newNode -> next = next_node; //update next of new node
robbiehuey 1:4421c1e849e9 90 next_node -> prev = newNode; //update prev of next_node
robbiehuey 1:4421c1e849e9 91 (dLinkedList -> size)++; //update size of linked list
DCchico 0:95264f964374 92 return;
DCchico 0:95264f964374 93 }
DCchico 0:95264f964374 94
robbiehuey 1:4421c1e849e9 95 void insertHead(DLinkedList* dLinkedList, void* data) {
robbiehuey 1:4421c1e849e9 96 if (dLinkedList -> head == NULL) {
DCchico 0:95264f964374 97 LLNode* newNode = create_llnode(data);
robbiehuey 1:4421c1e849e9 98 dLinkedList -> head = newNode;
robbiehuey 1:4421c1e849e9 99 dLinkedList -> tail = newNode;
robbiehuey 1:4421c1e849e9 100 (dLinkedList -> size)++;
robbiehuey 1:4421c1e849e9 101 } else {
robbiehuey 1:4421c1e849e9 102 insertBefore(dLinkedList, dLinkedList -> head, data);
robbiehuey 1:4421c1e849e9 103 }
robbiehuey 1:4421c1e849e9 104 }
robbiehuey 1:4421c1e849e9 105
robbiehuey 1:4421c1e849e9 106 void insertTail(DLinkedList* dLinkedList, void* data) {
robbiehuey 1:4421c1e849e9 107 if (dLinkedList -> head == NULL ){
robbiehuey 1:4421c1e849e9 108 LLNode* newNode = create_llnode(data);
robbiehuey 1:4421c1e849e9 109 dLinkedList -> head = newNode;
robbiehuey 1:4421c1e849e9 110 dLinkedList -> tail = newNode;
robbiehuey 1:4421c1e849e9 111 (dLinkedList -> size)++;
robbiehuey 1:4421c1e849e9 112 } else {
robbiehuey 1:4421c1e849e9 113 insertAfter(dLinkedList, dLinkedList->tail, data);
DCchico 0:95264f964374 114 }
DCchico 0:95264f964374 115 }
DCchico 0:95264f964374 116
DCchico 0:95264f964374 117 void deleteNode(DLinkedList* dLinkedList, LLNode* Node){
robbiehuey 1:4421c1e849e9 118 //LLNode* prevNode = Node -> prev;
robbiehuey 1:4421c1e849e9 119 //LLNode* nextNode = Node -> next;
robbiehuey 1:4421c1e849e9 120 if (dLinkedList -> size == 1){
robbiehuey 1:4421c1e849e9 121 free(Node->data);
robbiehuey 1:4421c1e849e9 122 free(Node);
robbiehuey 1:4421c1e849e9 123 (dLinkedList->size)--;
robbiehuey 1:4421c1e849e9 124 return;
robbiehuey 1:4421c1e849e9 125 }
robbiehuey 1:4421c1e849e9 126 if (dLinkedList -> head == Node) {
robbiehuey 1:4421c1e849e9 127 Node -> next -> prev = NULL;
robbiehuey 1:4421c1e849e9 128 dLinkedList -> head = Node -> next;
robbiehuey 1:4421c1e849e9 129 } else if (dLinkedList -> tail == Node) {
robbiehuey 1:4421c1e849e9 130 Node -> prev -> next = NULL;
robbiehuey 1:4421c1e849e9 131 dLinkedList -> tail = Node -> prev;
robbiehuey 1:4421c1e849e9 132 } else {
robbiehuey 1:4421c1e849e9 133 Node -> prev -> next = Node -> next;
robbiehuey 1:4421c1e849e9 134 Node -> next -> prev = Node -> prev;
robbiehuey 1:4421c1e849e9 135 }
robbiehuey 1:4421c1e849e9 136 (dLinkedList -> size)--;
robbiehuey 1:4421c1e849e9 137 free(Node -> data);
robbiehuey 1:4421c1e849e9 138 free(Node);
robbiehuey 1:4421c1e849e9 139 return;
DCchico 0:95264f964374 140 }
DCchico 0:95264f964374 141
DCchico 0:95264f964374 142 void destroyList(DLinkedList* dLinkedList){
robbiehuey 1:4421c1e849e9 143 if ((dLinkedList -> size) == 1) {
robbiehuey 1:4421c1e849e9 144 deleteNode(dLinkedList, dLinkedList -> head);
robbiehuey 1:4421c1e849e9 145 free(dLinkedList);
robbiehuey 1:4421c1e849e9 146 return;
robbiehuey 1:4421c1e849e9 147 }
robbiehuey 1:4421c1e849e9 148 LLNode* curr = dLinkedList -> head;
robbiehuey 1:4421c1e849e9 149 if (curr == NULL) {
robbiehuey 1:4421c1e849e9 150 free(dLinkedList);
robbiehuey 1:4421c1e849e9 151 return;
robbiehuey 1:4421c1e849e9 152 }
robbiehuey 1:4421c1e849e9 153 LLNode* next = curr -> next;
robbiehuey 1:4421c1e849e9 154 while (next != NULL) {
robbiehuey 1:4421c1e849e9 155 deleteNode(dLinkedList, curr);
robbiehuey 1:4421c1e849e9 156 curr = next;
robbiehuey 1:4421c1e849e9 157 next = curr -> next;
robbiehuey 1:4421c1e849e9 158 }
robbiehuey 1:4421c1e849e9 159 free(dLinkedList);
robbiehuey 1:4421c1e849e9 160 return;
DCchico 0:95264f964374 161 }
DCchico 0:95264f964374 162
robbiehuey 1:4421c1e849e9 163 void reverse(DLinkedList* dLinkedList){
robbiehuey 1:4421c1e849e9 164 if (dLinkedList -> size <= 1){
robbiehuey 1:4421c1e849e9 165 return;
robbiehuey 1:4421c1e849e9 166 }
robbiehuey 1:4421c1e849e9 167 LLNode* curr = dLinkedList -> head;
robbiehuey 1:4421c1e849e9 168 LLNode* start = dLinkedList -> head;
robbiehuey 1:4421c1e849e9 169 LLNode* dummy;
robbiehuey 1:4421c1e849e9 170 while (curr != NULL){
robbiehuey 1:4421c1e849e9 171 dummy = curr -> prev;
robbiehuey 1:4421c1e849e9 172 curr -> prev = curr -> next;
robbiehuey 1:4421c1e849e9 173 curr -> next = dummy;
robbiehuey 1:4421c1e849e9 174 curr = curr -> prev;
robbiehuey 1:4421c1e849e9 175 }
robbiehuey 1:4421c1e849e9 176 dLinkedList -> head = dLinkedList -> tail;
robbiehuey 1:4421c1e849e9 177 dLinkedList -> tail = start;
robbiehuey 1:4421c1e849e9 178 return;
robbiehuey 1:4421c1e849e9 179 }