• Choose a category
• All
• Classic-Fiction

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

* *

* Define a structure for doubly-linked list elements. *

* *

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

typedef struct DListElmt_ {

void *data;

struct DListElmt_ *prev;

struct DListElmt_ *next;

} DListElmt;

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

* *

* Define a structure for doubly-linked lists. *

* *

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

typedef struct DList_ {

int size;

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

void (*destroy)(void *data);

DListElmt *head;

DListElmt *tail;

} DList;

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

* *

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

* *

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

void dlist_init(DList *list, void (*destroy)(void *data));

void dlist_destroy(DList *list);

int dlist_ins_next(DList *list, DListElmt *element, const void *data);

int dlist_ins_prev(DList *list, DListElmt *element, const void *data);

int dlist_remove(DList *list, DListElmt *element, void **data);

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

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

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

#define dlist_is_head(element) ((element)->prev == NULL ? 1 : 0)

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

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

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

#define dlist_prev(element) ((element)->prev)

#endif

dlist_init

The dlist_init operation initializes a doubly-linked list so that it can be used in other operations (see Example 5.5). Initialization is the same as with a singly-linked list.

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

dlist_destroy

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

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

dlist_ins_next

The dlist_ins_next operation inserts an element into a doubly-linked list just after a specified element (see Example 5.5). Inserting an element in a doubly-linked list is similar to inserting one in a singly-linked list. The primary difference is that in addition to managing the next pointers, we must manage the prev pointers to keep the list linked properly in the reverse direction (see Figure 5.6).

Figure 5.6. Inserting an element into a doubly-linked list with dlist_ins_next

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

dlist_ins_ prev

The dlist_ins_ prev operation inserts an element into a doubly-linked list just before a specified element (see Example 5.5). Inserting an element in a doubly-linked list is similar to inserting one in a singly-linked list. As with dlist_ins_next, the primary difference is that in addition to managing the next pointers, we must manage the prev pointers to keep the list linked properly in the reverse direction.

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

dlist_remove

The dlist_remove operation removes a specified element from a doubly-linked list (see Example 5.5). The primary difference from a singly-linked list is that in addition to managing the next pointers, we must manage the prev pointers to keep the list linked properly in the reverse