11.12 Doubly-Linked Lists

A doubly-linked list is a mere extension of the ordinary linked list. While the latter one has an entry pointer to the first element of the list (obtainable via car) and for each element a pointer to the next element (obtainable via cdr), the doubly-linked list (dl-list for short) has both, an entry pointer to the first element and an entry pointer to the last element. These are obtainable via dllist-car and dllist-rac, respectively. Moreover, all elements of the dl-list point to the next and the previous element.

This well-known structure supports both appending and prepending elements in the same time complexity class.

Function: dllist &rest initial-elements

Return a doubly-linked list.

Optionally passed arguments are filled into the resulting dllist.

Function: dllistp object

Return non-nil if object is a dllist, nil otherwise.

Function: dllist-empty-p dllist

Return non-nil if dllist is empty, nil otherwise.

Function: dllist-size dllist

Return the size of dllist, that is the number of elements.

Function: dllist-car dllist

Return the front element of dllist.

Function: dllist-rac dllist

Return the back element of dllist.

Note: All of the following modifier functions work by side-effect.

Function: dllist-prepend dllist element

Add element to the front of dllist.

Function: dllist-append dllist element

Add element to the back of dllist.

Function: dllist-pop-car dllist

Remove the front element of dllist and return it.

Function: dllist-pop-rac dllist

Remove the back element of dllist and return it.

In box notation a dllist looks like

car         _______     _______
|          |       |   |       |    --> nil
|     _____|_     _v___|_     _v___|_
 --> |_______|   |_______|   |_______| <--
       | | ^       | | ^       | |        |
nil <--  | |_______| | |_______| |        |
         v           v           v        rac
       data1       data2       data3

Let us look at some examples.

(setq d (dllist))
  ⇒ (dllist)
(dllistp d)
  ⇒ t

(dllist-append d 2)
  ⇒ (dllist 2)
(dllist-append d 4)
  ⇒ (dllist 2 4)
(dllist-append d 6)
  ⇒ (dllist 2 4 6)

(dllist-car d)
  ⇒ 2
(dllist-rac d)
  ⇒ 6

(dllist-prepend d (dllist-pop-rac d))
  ⇒ (dllist 6 2 4)
(dllist-append d (dllist-pop-car d))
  ⇒ (dllist 2 4 6)
(dllist-size d)
  ⇒ 3

Of course, dl-lists can be converted to ordinary lisp lists.

Function: dllist-to-list dllist

Return the ordinary list induced by dllist, that is start with the first element in dllist and traverse through the back.

Function: dllist-to-list-reversed dllist

Return the ordinary list induced by dllist in reverse order, that is start with the last element in dllist and traverse through the front.

(dllist-to-list d)
  ⇒ (2 4 6)
(dllist-to-list-reversed d)
  ⇒ (6 4 2)