Phil Bagwell's VList data structure seems really interesting as a way to avoid a bunch of the pitfalls of naive lists performance-wise - the paper's good fun and there seems to be an implementation in racket for anybody who wants to play with it.
The problem with a vlist is that it doesn’t maintain lisp list semantics. You can’t implement setcdr on a vlist. But you can with something like cdr-coding.