Mastering Algorithms with C

Description of Doubly-Linked Lists

Doubly-linked lists , as their name implies, are composed of elements linked by two pointers. Each element of a doubly-linked list consists of three parts: in addition to the data and the next pointer, each element includes a pointer to the previous element, called the prev pointer. A doubly-linked list is formed by composing a number of elements so that the next pointer of each element points to the element that follows it, and the prev pointer points to the element preceding it. To mark the head and tail of the list, we set the prev pointer of the first element and the next pointer of the last element to NULL.

To traverse backward through a doubly-linked list, we use the prev pointers of consecutive elements in the tail-to-head direction. Thus, for the cost of an additional pointer for each element, a doubly-linked list offers greater flexibility than a singly-linked list in moving about the list. This can be useful when we know something about where an element might be stored in the list and can choose wisely how to move to it. For example, one flexibility that doubly-linked lists provide is a more intuitive means of removing an element than singly-linked lists.