Mastering Algorithms With C - Kyle Loudon [39]
* *
* Remove the element from the list. *
* *
*****************************************************************************/
*data = element->data;
if (element == list->head) {
/**************************************************************************
* *
* Handle removal from the head of the list. *
* *
**************************************************************************/
list->head = element->next;
if (list->head == NULL)
list->tail = NULL;
else
element->next->prev = NULL;
}
else {
/**************************************************************************
* *
* Handle removal from other than the head of the list. *
* *
**************************************************************************/
element->prev->next = element->next;
if (element->next == NULL)
list->tail = element->prev;
else
element->next->prev = element->prev;
}
/*****************************************************************************
* *
* Free the storage allocated by the abstract datatype. *
* *
*****************************************************************************/
free(element);
/*****************************************************************************
* *
* Adjust the size of the list to account for the removed element. *
* *
*****************************************************************************/
list->size--;
return
0;
}
Description of Circular Lists
The circular list is another form of linked list that provides additional flexibility in traversing elements. A circular list may be singly-linked or doubly-linked, but its distinguishing feature is that it has no tail. In a circular list, the next pointer of the last element points back to its first element rather than to NULL. In the case of a doubly-linked circular list, the prev pointer of the first element is set to point to the last element as well.
Whether dealing with a singly-linked or doubly-linked circular list, we never need to worry about reaching an element from which we can traverse no further as we move from element to element. Instead, the traversal simply continues back to the first element, or, in the case of a doubly-linked circular list, back to the last element. Traversing a list in this manner produces a circular pattern (see Figure 5.7), hence its name.
Figure 5.7. Elements linked together to form a circular list
The circular list presented in the following sections is a singly-linked circular list. Therefore, we are concerned only with maintaining a link from the last element back to the first element. In practice, whether to make use of a singly-linked circular list or one that is doubly-linked depends on the same reasoning presented earlier for choosing between singly-linked and doubly-linked lists that are not circular.
Interface for Circular Lists
Name
clist_init
Synopsis
void clist_init(CList *list, void (*destroy)(void *data));
Return Value
None.
Description
Initializes the circular list specified by list. This operation must be called for a circular list before the list can be used with any other operation. The destroy argument provides a way to free dynamically allocated data when clist_destroy is called. It works in a manner similar to that described for list_destroy. For a circular list containing data that should not be freed, destroy should be set to NULL.
Complexity
O (1)
Name
clist_destroy
Synopsis
void clist_destroy(CList *list);
Return Value
None.
Description
Destroys the circular list specified by list. No other operations are permitted after calling clist_destroy unless clist_init is called again. The clist_destroy operation removes all elements from a circular list and calls the function passed as destroy to clist_init once for each element as it is removed, provided destroy was not set to NULL.
Complexity
O (n), where n is the number of elements in the circular list.
Name
clist_ins_next
Synopsis
int clist_ins_next(CList *list, CListElmt *element, const void *data);
Return Value
0if inserting