• Choose a category
• All
• Classic-Fiction

#define clist_data(element) ((element)->data)

#define clist_next(element) ((element)->next)

#endif

clist_init

The clist_init operation initializes a circular list so that it can be used in other operations (see Example 5.7). Initialization is the same as with a singly-linked list that is not circular, with the exception that there is no tail member to initialize.

The runtime complexity of clist_init is O (1) because all of the steps in initializing a circular list run in a constant amount of time.

clist_destroy

The clist_destroy operation destroys a circular list (see Example 5.7). Primarily this means removing all elements from the list. The function passed as destroy to clist_init is called once for each element as it is removed, provided destroy was not set to NULL.

The runtime complexity of clist_destroy is O (n), where n is the number of elements in the list. This is because the O (1) operation clist_rem_next must be called once for each element.

clist_ins_next

The clist_ins_next operation inserts an element into a circular list just after a specified element (see Example 5.7). Inserting an element in a singly-linked circular list is similar to inserting one in a singly-linked list that is not circular. The primary difference occurs when we are inserting into an empty list. In this case, we must set the next pointer of the inserted element to point back to itself. This allows for the circular traversal of a list containing even just one element. It also ensures the proper insertion of elements in the future.

The runtime complexity of clist_ins_next is O (1) because all of the steps in inserting an element into a circular list run in a constant amount of time.

clist_rem_next

The clist_rem_next operation removes from a circular list the element just after a specified element (see Example 5.7). Removing an element from a singly-linked circular list is similar to removing an element from one that is not circular.

The runtime complexity of clist_rem_next is O (1) because all of the steps in removing an element from a circular list run in a constant amount of time.

clist_size, clist_head, clist_data, and clist_next

These macros implement some of the simpler circular list operations (see Example 5.6). Generally, they provide an interface for accessing and testing members of the CList and CListElmt structures.

The runtime complexity of these operations is O (1) because accessing and testing members of a structure are simple tasks that run in a constant amount of time.

Example 5.7. Implementation of the Circular List Abstract Datatype

/*****************************************************************************

* *

* ------------------------------- clist.c -------------------------------- *

* *

*****************************************************************************/

#include

#include

#include "clist.h"

/*****************************************************************************

* *

* ------------------------------ clist_init ------------------------------ *

* *

*****************************************************************************/

void clist_init(CList *list, void (*destroy)(void *data)) {

/*****************************************************************************

* *

* Initialize the list. *

* *

*****************************************************************************/

list->size = 0;

list->destroy = destroy;

list->head = NULL;

return;

}

/*****************************************************************************

* *

* ---------------------------- clist_destroy ----------------------------- *

* *

*****************************************************************************/

void clist_destroy(CList *list) {

void *data;

/*****************************************************************************

* *

* Remove each element. *

* *

*****************************************************************************/

while (clist_size(list) > 0)