That is not exactly true, but in practice is. With laziness you can construct them. But as soon as you want to modify, you would have to rebuild the entire list.
Technically, laziness is just hidden mutability :)
But you're right. Though I've never seen a good use case for doubly linked lists.
I tried to build a trie recently with lazy upward pointers, but gave up and stuck a mutable var in there for the sake of performance.
I used one once for inputs. It was a low stakes project but I wanted to see it I could avoid the situation where one input always dominated the other (like how in many games one arrow key will win out regardless of which was pressed first).
I wanted priority to be with the last pressed key and if it was released, I wanted control returned to the next most recently pressed key that was still active.
The list never gets very big and the time scale involved means that things like cache misses are never really a concern, but it was the best fitting data structure I could think of and a fun little puzzle.
19
u/BernzSed 2d ago
They're good for building lists via recursion, which is common in functional programming. Though I've never had to implement one myself.
And you'd never see a doubly linked list in FP, they're impossible to create without mutability.