Mastering Algorithms With C - Kyle Loudon [40]
Description
Inserts an element just after element in the circular list specified by list. When inserting into an empty list, element may point anywhere but should be NULL to avoid confusion. The new element contains a pointer to data, so the memory referenced by data should remain valid as long as the element remains in the list. It is the responsibility of the caller to manage the storage associated with data.
Complexity
O (1)
Name
clist_rem_next
Synopsis
int clist_rem_next(CList *list, CListElmt *element, void **data);
Return Value
0if removing the element is successful, or -1 otherwise.
Description
Removes the element just after element from the circular list specified by list. Upon return, data points to the data stored in the element that was removed. It is the responsibility of the caller to manage the storage associated with the data.
Complexity
O (1)
Name
clist_size
Synopsis
int clist_size(const CList *list);
Return Value
Number of elements in the list.
Description
Macro that evaluates to the number of elements in the circular list specified by list.
Complexity
O (1)
Name
clist_head
Synopsis
CListElmt *clist_head(const CList *list);
Return Value
Element at the head of the list.
Description
Macro that evaluates to the element at the head of the circular list specified by list.
Complexity
O (1)
Name
clist_data
Synopsis
void *clist_data(const CListElmt *element);
Return Value
Data stored in the element.
Description
Macro that evaluates to the data stored in the element of a circular list specified by element.
Complexity
O (1)
Name
clist_next
Synopsis
CListElmt *clist_next(const CListElmt *element);
Return Value
Element following the specified element.
Description
Macro that evaluates to the element of a circular list following the element specified by element.
Complexity
O (1)
Implementation and Analysis of Circular Lists
As with a singly-linked list, each element of a circular list consists of two parts: a data member and a pointer to the next element. The structure CListElmt represents an individual element of a circular list (see Example 5.6). As you would expect, this structure has two members corresponding to those just mentioned. The structure CList is the circular list data structure (see Example 5.6). This structure is similar to the one used for singly-linked lists, but it does not contain the tail member.
Example 5.6. Header for the Circular List Abstract Datatype
/*****************************************************************************
* *
* ------------------------------- clist.h -------------------------------- *
* *
*****************************************************************************/
#ifndef CLIST_H
#define CLIST_H
#include /***************************************************************************** * * * Define a structure for circular list elements. * * * *****************************************************************************/ typedef struct CListElmt_ { void *data; struct CListElmt_ *next; } CListElmt; /***************************************************************************** * * * Define a structure for circular lists. * * * *****************************************************************************/ typedef struct CList_ { int size; int (*match)(const void *key1, const void *key2); void (*destroy)(void *data); CListElmt *head; } CList; /***************************************************************************** * * * --------------------------- Public Interface --------------------------- * * * *****************************************************************************/ void clist_init(CList *list, void (*destroy)(void *data)); void clist_destroy(CList *list); int clist_ins_next(CList *list, CListElmt *element, const void *data); int clist_rem_next(CList *list, CListElmt *element, void **data); #define clist_size(list) ((list)->size) #define