Are there any good packages for Emacs that implement doubly-linked lists? I know I could make them myself, but I'd rather not re-invent the wheel.
Interestingly I had the same question recently. The only library I found is the now defunct Elib project (http://www.math.utah.edu/docs/info/elib_4.html#SEC14) (some discussion and another person commenting about DLL's here). Although the project is now unmaintained, you can still obtain the source from ftp://ftp.lysator.liu.se/pub/emacs/.
A word of warning: Since DLL's are a non-trivial datastructure be prepared for Emacs to hang up to several minutes when it tries to barf a stack trace containing your DLL.
I cleaned up the DLL code a little bit with a mind to publish on MELPA, but it will probably be a while before I find the time to finish it.