Robbie Huey / Mbed 2 deprecated baseline

baseline features - a little buggy

Dependencies:   mbed wave_player 4DGL-uLCD-SE MMA8452

doubly_linked_list.h@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 // Header file for DLL module.
DCchico 0:95264f964374 3 //
robbiehuey 1:4421c1e849e9 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
DCchico 0:95264f964374 11 #ifndef DOUBLELINKEDLIST_H
DCchico 0:95264f964374 12 #define DOUBLELINKEDLIST_H
DCchico 0:95264f964374 13
DCchico 0:95264f964374 14 // A linked list node structure.
DCchico 0:95264f964374 15 typedef struct llnode_t {
DCchico 0:95264f964374 16 void* data;
DCchico 0:95264f964374 17 struct llnode_t* prev;
DCchico 0:95264f964374 18 struct llnode_t* next;
DCchico 0:95264f964374 19 }LLNode;
DCchico 0:95264f964374 20
DCchico 0:95264f964374 21 /// The structure to store the information of a doubly linked list
DCchico 0:95264f964374 22 typedef struct dlinkedlist_t {
DCchico 0:95264f964374 23 struct llnode_t* head;
DCchico 0:95264f964374 24 struct llnode_t* tail;
DCchico 0:95264f964374 25 int size;
DCchico 0:95264f964374 26 } DLinkedList;
DCchico 0:95264f964374 27
robbiehuey 1:4421c1e849e9 28 //===========================
robbiehuey 1:4421c1e849e9 29 /* Creating nodes and lists */
robbiehuey 1:4421c1e849e9 30 //===========================
DCchico 0:95264f964374 31
DCchico 0:95264f964374 32 /**
DCchico 0:95264f964374 33 * create_llnode
DCchico 0:95264f964374 34 *
DCchico 0:95264f964374 35 * Creates a node by allocating memory for it on the heap,
robbiehuey 1:4421c1e849e9 36 * and initializing its previous and next pointers to NULL and its data
robbiehuey 1:4421c1e849e9 37 * pointer to the input data pointer
DCchico 0:95264f964374 38 *
robbiehuey 1:4421c1e849e9 39 * @param data A void pointer to data the user is adding to the doubly linked list.
DCchico 0:95264f964374 40 * @return A pointer to the linked list node
DCchico 0:95264f964374 41 */
DCchico 0:95264f964374 42 LLNode* create_llnode(void* data);
DCchico 0:95264f964374 43
DCchico 0:95264f964374 44 /**
DCchico 0:95264f964374 45 * create_dlinkedlist
DCchico 0:95264f964374 46 *
robbiehuey 1:4421c1e849e9 47 * Creates a doubly linked list by allocating memory for it on the heap.
robbiehuey 1:4421c1e849e9 48 * Initialize the size to zero, as well as head and tail pointers to NULL.
DCchico 0:95264f964374 49 *
DCchico 0:95264f964374 50 * @return A pointer to an empty dlinkedlist
DCchico 0:95264f964374 51 */
DCchico 0:95264f964374 52 DLinkedList* create_dlinkedlist(void);
DCchico 0:95264f964374 53
robbiehuey 1:4421c1e849e9 54 //============================
robbiehuey 1:4421c1e849e9 55 /* Accessing nodes and lists */
robbiehuey 1:4421c1e849e9 56 //============================
DCchico 0:95264f964374 57
DCchico 0:95264f964374 58 /**
DCchico 0:95264f964374 59 * getSize
DCchico 0:95264f964374 60 *
DCchico 0:95264f964374 61 * Return the size of the doubly linked list
DCchico 0:95264f964374 62 *
DCchico 0:95264f964374 63 * @param dLinkedList A pointer to the doubly linked list
DCchico 0:95264f964374 64 * @return the size
DCchico 0:95264f964374 65 */
DCchico 0:95264f964374 66 int getSize(DLinkedList* dLinkedList);
robbiehuey 1:4421c1e849e9 67
robbiehuey 1:4421c1e849e9 68 /**
robbiehuey 1:4421c1e849e9 69 * getHead
robbiehuey 1:4421c1e849e9 70 *
robbiehuey 1:4421c1e849e9 71 * Return the head of the doubly linked list
robbiehuey 1:4421c1e849e9 72 *
robbiehuey 1:4421c1e849e9 73 * @param dLinkedList A pointer to the doubly linked list
robbiehuey 1:4421c1e849e9 74 * @return A pointer to an LLNode
robbiehuey 1:4421c1e849e9 75 */
robbiehuey 1:4421c1e849e9 76 LLNode* getHead(DLinkedList* dLinkedList);
robbiehuey 1:4421c1e849e9 77
robbiehuey 1:4421c1e849e9 78 /**
robbiehuey 1:4421c1e849e9 79 * getTail
robbiehuey 1:4421c1e849e9 80 *
robbiehuey 1:4421c1e849e9 81 * Return the tail of the doubly linked list
robbiehuey 1:4421c1e849e9 82 *
robbiehuey 1:4421c1e849e9 83 * @param dLinkedList A pointer to the doubly linked list
robbiehuey 1:4421c1e849e9 84 * @return A pointer to an LLNode
robbiehuey 1:4421c1e849e9 85 */
robbiehuey 1:4421c1e849e9 86 LLNode* getTail(DLinkedList* dLinkedList);
robbiehuey 1:4421c1e849e9 87
robbiehuey 1:4421c1e849e9 88 /**
robbiehuey 1:4421c1e849e9 89 * getNext
robbiehuey 1:4421c1e849e9 90 *
robbiehuey 1:4421c1e849e9 91 * Return the next node after the input node.
robbiehuey 1:4421c1e849e9 92 *
robbiehuey 1:4421c1e849e9 93 * @param node A pointer to an LLNode
robbiehuey 1:4421c1e849e9 94 * @return A pointer to an LLNode
robbiehuey 1:4421c1e849e9 95 */
robbiehuey 1:4421c1e849e9 96 LLNode* getNext(LLNode* node);
robbiehuey 1:4421c1e849e9 97
robbiehuey 1:4421c1e849e9 98 /**
robbiehuey 1:4421c1e849e9 99 * getPrev
robbiehuey 1:4421c1e849e9 100 *
robbiehuey 1:4421c1e849e9 101 * Return the previous node before the input node.
robbiehuey 1:4421c1e849e9 102 *
robbiehuey 1:4421c1e849e9 103 * @param node A pointer to an LLNode
robbiehuey 1:4421c1e849e9 104 * @return A pointer to an LLNode
robbiehuey 1:4421c1e849e9 105 */
robbiehuey 1:4421c1e849e9 106 LLNode* getPrev(LLNode* node);
robbiehuey 1:4421c1e849e9 107
robbiehuey 1:4421c1e849e9 108 /**
robbiehuey 1:4421c1e849e9 109 * getData
robbiehuey 1:4421c1e849e9 110 *
robbiehuey 1:4421c1e849e9 111 * Return the input node's data.
robbiehuey 1:4421c1e849e9 112 *
robbiehuey 1:4421c1e849e9 113 * @param node A pointer to an LLNode
robbiehuey 1:4421c1e849e9 114 * @return A void pointer to the node's data.
robbiehuey 1:4421c1e849e9 115 */
robbiehuey 1:4421c1e849e9 116 void* getData(LLNode* node);
robbiehuey 1:4421c1e849e9 117
robbiehuey 1:4421c1e849e9 118 //============================
robbiehuey 1:4421c1e849e9 119 /* Inserting nodes into lists */
robbiehuey 1:4421c1e849e9 120 //============================
robbiehuey 1:4421c1e849e9 121
robbiehuey 1:4421c1e849e9 122 /**
robbiehuey 1:4421c1e849e9 123 * insertAfter
robbiehuey 1:4421c1e849e9 124 *
robbiehuey 1:4421c1e849e9 125 * Insert data after the prev_node. Update head/tail/size if necessary.
robbiehuey 1:4421c1e849e9 126 * Assumes prev_node is not NULL and is in dLinkedList. (Check if it is NULL and if so, print an error
robbiehuey 1:4421c1e849e9 127 * message and return.)
robbiehuey 1:4421c1e849e9 128 *
robbiehuey 1:4421c1e849e9 129 * @param dLinkedList A pointer to the doubly linked list
robbiehuey 1:4421c1e849e9 130 * @param prev_node A pointer to a linked list node.
robbiehuey 1:4421c1e849e9 131 * @param data A void pointer to data.
robbiehuey 1:4421c1e849e9 132 */
robbiehuey 1:4421c1e849e9 133 void insertAfter(DLinkedList* dLinkedList, LLNode* prev_node, void* data);
robbiehuey 1:4421c1e849e9 134
robbiehuey 1:4421c1e849e9 135 /**
robbiehuey 1:4421c1e849e9 136 * insertBefore
robbiehuey 1:4421c1e849e9 137 *
robbiehuey 1:4421c1e849e9 138 * Insert data before the next_node. Update head/tail/size if necessary.
robbiehuey 1:4421c1e849e9 139 * Assumes prev_node is not NULL and is in dLinkedList. (Check if it is NULL and if so, print an error
robbiehuey 1:4421c1e849e9 140 * message and return.)
robbiehuey 1:4421c1e849e9 141 * Update the size.
robbiehuey 1:4421c1e849e9 142 *
robbiehuey 1:4421c1e849e9 143 * @param dLinkedList A pointer to the doubly linked list
robbiehuey 1:4421c1e849e9 144 * @param next_node A pointer to a linked list node.
robbiehuey 1:4421c1e849e9 145 * @param data A void pointer to data.
robbiehuey 1:4421c1e849e9 146 */
robbiehuey 1:4421c1e849e9 147 void insertBefore(DLinkedList* dLinkedList, LLNode* next_node, void* data);
robbiehuey 1:4421c1e849e9 148
robbiehuey 1:4421c1e849e9 149 /**
robbiehuey 1:4421c1e849e9 150 * insertHead
robbiehuey 1:4421c1e849e9 151 *
robbiehuey 1:4421c1e849e9 152 * Create a new LLNode with the given data and insert it at the head of the
robbiehuey 1:4421c1e849e9 153 * doubly linked list. Update head/tail/size if necessary.
robbiehuey 1:4421c1e849e9 154 * Note: The case where dLinkedList is not empty can be implemented by calling
robbiehuey 1:4421c1e849e9 155 * insertBefore with the head of the list as the next_node.
robbiehuey 1:4421c1e849e9 156 *
robbiehuey 1:4421c1e849e9 157 * @param dLinkedList A pointer to the doubly linked list
robbiehuey 1:4421c1e849e9 158 * @param data A void pointer to data the user is adding to the doubly linked list.
robbiehuey 1:4421c1e849e9 159 *
robbiehuey 1:4421c1e849e9 160 */
robbiehuey 1:4421c1e849e9 161 void insertHead(DLinkedList* dLinkedList, void* data);
robbiehuey 1:4421c1e849e9 162
robbiehuey 1:4421c1e849e9 163 /**
robbiehuey 1:4421c1e849e9 164 * insertTail
robbiehuey 1:4421c1e849e9 165 *
robbiehuey 1:4421c1e849e9 166 * Create a new LLNode with the given data and insert it at the tail of the
robbiehuey 1:4421c1e849e9 167 * doubly linked list. Update head/tail/size if necessary.
robbiehuey 1:4421c1e849e9 168 * Note: The case where dLinkedList is not empty can be implemented by calling
robbiehuey 1:4421c1e849e9 169 * insertAfter with the tail of the list as the next_node.
robbiehuey 1:4421c1e849e9 170 *
robbiehuey 1:4421c1e849e9 171 * @param dLinkedList A pointer to the doubly linked list
robbiehuey 1:4421c1e849e9 172 * @param data A void pointer to data the user is adding to the doubly linked list.
robbiehuey 1:4421c1e849e9 173 *
robbiehuey 1:4421c1e849e9 174 */
robbiehuey 1:4421c1e849e9 175 void insertTail(DLinkedList* dLinkedList, void* data);
robbiehuey 1:4421c1e849e9 176
robbiehuey 1:4421c1e849e9 177 //===========================
robbiehuey 1:4421c1e849e9 178 /* Deleting nodes and lists */
robbiehuey 1:4421c1e849e9 179 //===========================
robbiehuey 1:4421c1e849e9 180
robbiehuey 1:4421c1e849e9 181 /**
robbiehuey 1:4421c1e849e9 182 * deleteNode
robbiehuey 1:4421c1e849e9 183 *
robbiehuey 1:4421c1e849e9 184 * Delete the node pointed to by Node (splice it out).
robbiehuey 1:4421c1e849e9 185 * Update head/tail/size if necessary.
robbiehuey 1:4421c1e849e9 186 * Free the Node's data as well as the Node.
robbiehuey 1:4421c1e849e9 187 * Assumes Node is not NULL and is in dLinkedList.
robbiehuey 1:4421c1e849e9 188 *
robbiehuey 1:4421c1e849e9 189 * @param dLinkedList A pointer to the doubly linked list
robbiehuey 1:4421c1e849e9 190 * @param Node A pointer to a linked list node.
robbiehuey 1:4421c1e849e9 191 */
robbiehuey 1:4421c1e849e9 192
robbiehuey 1:4421c1e849e9 193 void deleteNode(DLinkedList* dLinkedList, LLNode* Node);
robbiehuey 1:4421c1e849e9 194
robbiehuey 1:4421c1e849e9 195 /**
robbiehuey 1:4421c1e849e9 196 * destroyList
robbiehuey 1:4421c1e849e9 197 *
robbiehuey 1:4421c1e849e9 198 * Destroy the doubly linked list. Everything in the doubly linked list,
robbiehuey 1:4421c1e849e9 199 * including list structure, nodes and data, are all freed from the heap.
robbiehuey 1:4421c1e849e9 200 *
robbiehuey 1:4421c1e849e9 201 * @param dLinkedList A pointer to the doubly linked list
robbiehuey 1:4421c1e849e9 202 *
robbiehuey 1:4421c1e849e9 203 */
robbiehuey 1:4421c1e849e9 204 void destroyList(DLinkedList* dLinkedList);
robbiehuey 1:4421c1e849e9 205
robbiehuey 1:4421c1e849e9 206 //==================
robbiehuey 1:4421c1e849e9 207 /* Reversing lists */
robbiehuey 1:4421c1e849e9 208 //==================
robbiehuey 1:4421c1e849e9 209
robbiehuey 1:4421c1e849e9 210 /**
robbiehuey 1:4421c1e849e9 211 * reverse
robbiehuey 1:4421c1e849e9 212 *
robbiehuey 1:4421c1e849e9 213 * Reverse the order of the doubly linked list.
robbiehuey 1:4421c1e849e9 214 * Update head/tail if necessary.
robbiehuey 1:4421c1e849e9 215 * This should not create a new list (it should rewire the nodes in dLinkedList).
robbiehuey 1:4421c1e849e9 216
robbiehuey 1:4421c1e849e9 217 *
robbiehuey 1:4421c1e849e9 218 * @param dLinkedList A pointer to the doubly linked list
robbiehuey 1:4421c1e849e9 219 *
robbiehuey 1:4421c1e849e9 220 */
robbiehuey 1:4421c1e849e9 221 void reverse(DLinkedList* dLinkedList);
robbiehuey 1:4421c1e849e9 222
DCchico 0:95264f964374 223 #endif