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-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.
Return a doubly-linked list.
Optionally passed arguments are filled into the resulting dllist.
nil if object is a dllist,
nil if dllist is empty,
Return the size of dllist, that is the number of elements.
Return the front element of dllist.
Return the back element of dllist.
Note: All of the following modifier functions work by side-effect.
Add element to the front of dllist.
Add element to the back of dllist.
Remove the front element of dllist and return it.
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.
Return the ordinary list induced by dllist, that is start with the first element in dllist and traverse through the back.
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)