• Choose a category
• All
• Classic-Fiction

* *

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

typedef struct ListElmt_ {

void *data;

struct ListElmt_ *next;

} ListElmt;

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

* *

* Define a structure for linked lists. *

* *

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

typedef struct List_ {

int size;

int (*match)(const void *key1, const void *key2);

void (*destroy)(void *data);

ListElmt *head;

ListElmt *tail;

} List;

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

* *

* --------------------------- Public Interface --------------------------- *

* *

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

void list_init(List *list, void (*destroy)(void *data));

void list_destroy(List *list);

int list_ins_next(List *list, ListElmt *element, const void *data);

int list_rem_next(List *list, ListElmt *element, void **data);

#define list_size(list) ((list)->size)

#define list_head(list) ((list)->head)

#define list_tail(list) ((list)->tail)

#define list_is_head(list, element) ((element) == (list)->head ? 1 : 0)

#define list_is_tail(element) ((element)->next == NULL ? 1 : 0)

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

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

#endif

list_init

The list_init operation initializes a linked list so that it can be used in other operations (see Example 5.2). Initializing a linked list is a simple operation in which the size member of the list is set to 0, the destroy member to destroy, and the head and tail pointers to NULL.

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

list_destroy

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

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

list_ins_next

The list_ins_next operation inserts an element into a linked list just after a specified element (see Example 5.2). The call sets the new element to point to the data passed by the caller. The actual process of inserting the new element into the list is a simple one, but it does require some care. There are two cases to consider: insertion at the head of the list and insertion elsewhere.

Generally, to insert an element into a linked list, we set the next pointer of the new element to point to the element it is going to precede, and we set the next pointer of the element that will precede the new element to point to the new element (see Figure 5.3). However, when inserting at the head of a list, there is no element that will precede the new element. Thus, in this case, we set the next pointer of the new element to the current head of the list, then reset the head of the list to point to the new element. Recall from the interface design in the previous section that passing NULL for element indicates that the new element should be inserted at the head. In addition to these tasks, whenever we insert an element at the tail of the list, we must update the tail member of the list data structure to point to the new tail. Last, we update the size of the list by incrementing its size member.

Figure 5.3. Inserting an element into a linked list

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

list_rem_next

The list_rem_next operation removes from a linked list the element just after a specified element (see Example 5.2). The reasons for removing the element just after, as opposed to the element itself, are discussed in the questions and