Trace Linked Implementation

  • Trace the core operations of Queue (linked implementation).

Think about a linked implementation of queue such that the core operations are constant time.

Exercise Complete the table below: update the linked list as you trace the operations; show value returned if any.

OperationLinked ListValue Returned
enqueue(1)HEAD -> (1) <- TAIL
enqueue(2)HEAD -> (1) -> (2) <- TAIL
enqueue(3)
dequeue()
enqueue(4)
dequeue()
enqueue(5)
front()
dequeue()
front()
Solution
OperationLinked ListValue Returned
enqueue(1)HEAD -> (1) <- TAIL
enqueue(2)HEAD -> (1) -> (2) <- TAIL
enqueue(3)HEAD -> (1) -> (2) -> (3) <- TAIL
dequeue()HEAD -> (2) -> (3) <- TAIL
enqueue(4)HEAD -> (2) -> (3) -> (4) <- TAIL
dequeue()HEAD -> (3) -> (4) <- TAIL
enqueue(5)HEAD -> (3) -> (4) -> (5) <- TAIL
front()HEAD -> (3) -> (4) -> (5) <- TAIL3
dequeue()HEAD -> (4) -> (5) <- TAIL
front()HEAD -> (4) -> (5) <- TAIL4
Resources