Imperative implementations
Implementing a deque is simple in the imperative world. We could use a doubly linked list that will give us O(1)
push and pop at both ends.
If we keep track of the first and the last elements, adding or removing elements at either end would just be a matter of twiddling a few pointers. Of course, we cannot use this model as we never ever mutate a data structure in place. What about efficiency then?
Hang on! We will soon see how amortization and laziness help us design an efficient deque algorithm.
