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