Mastering Algorithms with C

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 <stdlib.h> /***************************************************************************** * * * 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 ...