This is a simple immutable deque based on binary trees. What do you think about it? Does this kind of data structure, or possibly an improvement thereof, seem useful? How could I improve it, preferably without getting rid of its strengths? (Not in the sense of more operations, in the sense of different design) Does this sort of thing have a name?
Red nodes are newly instantiated; blue ones are reused. Nodes aren't actually red or anything, it's just for emphasis.
Note that right deques do not take O(n). Any access to an element in the deque depends on how long ago it was inserted. You can perform any enqueue or concat operation at O(1).
You can also use the 'weight' of each non-leaf node to change the orientation of the tree, such as to make all right access costly and left access cheap, or to provide O(logn) access to either end. This process takes O(n) worst case, depending on the initial orientation of the tree.
Alternatively, I could 'search' for the lightest node into which to insert a given node, turning all operations into O(logn) operations.
Best Answer
Congratulations you invented the immutable list. It appears in every functional language and is the bread and butter of functional programming. It's not often used as a dequeue though.
For that purpose there are better data-structures. I recommend reading "Purely Functional Data Structures" by Chris Okasaki if you'd like to gain some insight into the different data-structures that exist.