Kevin Abraham / Mbed 2 deprecated MazeRunner_Fall2017

ECE 2036 Project

Dependencies:   mbed wave_player 4DGL-uLCD-SE

doublely_linked_list.h@2:2042f29de6b7, 2019-11-21 (annotated)

Committer:
abraha2d
Date:
Thu Nov 21 16:10:57 2019 +0000
Revision:
2:2042f29de6b7
Parent:
0:cf4396614a79 
Because other peeps is wanting dis...

Who changed what in which revision?

UserRevisionLine numberNew contents of line
rconnorlawson 0:cf4396614a79 1 /** @file doublely_linked_list.h */
rconnorlawson 0:cf4396614a79 2 #ifndef DOUBLELINKEDLIST_H
rconnorlawson 0:cf4396614a79 3 #define DOUBLELINKEDLIST_H
rconnorlawson 0:cf4396614a79 4
rconnorlawson 0:cf4396614a79 5
rconnorlawson 0:cf4396614a79 6 /********************************************
rconnorlawson 0:cf4396614a79 7 * Doublely Linked List library functions *
rconnorlawson 0:cf4396614a79 8 * For more details on their functionality, *
rconnorlawson 0:cf4396614a79 9 * see the documentation in doublely_linked_list.c *
rconnorlawson 0:cf4396614a79 10 ********************************************/
rconnorlawson 0:cf4396614a79 11
rconnorlawson 0:cf4396614a79 12
rconnorlawson 0:cf4396614a79 13 /**
rconnorlawson 0:cf4396614a79 14 * This structure represents an entire linked list.
rconnorlawson 0:cf4396614a79 15 */
rconnorlawson 0:cf4396614a79 16 typedef struct dlinkedlist_t {
rconnorlawson 0:cf4396614a79 17 /** The head pointer for the list (points to the first node) */
rconnorlawson 0:cf4396614a79 18 struct llnode_t* head;
rconnorlawson 0:cf4396614a79 19
rconnorlawson 0:cf4396614a79 20 /** The tail pointer for the list (points to the last node) */
rconnorlawson 0:cf4396614a79 21 struct llnode_t* tail;
rconnorlawson 0:cf4396614a79 22
rconnorlawson 0:cf4396614a79 23 /** The current pointer for the list (points to the current node) */
rconnorlawson 0:cf4396614a79 24 struct llnode_t* current;
rconnorlawson 0:cf4396614a79 25
rconnorlawson 0:cf4396614a79 26 /** The number of nodes in the list */
rconnorlawson 0:cf4396614a79 27 int size;
rconnorlawson 0:cf4396614a79 28 } DLinkedList;
rconnorlawson 0:cf4396614a79 29
rconnorlawson 0:cf4396614a79 30 /**
rconnorlawson 0:cf4396614a79 31 * This structure represents a single list node.
rconnorlawson 0:cf4396614a79 32 */
rconnorlawson 0:cf4396614a79 33 typedef struct llnode_t {
rconnorlawson 0:cf4396614a79 34 /** The data associated with this node */
rconnorlawson 0:cf4396614a79 35 void* data;
rconnorlawson 0:cf4396614a79 36
rconnorlawson 0:cf4396614a79 37 /** A pointer to the previous node in the list. NULL if there is no previous node. */
rconnorlawson 0:cf4396614a79 38 struct llnode_t* previous;
rconnorlawson 0:cf4396614a79 39
rconnorlawson 0:cf4396614a79 40 /** A pointer to the next node in the list. NULL if there is no next node. */
rconnorlawson 0:cf4396614a79 41 struct llnode_t* next;
rconnorlawson 0:cf4396614a79 42 } LLNode;
rconnorlawson 0:cf4396614a79 43
rconnorlawson 0:cf4396614a79 44
rconnorlawson 0:cf4396614a79 45 /**
rconnorlawson 0:cf4396614a79 46 * create_dlinkedlist
rconnorlawson 0:cf4396614a79 47 *
rconnorlawson 0:cf4396614a79 48 * Creates a doublely liked list by allocating memory for it on the heap. Initialize the size to zero,
rconnorlawson 0:cf4396614a79 49 * as well as head, current, and tail pointer to NULL
rconnorlawson 0:cf4396614a79 50 *
rconnorlawson 0:cf4396614a79 51 * @return A pointer to an empty dlinkedlist
rconnorlawson 0:cf4396614a79 52 */
rconnorlawson 0:cf4396614a79 53 DLinkedList* create_dlinkedlist(void);
rconnorlawson 0:cf4396614a79 54
rconnorlawson 0:cf4396614a79 55 /**
rconnorlawson 0:cf4396614a79 56 * create_llnode
rconnorlawson 0:cf4396614a79 57 *
rconnorlawson 0:cf4396614a79 58 * Helper function that creates a node by allocating memory for it on the heap,
rconnorlawson 0:cf4396614a79 59 * and initializing its previous and next pointers to NULL and its data pointer to the input
rconnorlawson 0:cf4396614a79 60 * data pointer
rconnorlawson 0:cf4396614a79 61 *
rconnorlawson 0:cf4396614a79 62 * @param data A void pointer to data the user is adding to the doublely linked list.
rconnorlawson 0:cf4396614a79 63 * @return A pointer to the linked list node
rconnorlawson 0:cf4396614a79 64 */
rconnorlawson 0:cf4396614a79 65 LLNode* create_llnode(void* data);
rconnorlawson 0:cf4396614a79 66
rconnorlawson 0:cf4396614a79 67
rconnorlawson 0:cf4396614a79 68 /**
rconnorlawson 0:cf4396614a79 69 * InsertHead
rconnorlawson 0:cf4396614a79 70 *
rconnorlawson 0:cf4396614a79 71 * Insert the data to the head of the doublely linked list.
rconnorlawson 0:cf4396614a79 72 * Do not update the current node.
rconnorlawson 0:cf4396614a79 73 *
rconnorlawson 0:cf4396614a79 74 * @param dLinkedList A pointer to the doublely linked list
rconnorlawson 0:cf4396614a79 75 * @param data A void pointer to data the user is adding to the doublely linked list.
rconnorlawson 0:cf4396614a79 76 *
rconnorlawson 0:cf4396614a79 77 */
rconnorlawson 0:cf4396614a79 78 void insertHead(DLinkedList* dLinkedList, void* data);
rconnorlawson 0:cf4396614a79 79
rconnorlawson 0:cf4396614a79 80
rconnorlawson 0:cf4396614a79 81 /**
rconnorlawson 0:cf4396614a79 82 * insertTail
rconnorlawson 0:cf4396614a79 83 *
rconnorlawson 0:cf4396614a79 84 * Insert the data to the tail of the doublely linked list.
rconnorlawson 0:cf4396614a79 85 * Do not update the current node.
rconnorlawson 0:cf4396614a79 86 *
rconnorlawson 0:cf4396614a79 87 * @param dLinkedList A pointer to the doublely linked list
rconnorlawson 0:cf4396614a79 88 * @param data A void pointer to data the user is adding to the doublely linked list.
rconnorlawson 0:cf4396614a79 89 *
rconnorlawson 0:cf4396614a79 90 */
rconnorlawson 0:cf4396614a79 91 void insertTail(DLinkedList* dLinkedList, void* data);
rconnorlawson 0:cf4396614a79 92
rconnorlawson 0:cf4396614a79 93
rconnorlawson 0:cf4396614a79 94 /**
rconnorlawson 0:cf4396614a79 95 * insertAfter
rconnorlawson 0:cf4396614a79 96 *
rconnorlawson 0:cf4396614a79 97 * Insert a new node into the doublely linked list immediately after the current node.
rconnorlawson 0:cf4396614a79 98 * If the current node is NULL, this method fails. Do not update the current node.
rconnorlawson 0:cf4396614a79 99 *
rconnorlawson 0:cf4396614a79 100 * @param dLinkedList A pointer to the doublely linked list.
rconnorlawson 0:cf4396614a79 101 * @param newData A void pointer to the new data to insert.
rconnorlawson 0:cf4396614a79 102 * @return 1 if inserted the new data successfully
rconnorlawson 0:cf4396614a79 103 * 0 if the current pointer is NULL
rconnorlawson 0:cf4396614a79 104 */
rconnorlawson 0:cf4396614a79 105 int insertAfter(DLinkedList* dLinkedList, void* newData);
rconnorlawson 0:cf4396614a79 106
rconnorlawson 0:cf4396614a79 107
rconnorlawson 0:cf4396614a79 108 /**
rconnorlawson 0:cf4396614a79 109 * insertBefore
rconnorlawson 0:cf4396614a79 110 *
rconnorlawson 0:cf4396614a79 111 * Insert a new node into the doublely linked list immediately before the current node.
rconnorlawson 0:cf4396614a79 112 * If the current node is NULL, this method fails. Do not update the current node.
rconnorlawson 0:cf4396614a79 113 *
rconnorlawson 0:cf4396614a79 114 * @param dLinkedList A pointer to the doublely linked list
rconnorlawson 0:cf4396614a79 115 * @param newData A void pointer to the new data to insert
rconnorlawson 0:cf4396614a79 116 * @return 1 if insert the new data successfully
rconnorlawson 0:cf4396614a79 117 * 0 if the current pointer is NULL
rconnorlawson 0:cf4396614a79 118 */
rconnorlawson 0:cf4396614a79 119 int insertBefore(DLinkedList* dLinkedList, void* newData);
rconnorlawson 0:cf4396614a79 120
rconnorlawson 0:cf4396614a79 121
rconnorlawson 0:cf4396614a79 122 /**
rconnorlawson 0:cf4396614a79 123 * deleteBackward
rconnorlawson 0:cf4396614a79 124 *
rconnorlawson 0:cf4396614a79 125 * Delete the node the current pointer is pointed at, and move the current pointer backward.
rconnorlawson 0:cf4396614a79 126 * Be aware that deleteBackward will cause problems if the current node is the list head,
rconnorlawson 0:cf4396614a79 127 * or if the current node is the only node in the list. In these cases, the current
rconnorlawson 0:cf4396614a79 128 * pointer should be set to NULL after deleting the node, and the list head and tail
rconnorlawson 0:cf4396614a79 129 * pointers should be updated appropriately.
rconnorlawson 0:cf4396614a79 130 *
rconnorlawson 0:cf4396614a79 131 * @param dLinkedList A pointer to the doublely linked list
rconnorlawson 0:cf4396614a79 132 * @return the data of the new current pointer and NULL if the current pointer is NULL
rconnorlawson 0:cf4396614a79 133 */
rconnorlawson 0:cf4396614a79 134 void* deleteBackward(DLinkedList* dLinkedList);
rconnorlawson 0:cf4396614a79 135
rconnorlawson 0:cf4396614a79 136
rconnorlawson 0:cf4396614a79 137 /**
rconnorlawson 0:cf4396614a79 138 * deleteForward
rconnorlawson 0:cf4396614a79 139 *
rconnorlawson 0:cf4396614a79 140 * Delete the node the current pointer is pointed at, and move the current pointer forward.
rconnorlawson 0:cf4396614a79 141 * Be aware that deleteForward will cause problems if the current node is the list tail,
rconnorlawson 0:cf4396614a79 142 * or if the current node is the only node in the list. In these cases, the current
rconnorlawson 0:cf4396614a79 143 * pointer should be set to NULL after deleting the node, and the list head and tail
rconnorlawson 0:cf4396614a79 144 * pointers should be updated appropriately.
rconnorlawson 0:cf4396614a79 145 *
rconnorlawson 0:cf4396614a79 146 * @param dLinkedList A pointer to the doublely linked list
rconnorlawson 0:cf4396614a79 147 * @return the data of the new current pointer and NULL if the current pointer is NULL
rconnorlawson 0:cf4396614a79 148 */
rconnorlawson 0:cf4396614a79 149 void* deleteForward(DLinkedList* dLinkedList);
rconnorlawson 0:cf4396614a79 150
rconnorlawson 0:cf4396614a79 151 /**
rconnorlawson 0:cf4396614a79 152 * removeBackward
rconnorlawson 0:cf4396614a79 153 *
rconnorlawson 0:cf4396614a79 154 * Remove the node the current pointer is pointed at from the list and return the data
rconnorlawson 0:cf4396614a79 155 * associated with the current node. Move the current pointer backward.
rconnorlawson 0:cf4396614a79 156 * Be aware that removeBackward will cause problems if the current node is the list head,
rconnorlawson 0:cf4396614a79 157 * or if the current node is the only node in the list. In these cases, the current
rconnorlawson 0:cf4396614a79 158 * pointer should be set to NULL after removing the node, and the list head and tail
rconnorlawson 0:cf4396614a79 159 * pointers should be updated appropriately.
rconnorlawson 0:cf4396614a79 160 *
rconnorlawson 0:cf4396614a79 161 * @param dLinkedList A pointer to the doublely linked list
rconnorlawson 0:cf4396614a79 162 * @return the data of the removed node, or NULL if the current pointer is NULL
rconnorlawson 0:cf4396614a79 163 */
rconnorlawson 0:cf4396614a79 164 void* removeBackward(DLinkedList* dLinkedList);
rconnorlawson 0:cf4396614a79 165
rconnorlawson 0:cf4396614a79 166
rconnorlawson 0:cf4396614a79 167 /**
rconnorlawson 0:cf4396614a79 168 * removeForward
rconnorlawson 0:cf4396614a79 169 *
rconnorlawson 0:cf4396614a79 170 * Remove the node the current pointer is pointed at from the list and return the data
rconnorlawson 0:cf4396614a79 171 * associated with the current node. Move the current pointer forward.
rconnorlawson 0:cf4396614a79 172 * Be aware that removeForward will cause problems if the current node is the list tail,
rconnorlawson 0:cf4396614a79 173 * or if the current node is the only node in the list. In these cases, the current
rconnorlawson 0:cf4396614a79 174 * pointer should be set to NULL after removing the node, and the list head and tail
rconnorlawson 0:cf4396614a79 175 * pointers should be updated appropriately.
rconnorlawson 0:cf4396614a79 176 *
rconnorlawson 0:cf4396614a79 177 * @param dLinkedList A pointer to the doublely linked list
rconnorlawson 0:cf4396614a79 178 * @return the data of the removed node, or NULL if the current pointer is NULL
rconnorlawson 0:cf4396614a79 179 */
rconnorlawson 0:cf4396614a79 180 void* removeForward(DLinkedList* dLinkedList);
rconnorlawson 0:cf4396614a79 181
rconnorlawson 0:cf4396614a79 182
rconnorlawson 0:cf4396614a79 183 /**
rconnorlawson 0:cf4396614a79 184 * destroyList
rconnorlawson 0:cf4396614a79 185 *
rconnorlawson 0:cf4396614a79 186 * Destroy the doublely linked list. Everything in the linked list including list structure,
rconnorlawson 0:cf4396614a79 187 * nodes and data are all freed from the heap
rconnorlawson 0:cf4396614a79 188 *
rconnorlawson 0:cf4396614a79 189 * @param dLinkedList A pointer to the doublely linked list
rconnorlawson 0:cf4396614a79 190 * @param shouldFree Flag. 1 indicates if data should be freed upon deletion of node.
rconnorlawson 0:cf4396614a79 191 *
rconnorlawson 0:cf4396614a79 192 */
rconnorlawson 0:cf4396614a79 193 void destroyList(DLinkedList* dLinkedList);
rconnorlawson 0:cf4396614a79 194
rconnorlawson 0:cf4396614a79 195
rconnorlawson 0:cf4396614a79 196 /**
rconnorlawson 0:cf4396614a79 197 * getHead
rconnorlawson 0:cf4396614a79 198 *
rconnorlawson 0:cf4396614a79 199 * Return the data contained in the head of the doublely linked list, and set the list current pointer
rconnorlawson 0:cf4396614a79 200 * to head
rconnorlawson 0:cf4396614a79 201 *
rconnorlawson 0:cf4396614a79 202 * @param dLinkedList A pointer to the doublely linked list
rconnorlawson 0:cf4396614a79 203 * @return the head data or NULL if head == NULL
rconnorlawson 0:cf4396614a79 204 */
rconnorlawson 0:cf4396614a79 205 void* getHead(DLinkedList* dLinkedList);
rconnorlawson 0:cf4396614a79 206
rconnorlawson 0:cf4396614a79 207 /**
rconnorlawson 0:cf4396614a79 208 * getTail
rconnorlawson 0:cf4396614a79 209 *
rconnorlawson 0:cf4396614a79 210 * Return the data contained in the tail of the doublely linked list, and set the current pointer
rconnorlawson 0:cf4396614a79 211 * to tail
rconnorlawson 0:cf4396614a79 212 *
rconnorlawson 0:cf4396614a79 213 * @param dLinkedList A pointer to the doublely linked list
rconnorlawson 0:cf4396614a79 214 * @return the tail data or NULL if tail == NULL
rconnorlawson 0:cf4396614a79 215 */
rconnorlawson 0:cf4396614a79 216 void* getTail(DLinkedList* dLinkedList);
rconnorlawson 0:cf4396614a79 217
rconnorlawson 0:cf4396614a79 218
rconnorlawson 0:cf4396614a79 219 /**
rconnorlawson 0:cf4396614a79 220 * getCurrent
rconnorlawson 0:cf4396614a79 221 *
rconnorlawson 0:cf4396614a79 222 * Return the data the current pointer is pointing at
rconnorlawson 0:cf4396614a79 223 *
rconnorlawson 0:cf4396614a79 224 * @param dLinkedList A pointer to the doublely linked list
rconnorlawson 0:cf4396614a79 225 * @return the current data or NULL if current == NULL
rconnorlawson 0:cf4396614a79 226 */
rconnorlawson 0:cf4396614a79 227 void* getCurrent(DLinkedList* dLinkedList);
rconnorlawson 0:cf4396614a79 228
rconnorlawson 0:cf4396614a79 229
rconnorlawson 0:cf4396614a79 230 /**
rconnorlawson 0:cf4396614a79 231 * getNext
rconnorlawson 0:cf4396614a79 232 *
rconnorlawson 0:cf4396614a79 233 * Return the next data the current pointer is pointing at, and move the current pointer to next node.
rconnorlawson 0:cf4396614a79 234 * If the current pointer is at the tail, the next node is NULL.
rconnorlawson 0:cf4396614a79 235 *
rconnorlawson 0:cf4396614a79 236 * @param dLinkedList A pointer to the doublely linked list
rconnorlawson 0:cf4396614a79 237 * @return the next data or NULL if current == NULL
rconnorlawson 0:cf4396614a79 238 */
rconnorlawson 0:cf4396614a79 239 void* getNext(DLinkedList* dLinkedList);
rconnorlawson 0:cf4396614a79 240
rconnorlawson 0:cf4396614a79 241
rconnorlawson 0:cf4396614a79 242 /**
rconnorlawson 0:cf4396614a79 243 * getPrevious
rconnorlawson 0:cf4396614a79 244 *
rconnorlawson 0:cf4396614a79 245 * Return the previous data the current pointer is pointing at, and move the current pointer to
rconnorlawson 0:cf4396614a79 246 * previous node. If the current pointer is at the head, the previous node is NULL.
rconnorlawson 0:cf4396614a79 247 *
rconnorlawson 0:cf4396614a79 248 * @param dLinkedList A pointer to the doublely linked list
rconnorlawson 0:cf4396614a79 249 * @return the previous data or NULL if current == NULL
rconnorlawson 0:cf4396614a79 250 */
rconnorlawson 0:cf4396614a79 251 void* getPrevious(DLinkedList* dLinkedList);
rconnorlawson 0:cf4396614a79 252
rconnorlawson 0:cf4396614a79 253
rconnorlawson 0:cf4396614a79 254 /**
rconnorlawson 0:cf4396614a79 255 * getSize
rconnorlawson 0:cf4396614a79 256 *
rconnorlawson 0:cf4396614a79 257 * Return the size of the doublely linked list
rconnorlawson 0:cf4396614a79 258 *
rconnorlawson 0:cf4396614a79 259 * @param dLinkedList A pointer to the doublely linked list
rconnorlawson 0:cf4396614a79 260 * @return the size
rconnorlawson 0:cf4396614a79 261 */
rconnorlawson 0:cf4396614a79 262 int getSize(DLinkedList* dLinkedList);
rconnorlawson 0:cf4396614a79 263 #endif