Comments and corrections?
I like the idea of being able to use alists rather than inventing a new data structure for bidirectional lists.
Still, I wonder about using HAMTs (Hash Array Mapped Tries) as the basis instead. Thinking about this a bit more, if one kept a HAMT mapping keys to pairs of keys or #f, then the car of each pair could represent the element to the left in the list, if any, and the cdr could represent the element to the right, if any. (If one wanted to be able to store #f as a key, one could use a special value to represent that there was no adjacent key in that direction.) HAMTs can be persistent, and the implementation that I contributed for SRFI 146 follows Clojure's model by allowing one to switch between persistent and mutable states. (The mutable version reduces constant-time overhead.) This design would allow for quick deletion and insertion in the middle of the list, too.
It has been a long time since I thought about HAMTs, but this seems doable and practical.
This reminds me that I need to read Okasaki's Purely Functional Data Structures book. It's on my shelf, and the reviews say it's fantastic, but I haven't gotten around to it.