My D Common Lisp library exists to enable using doubly-linked lists in a program using a style which resembles singly-linked lists as closely as reasonable. This library was written, as I need such in a program I'm currently writing, which is a re-envisioning of an earlier implementation; the lacking of doubly-linked lists in the standard library had me originally writing my program using a parallel array approach, and it's queer for me to look back and wonder how I didn't realize what I was doing.
This library is licensed under the GNU Affero General Public License version three.
The D library should be considered eternally incomplete, as there's no restriction on further adding to it, and I intend to do this at my leisure and as I recognize more common routines. The intention is that the library will always be used with its prefix, usually a laughable idea, because it shares symbols with the common Lisp symbols; this approach nicely avoids any unnecessary prefixing, and yet has prefixing in practice. The fundamental unit of this library is CONS, containing a CBR, CAR, and CDR; this scheme very pleasantly uses the first four letters of the alphabet, and CBR can be thought of as having a ``backwards'' mnemonic. As with the singly-linked lists, NIL is used in termination. My decision to avoid a circular representation, or using a holder for both ends is purely aesthetic.
The CBR, CAR, and CDR behave as the usual CAR and CDR do, including regarding NIL. Whereas a single link avoids many design considerations, I've come to realize doubly-linked lists pose several issues of links and choice in handling them; in particular, LINK and UNLINK should be used for more complex list manipulations that a singly-linked list hides by its inability to be traversed down both paths.
The LIST is likely to be used for making most doubly-linked lists, returning that most ``backwards'' element as its primary value, and the other end as its second, for when this is needed; the LIST* is similar to its singly-linked counterpart, with the first element being the first CBR, along with the last element being the last CDR, also returning two values. The MAKE-LIST needs little explanation.
The LENGTH returns three values: that primary value is the total length of the list, the second from following the CBR, and the last being by the CDR. If only one of the latter lengths be wanted, pass the relevant symbol as the second parameter, in which case the primary and corresponding values will comply, with that unwanted length being reported as zero, although don't depend on it being zero so. The LIST-LENGTH is as LENGTH, also detecting circularity, with the circular lengths reported as NIL.
I refuse to name that desire to traverse both CBR and CDR; relevant functions will observe parameter passing and use that to determine such, which merely has a caveat regarding a conditional traversal. Follows is code which should be used for conditionally traversing so, and should be fairly uncommon:
(APPLY 'D:LENGTH LIST (COND (... '(D:CBR)) (... '(D:CDR))))
In writing POP and PUSH, I originally wrote macros blindly, before realizing this was unnecessary; I made them functions, which merely save calls to UNLINK, LINK, CONS, and whatnot, being conveniences.
Here is the source and the documentation.