Mastering Algorithms with C

Implementation and Analysis of Doubly Linked Lists

Recall that each element of a doubly-linked list consists of three parts: a data member, a pointer to the next element, and a pointer to the previous element. The structure DListElmt represents an individual element of a doubly-linked list (see Example 5.4). As you would expect, this structure has three members corresponding to those just mentioned. The structure DList is the doubly-linked list data structure (see Example 5.4). This structure has members analogous to the ones used for singly-linked lists.

Example 5.4. Header for the Doubly-Linked List Abstract Datatype

/***************************************************************************** * * * ------------------------------- dlist.h -------------------------------- * * * *****************************************************************************/ #ifndef DLIST_H #define DLIST_H #include <stdlib.h> /***************************************************************************** * * * 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 ...