Consider our queue implementation using two lists from the previous chapter. When the out
list becomes empty, we substitute it with the reversed in
list.
To jog your memory, here is the relevant code snippet:
scala> def pop(queue: Fifo): (Int, Fifo) = {
| queue.out match {
| case Nil => throw new IllegalArgumentException("Empty queue");
| case x :: Nil => (x, queue.copy(out = queue.in.reverse, Nil))
| case y :: ys => (y, queue.copy(out = ys))
| }
| }
pop: (queue: Fifo)(Int, Fifo)
Note the second case clause where the substitution happens. When we have a large number of insertions, reversing the in
list would possibly incur O(n) cost. This would happen once in a while, but that would still be something at least.
So most of our push
and pop
operations would be O(1), given the occasional in
list reversal that could be O(n). This is the concept of amortization, where the occasional cost of reversal is paid off...