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?
User | Revision | Line number | New 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 | } |