doublely_linked_list.h

00001 /** @file doublely_linked_list.h */
00002 #ifndef DOUBLELINKEDLIST_H
00003 #define DOUBLELINKEDLIST_H
00004 
00005 
00006 /********************************************
00007  * Doublely Linked List library functions *
00008  * For more details on their functionality, *
00009  * see the documentation in doublely_linked_list.c *
00010  ********************************************/
00011 
00012 
00013 /**
00014  * This structure represents an entire linked list.
00015  */
00016 typedef struct dlinkedlist_t {
00017     /** The head pointer for the list (points to the first node) */
00018     struct llnode_t* head;
00019 
00020     /** The tail pointer for the list (points to the last node) */
00021     struct llnode_t* tail;
00022 
00023     /** The current pointer for the list (points to the current node) */
00024     struct llnode_t* current;
00025 
00026     /** The number of nodes in the list */
00027     int size;
00028 } DLinkedList;
00029 
00030 /**
00031  * This structure represents a single list node.
00032  */
00033 typedef struct llnode_t {
00034     /** The data associated with this node */
00035     void* data;
00036 
00037     /** A pointer to the previous node in the list. NULL if there is no previous node. */
00038     struct llnode_t* previous;
00039 
00040     /** A pointer to the next node in the list. NULL if there is no next node. */
00041     struct llnode_t* next;
00042 } LLNode;
00043 
00044 
00045 /**
00046  * create_dlinkedlist
00047  *
00048  * Creates a doublely liked list by allocating memory for it on the heap. Initialize the size to zero,
00049  * as well as head, current, and tail pointer to NULL
00050  *
00051  * @return A pointer to an empty dlinkedlist
00052  */
00053 DLinkedList* create_dlinkedlist(void);
00054 
00055 /**
00056  * create_llnode
00057  *
00058  * Helper function that creates a node by allocating memory for it on the heap,
00059  * and initializing its previous and next pointers to NULL and its data pointer to the input
00060  * data pointer
00061  *
00062  * @param data A void pointer to data the user is adding to the doublely linked list.
00063  * @return A pointer to the linked list node
00064  */
00065 LLNode* create_llnode(void* data);
00066 
00067 
00068 /**
00069  * InsertHead
00070  *
00071  * Insert the data to the head of the doublely linked list.
00072  * Do not update the current node.
00073  *
00074  * @param dLinkedList A pointer to the doublely linked list
00075  * @param data A void pointer to data the user is adding to the doublely linked list.
00076  *
00077  */
00078 void insertHead(DLinkedList* dLinkedList, void* data);
00079 
00080 
00081 /**
00082  * insertTail
00083  *
00084  * Insert the data to the tail of the doublely linked list.
00085  * Do not update the current node.
00086  *
00087  * @param dLinkedList A pointer to the doublely linked list
00088  * @param data A void pointer to data the user is adding to the doublely linked list.
00089  *
00090  */
00091 void insertTail(DLinkedList* dLinkedList, void* data);
00092 
00093 
00094 /**
00095  * insertAfter
00096  *
00097  * Insert a new node into the doublely linked list immediately after the current node.
00098  * If the current node is NULL, this method fails. Do not update the current node.
00099  *
00100  * @param dLinkedList A pointer to the doublely linked list.
00101  * @param newData A void pointer to the new data to insert.
00102  * @return 1 if inserted the new data successfully
00103  *         0 if the current pointer is NULL
00104  */
00105 int insertAfter(DLinkedList* dLinkedList, void* newData);
00106 
00107 
00108 /**
00109  * insertBefore
00110  *
00111  * Insert a new node into the doublely linked list immediately before the current node.
00112  * If the current node is NULL, this method fails. Do not update the current node.
00113  *
00114  * @param dLinkedList A pointer to the doublely linked list
00115  * @param newData A void pointer to the new data to insert
00116  * @return 1 if insert the new data successfully
00117  *         0 if the current pointer is NULL
00118  */
00119 int insertBefore(DLinkedList* dLinkedList, void* newData);
00120 
00121 
00122 /**
00123  * deleteBackward
00124  *
00125  * Delete the node the current pointer is pointed at, and move the current pointer backward.
00126  * Be aware that deleteBackward will cause problems if the current node is the list head,
00127  * or if the current node is the only node in the list. In these cases, the current
00128  * pointer should be set to NULL after deleting the node, and the list head and tail
00129  * pointers should be updated appropriately.
00130  *
00131  * @param dLinkedList A pointer to the doublely linked list
00132  * @return the data of the new current pointer and NULL if the current pointer is NULL
00133  */
00134 void* deleteBackward(DLinkedList* dLinkedList);
00135 
00136 
00137 /**
00138  * deleteForward
00139  *
00140  * Delete the node the current pointer is pointed at, and move the current pointer forward.
00141  * Be aware that deleteForward will cause problems if the current node is the list tail,
00142  * or if the current node is the only node in the list. In these cases, the current
00143  * pointer should be set to NULL after deleting the node, and the list head and tail
00144  * pointers should be updated appropriately.
00145  *
00146  * @param dLinkedList A pointer to the doublely linked list
00147  * @return the data of the new current pointer and NULL if the current pointer is NULL
00148  */
00149 void* deleteForward(DLinkedList* dLinkedList);
00150 
00151 /**
00152  * removeBackward
00153  *
00154  * Remove the node the current pointer is pointed at from the list and return the data
00155  * associated with the current node. Move the current pointer backward.
00156  * Be aware that removeBackward will cause problems if the current node is the list head,
00157  * or if the current node is the only node in the list. In these cases, the current
00158  * pointer should be set to NULL after removing the node, and the list head and tail
00159  * pointers should be updated appropriately.
00160  *
00161  * @param dLinkedList A pointer to the doublely linked list
00162  * @return the data of the removed node, or NULL if the current pointer is NULL
00163  */
00164 void* removeBackward(DLinkedList* dLinkedList);
00165 
00166 
00167 /**
00168  * removeForward
00169  *
00170  * Remove the node the current pointer is pointed at from the list and return the data
00171  * associated with the current node. Move the current pointer forward.
00172  * Be aware that removeForward will cause problems if the current node is the list tail,
00173  * or if the current node is the only node in the list. In these cases, the current
00174  * pointer should be set to NULL after removing the node, and the list head and tail
00175  * pointers should be updated appropriately.
00176  *
00177  * @param dLinkedList A pointer to the doublely linked list
00178  * @return the data of the removed node, or NULL if the current pointer is NULL
00179  */
00180 void* removeForward(DLinkedList* dLinkedList);
00181 
00182 
00183 /**
00184  * destroyList
00185  *
00186  * Destroy the doublely linked list. Everything in the linked list including list structure,
00187  * nodes and data are all freed from the heap
00188  *
00189  * @param dLinkedList A pointer to the doublely linked list
00190  * @param shouldFree Flag. 1 indicates if data should be freed upon deletion of node.
00191  *
00192  */
00193 void destroyList(DLinkedList* dLinkedList);
00194 
00195 
00196 /**
00197  * getHead
00198  *
00199  * Return the data contained in the head of the doublely linked list, and set the list current pointer
00200  * to head
00201  *
00202  * @param dLinkedList A pointer to the doublely linked list
00203  * @return the head data or  NULL if head == NULL
00204  */
00205 void* getHead(DLinkedList* dLinkedList);
00206 
00207 /**
00208  * getTail
00209  *
00210  * Return the data contained in the tail of the doublely linked list, and set the current pointer
00211  * to tail
00212  *
00213  * @param dLinkedList A pointer to the doublely linked list
00214  * @return the tail data or  NULL if tail == NULL
00215  */
00216 void* getTail(DLinkedList* dLinkedList);
00217 
00218 
00219 /**
00220  * getCurrent
00221  *
00222  * Return the data the current pointer is pointing at
00223  *
00224  * @param dLinkedList A pointer to the doublely linked list
00225  * @return the current data or NULL if current == NULL
00226  */
00227 void* getCurrent(DLinkedList* dLinkedList);
00228 
00229 
00230 /**
00231  * getNext
00232  *
00233  * Return the next data the current pointer is pointing at, and move the current pointer to next node.
00234  * If the current pointer is at the tail, the next node is NULL.
00235  *
00236  * @param dLinkedList A pointer to the doublely linked list
00237  * @return the next data or NULL if current == NULL
00238  */
00239 void* getNext(DLinkedList* dLinkedList);
00240 
00241 
00242 /**
00243  * getPrevious
00244  *
00245  * Return the previous data the current pointer is pointing at, and move the current pointer to
00246  * previous node.  If the current pointer is at the head, the previous node is NULL.
00247  *
00248  * @param dLinkedList A pointer to the doublely linked list
00249  * @return the previous data or NULL if current == NULL
00250  */
00251 void* getPrevious(DLinkedList* dLinkedList);
00252 
00253 
00254 /**
00255  * getSize
00256  *
00257  * Return the size of the doublely linked list
00258  *
00259  * @param dLinkedList A pointer to the doublely linked list
00260  * @return  the size
00261  */
00262 int getSize(DLinkedList* dLinkedList);
00263 #endif