Dylan Frausto / Mbed 2 deprecated mberdl_shell_rev_b

f

Dependencies:   mbed 4DGL-uLCD-SE MMA8452

doubly_linked_list.h@6:453dc852ac0f, 2022-04-12 (annotated)

Committer:
dfrausto3
Date:
Tue Apr 12 01:39:20 2022 +0000
Revision:
6:453dc852ac0f
Parent:
0:8e3b9bb1084a 
f

Who changed what in which revision?

UserRevisionLine numberNew contents of line
dfrausto3 6:453dc852ac0f 1 //Put your DLL header file from P2-1 in here//Put your DLL header file from P2-1 in here//=================================================================
dfrausto3 6:453dc852ac0f 2 // Header file for DLL module.
dfrausto3 6:453dc852ac0f 3 //
dfrausto3 6:453dc852ac0f 4 // Copyright 2022 Georgia Tech. All rights reserved.
dfrausto3 6:453dc852ac0f 5 // The materials provided by the instructor in this course are for
dfrausto3 6:453dc852ac0f 6 // the use of the students currently enrolled in the course.
dfrausto3 6:453dc852ac0f 7 // Copyrighted course materials may not be further disseminated.
dfrausto3 6:453dc852ac0f 8 // This file must not be made publicly available anywhere.
dfrausto3 6:453dc852ac0f 9 //=================================================================
dfrausto3 6:453dc852ac0f 10
dfrausto3 6:453dc852ac0f 11 #ifndef DOUBLELINKEDLIST_H
dfrausto3 6:453dc852ac0f 12 #define DOUBLELINKEDLIST_H
dfrausto3 6:453dc852ac0f 13
dfrausto3 6:453dc852ac0f 14 // A function pointer type
dfrausto3 6:453dc852ac0f 15 typedef int (*CompareFunction)(void* input1, void* input2);
dfrausto3 6:453dc852ac0f 16
dfrausto3 6:453dc852ac0f 17 // A linked list node structure.
dfrausto3 6:453dc852ac0f 18 typedef struct llnode_t {
dfrausto3 6:453dc852ac0f 19 void* data;
dfrausto3 6:453dc852ac0f 20 struct llnode_t* prev;
dfrausto3 6:453dc852ac0f 21 struct llnode_t* next;
dfrausto3 6:453dc852ac0f 22 }LLNode;
dfrausto3 6:453dc852ac0f 23
dfrausto3 6:453dc852ac0f 24 /// The structure to store the information of a doubly linked list
dfrausto3 6:453dc852ac0f 25 typedef struct dlinkedlist_t {
dfrausto3 6:453dc852ac0f 26 struct llnode_t* head;
dfrausto3 6:453dc852ac0f 27 struct llnode_t* tail;
dfrausto3 6:453dc852ac0f 28 int size;
dfrausto3 6:453dc852ac0f 29 CompareFunction compare;
dfrausto3 6:453dc852ac0f 30 } DLinkedList;
dfrausto3 6:453dc852ac0f 31
dfrausto3 6:453dc852ac0f 32 //===========================
dfrausto3 6:453dc852ac0f 33 /* Creating nodes and lists */
dfrausto3 6:453dc852ac0f 34 //===========================
dfrausto3 6:453dc852ac0f 35
dfrausto3 6:453dc852ac0f 36 /**
dfrausto3 6:453dc852ac0f 37 * create_llnode
dfrausto3 6:453dc852ac0f 38 *
dfrausto3 6:453dc852ac0f 39 * Creates a node by allocating memory for it on the heap,
dfrausto3 6:453dc852ac0f 40 * and initializing its previous and next pointers to NULL and
dfrausto3 6:453dc852ac0f 41 * its data pointer to the input data pointer
dfrausto3 6:453dc852ac0f 42 *
dfrausto3 6:453dc852ac0f 43 * @param data A void pointer to data the user is adding to the doubly linked list.
dfrausto3 6:453dc852ac0f 44 * @return A pointer to the linked list node
dfrausto3 6:453dc852ac0f 45 */
dfrausto3 6:453dc852ac0f 46 LLNode* create_llnode(void* data);
dfrausto3 6:453dc852ac0f 47
dfrausto3 6:453dc852ac0f 48 /**
dfrausto3 6:453dc852ac0f 49 * create_dlinkedlist
dfrausto3 6:453dc852ac0f 50 *
dfrausto3 6:453dc852ac0f 51 * Creates a doubly linked list by allocating memory for it on the heap.
dfrausto3 6:453dc852ac0f 52 * Initialize the size to zero, as well as head and tail pointers to NULL
dfrausto3 6:453dc852ac0f 53 *
dfrausto3 6:453dc852ac0f 54 * @return A pointer to an empty dlinkedlist
dfrausto3 6:453dc852ac0f 55 */
dfrausto3 6:453dc852ac0f 56 DLinkedList* create_dlinkedlist(CompareFunction compare);
dfrausto3 6:453dc852ac0f 57
dfrausto3 6:453dc852ac0f 58 //============================
dfrausto3 6:453dc852ac0f 59 /* Accessing nodes and lists */
dfrausto3 6:453dc852ac0f 60 //============================
dfrausto3 6:453dc852ac0f 61
dfrausto3 6:453dc852ac0f 62 /**
dfrausto3 6:453dc852ac0f 63 * getSize
dfrausto3 6:453dc852ac0f 64 *
dfrausto3 6:453dc852ac0f 65 * Return the size of the doubly linked list
dfrausto3 6:453dc852ac0f 66 *
dfrausto3 6:453dc852ac0f 67 * @param dLinkedList A pointer to the doubly linked list
dfrausto3 6:453dc852ac0f 68 * @return the size
dfrausto3 6:453dc852ac0f 69 */
dfrausto3 6:453dc852ac0f 70 int getSize(DLinkedList* dLinkedList);
dfrausto3 6:453dc852ac0f 71
dfrausto3 6:453dc852ac0f 72 /**
dfrausto3 6:453dc852ac0f 73 * getHead
dfrausto3 6:453dc852ac0f 74 *
dfrausto3 6:453dc852ac0f 75 * Return the head of the doubly linked list
dfrausto3 6:453dc852ac0f 76 *
dfrausto3 6:453dc852ac0f 77 * @param dLinkedList A pointer to the doubly linked list
dfrausto3 6:453dc852ac0f 78 * @return A pointer to an LLNode
dfrausto3 6:453dc852ac0f 79 */
dfrausto3 6:453dc852ac0f 80 LLNode* getHead(DLinkedList* dLinkedList);
dfrausto3 6:453dc852ac0f 81
dfrausto3 6:453dc852ac0f 82 /**
dfrausto3 6:453dc852ac0f 83 * getTail
dfrausto3 6:453dc852ac0f 84 *
dfrausto3 6:453dc852ac0f 85 * Return the tail of the doubly linked list
dfrausto3 6:453dc852ac0f 86 *
dfrausto3 6:453dc852ac0f 87 * @param dLinkedList A pointer to the doubly linked list
dfrausto3 6:453dc852ac0f 88 * @return A pointer to an LLNode
dfrausto3 6:453dc852ac0f 89 */
dfrausto3 6:453dc852ac0f 90 LLNode* getTail(DLinkedList* dLinkedList);
dfrausto3 6:453dc852ac0f 91
dfrausto3 6:453dc852ac0f 92 /**
dfrausto3 6:453dc852ac0f 93 * getNext
dfrausto3 6:453dc852ac0f 94 *
dfrausto3 6:453dc852ac0f 95 * Return the next node after the input node.
dfrausto3 6:453dc852ac0f 96 *
dfrausto3 6:453dc852ac0f 97 * @param node A pointer to an LLNode
dfrausto3 6:453dc852ac0f 98 * @return A pointer to an LLNode
dfrausto3 6:453dc852ac0f 99 */
dfrausto3 6:453dc852ac0f 100 LLNode* getNext(LLNode* node);
dfrausto3 6:453dc852ac0f 101
dfrausto3 6:453dc852ac0f 102 /**
dfrausto3 6:453dc852ac0f 103 * getPrev
dfrausto3 6:453dc852ac0f 104 *
dfrausto3 6:453dc852ac0f 105 * Return the previous node before the input node.
dfrausto3 6:453dc852ac0f 106 *
dfrausto3 6:453dc852ac0f 107 * @param node A pointer to an LLNode
dfrausto3 6:453dc852ac0f 108 * @return A pointer to an LLNode
dfrausto3 6:453dc852ac0f 109 */
dfrausto3 6:453dc852ac0f 110 LLNode* getPrev(LLNode* node);
dfrausto3 6:453dc852ac0f 111
dfrausto3 6:453dc852ac0f 112 /**
dfrausto3 6:453dc852ac0f 113 * getData
dfrausto3 6:453dc852ac0f 114 *
dfrausto3 6:453dc852ac0f 115 * Return the input node's data.
dfrausto3 6:453dc852ac0f 116 *
dfrausto3 6:453dc852ac0f 117 * @param node A pointer to an LLNode
dfrausto3 6:453dc852ac0f 118 * @return A void pointer to the node's data.
dfrausto3 6:453dc852ac0f 119 */
dfrausto3 6:453dc852ac0f 120 void* getData(LLNode* node);
dfrausto3 6:453dc852ac0f 121
dfrausto3 6:453dc852ac0f 122 //============================
dfrausto3 6:453dc852ac0f 123 /* Inserting nodes into lists */
dfrausto3 6:453dc852ac0f 124 //============================
dfrausto3 6:453dc852ac0f 125
dfrausto3 6:453dc852ac0f 126 /**
dfrausto3 6:453dc852ac0f 127 * insertAfter
dfrausto3 6:453dc852ac0f 128 *
dfrausto3 6:453dc852ac0f 129 * Insert data after the prev_node. Update head/tail if necessary.
dfrausto3 6:453dc852ac0f 130 * Assumes prev_node is not NULL and is in dLinkedList.
dfrausto3 6:453dc852ac0f 131 * (Check if it is NULL and if so, print an error message and return.)
dfrausto3 6:453dc852ac0f 132 * Update the size.
dfrausto3 6:453dc852ac0f 133 *
dfrausto3 6:453dc852ac0f 134 * @param dLinkedList A pointer to the doubly linked list
dfrausto3 6:453dc852ac0f 135 * @param pre_node A pointer to a linked list node.
dfrausto3 6:453dc852ac0f 136 * @param data A void pointer to data.
dfrausto3 6:453dc852ac0f 137 */
dfrausto3 6:453dc852ac0f 138 void insertAfter(DLinkedList* dLinkedList, LLNode* prev_node, void* data);
dfrausto3 6:453dc852ac0f 139
dfrausto3 6:453dc852ac0f 140 /**
dfrausto3 6:453dc852ac0f 141 * insertBefore
dfrausto3 6:453dc852ac0f 142 *
dfrausto3 6:453dc852ac0f 143 * Insert data before the next_node. Update head/tail if necessary.
dfrausto3 6:453dc852ac0f 144 * Assumes next_node is not NULL and is in dLinkedList.
dfrausto3 6:453dc852ac0f 145 * (Check if it is NULL and if so, print an error message and return.)
dfrausto3 6:453dc852ac0f 146 * Update the size.
dfrausto3 6:453dc852ac0f 147
dfrausto3 6:453dc852ac0f 148 *
dfrausto3 6:453dc852ac0f 149 * @param dLinkedList A pointer to the doubly linked list
dfrausto3 6:453dc852ac0f 150 * @param pre_node A pointer to a linked list node.
dfrausto3 6:453dc852ac0f 151 * @param data A void pointer to data.
dfrausto3 6:453dc852ac0f 152 */
dfrausto3 6:453dc852ac0f 153 void insertBefore(DLinkedList* dLinkedList, LLNode* next_node, void* data);
dfrausto3 6:453dc852ac0f 154
dfrausto3 6:453dc852ac0f 155 /**
dfrausto3 6:453dc852ac0f 156 * insertHead
dfrausto3 6:453dc852ac0f 157 *
dfrausto3 6:453dc852ac0f 158 * Create a new LLNode with the given data and insert it at the head of the
dfrausto3 6:453dc852ac0f 159 * doubly linked list. Update head/tail/size if necessary.
dfrausto3 6:453dc852ac0f 160 * Note: The case where dLinkedList is not empty can be implemented by calling
dfrausto3 6:453dc852ac0f 161 * insertBefore with the head of the list as the next_node.
dfrausto3 6:453dc852ac0f 162 *
dfrausto3 6:453dc852ac0f 163 * @param dLinkedList A pointer to the doubly linked list
dfrausto3 6:453dc852ac0f 164 * @param data A void pointer to data the user is adding to the doubly linked list.
dfrausto3 6:453dc852ac0f 165 *
dfrausto3 6:453dc852ac0f 166 */
dfrausto3 6:453dc852ac0f 167 void insertHead(DLinkedList* dLinkedList, void* data);
dfrausto3 6:453dc852ac0f 168
dfrausto3 6:453dc852ac0f 169
dfrausto3 6:453dc852ac0f 170 /**
dfrausto3 6:453dc852ac0f 171 * insertTail
dfrausto3 6:453dc852ac0f 172 *
dfrausto3 6:453dc852ac0f 173 * Create a new LLNode with the given data and insert it at the tail of the
dfrausto3 6:453dc852ac0f 174 * doubly linked list. Update head/tail/size if necessary.
dfrausto3 6:453dc852ac0f 175 * Note: The case where dLinkedList is not empty can be implemented by calling
dfrausto3 6:453dc852ac0f 176 * insertAfter with the tail of the list as the prev_node.
dfrausto3 6:453dc852ac0f 177 *
dfrausto3 6:453dc852ac0f 178 * @param dLinkedList A pointer to the doubly linked list
dfrausto3 6:453dc852ac0f 179 * @param data A void pointer to data the user is adding to the doubly linked list.
dfrausto3 6:453dc852ac0f 180 *
dfrausto3 6:453dc852ac0f 181 */
dfrausto3 6:453dc852ac0f 182 void insertTail(DLinkedList* dLinkedList, void* data);
dfrausto3 6:453dc852ac0f 183
dfrausto3 6:453dc852ac0f 184
dfrausto3 6:453dc852ac0f 185 //============================
dfrausto3 6:453dc852ac0f 186 /* Looking up nodes in lists */
dfrausto3 6:453dc852ac0f 187 //============================
dfrausto3 6:453dc852ac0f 188
dfrausto3 6:453dc852ac0f 189 /**
dfrausto3 6:453dc852ac0f 190 * findNode
dfrausto3 6:453dc852ac0f 191 *
dfrausto3 6:453dc852ac0f 192 * Finds the node whose data points to the same structure pointed to by data.
dfrausto3 6:453dc852ac0f 193 * Uses dLinkedList's compare function to determine whether the data match.
dfrausto3 6:453dc852ac0f 194 * Update head/tail if necessary.
dfrausto3 6:453dc852ac0f 195 *
dfrausto3 6:453dc852ac0f 196 * Return NULL if dLinkedList is empty or data is not found in it.
dfrausto3 6:453dc852ac0f 197 *
dfrausto3 6:453dc852ac0f 198 * @param dLinkedList A pointer to the doubly linked list
dfrausto3 6:453dc852ac0f 199 * @param data The data to be searched for
dfrausto3 6:453dc852ac0f 200 * @return A pointer to an LLNode
dfrausto3 6:453dc852ac0f 201 */
dfrausto3 6:453dc852ac0f 202
dfrausto3 6:453dc852ac0f 203 LLNode* findNode(DLinkedList* dLinkedList, void* data);
dfrausto3 6:453dc852ac0f 204
dfrausto3 6:453dc852ac0f 205
dfrausto3 6:453dc852ac0f 206 //===========================
dfrausto3 6:453dc852ac0f 207 /* Deleting nodes and lists */
dfrausto3 6:453dc852ac0f 208 //===========================
dfrausto3 6:453dc852ac0f 209
dfrausto3 6:453dc852ac0f 210 /**
dfrausto3 6:453dc852ac0f 211 * deleteNode
dfrausto3 6:453dc852ac0f 212 *
dfrausto3 6:453dc852ac0f 213 * Delete the node pointed to by Node (splice it out).
dfrausto3 6:453dc852ac0f 214 * Update head/tail if necessary.
dfrausto3 6:453dc852ac0f 215 * Free the Node's data as well as the Node.
dfrausto3 6:453dc852ac0f 216 * Assumes Node is not NULL and is in dLinkedList.
dfrausto3 6:453dc852ac0f 217 *
dfrausto3 6:453dc852ac0f 218 * @param dLinkedList A pointer to the doubly linked list
dfrausto3 6:453dc852ac0f 219 * @param Node A pointer to a linked list node.
dfrausto3 6:453dc852ac0f 220 */
dfrausto3 6:453dc852ac0f 221 void deleteNode(DLinkedList* dLinkedList, LLNode* Node);
dfrausto3 6:453dc852ac0f 222
dfrausto3 6:453dc852ac0f 223
dfrausto3 6:453dc852ac0f 224 /**
dfrausto3 6:453dc852ac0f 225 * destroyList
dfrausto3 6:453dc852ac0f 226 *
dfrausto3 6:453dc852ac0f 227 * Destroy the doubly linked list. Everything in the linked list including list structure,
dfrausto3 6:453dc852ac0f 228 * nodes and data are all freed from the heap
dfrausto3 6:453dc852ac0f 229 *
dfrausto3 6:453dc852ac0f 230 * @param dLinkedList A pointer to the doubly linked list
dfrausto3 6:453dc852ac0f 231 *
dfrausto3 6:453dc852ac0f 232 */
dfrausto3 6:453dc852ac0f 233 void destroyList(DLinkedList* dLinkedList);
dfrausto3 6:453dc852ac0f 234
dfrausto3 6:453dc852ac0f 235
dfrausto3 6:453dc852ac0f 236 //==================
dfrausto3 6:453dc852ac0f 237 /* Reversing lists */
dfrausto3 6:453dc852ac0f 238 //==================
dfrausto3 6:453dc852ac0f 239
dfrausto3 6:453dc852ac0f 240 /**
dfrausto3 6:453dc852ac0f 241 * reverse
dfrausto3 6:453dc852ac0f 242 *
dfrausto3 6:453dc852ac0f 243 * Reverse the order of the doubly linked list. Update head/tail if necessary.
dfrausto3 6:453dc852ac0f 244 * This should not create a new list (it should rewire the nodes in dLinkedList).
dfrausto3 6:453dc852ac0f 245 *
dfrausto3 6:453dc852ac0f 246 * @param dLinkedList A pointer to the doubly linked list
dfrausto3 6:453dc852ac0f 247 *
dfrausto3 6:453dc852ac0f 248 */
dfrausto3 6:453dc852ac0f 249 void reverse(DLinkedList* dLinkedList);
dfrausto3 6:453dc852ac0f 250
dfrausto3 6:453dc852ac0f 251
dfrausto3 6:453dc852ac0f 252 #endif
dfrausto3 6:453dc852ac0f 253