duallist

A duallist is a simple, two-list implementation of a queue used in functional programming. It stores elements in two singly linked lists, commonly called the front (F) and the back (B). The design aims to support efficient insertion at one end and removal from the other without mutating a single list on every operation.

Structure and operations: The duallist maintains two lists: the front list from which elements are removed and the back list into which new elements are enqueued. Enqueuing adds to the back list; dequeuing removes from the front list. If the front list becomes empty, the back list is reversed and becomes the new front, and the back list is reset to empty. This rebalance preserves the overall order of elements and avoids frequent large mutations.

Performance: Each operation has amortized O(1) time. A single operation may incur O(n) time during a rebalancing step when the front list is empty and the back list must be reversed, but the cost is spread across subsequent operations, yielding constant average time per operation.

Origins and usage: The duallist is also described as a two-list queue and appears in discussions of pure functional data structures. It provides a mutation-free way to implement a queue in languages with immutable data, offering a straightforward and predictable approach to enqueue and dequeue operations.

Relation to other structures: The duallist is closely related to the two-stack queue and to double-ended queues (deques). While similar in goal to efficiently support additions and removals at opposite ends, the duallist emphasizes a two-list representation and amortized analysis, making it a foundational concept in functional data structure design.