Trace 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.

Operation	Linked List	Value Returned
`enqueue(1)`	`HEAD -> (1) <- TAIL`
`enqueue(2)`	`HEAD -> (1) -> (2) <- TAIL`
`enqueue(3)`
`dequeue()`
`enqueue(4)`
`dequeue()`
`enqueue(5)`
`front()`
`dequeue()`
`front()`

Solution

Operation	Linked List	Value 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) <- TAIL`	3
`dequeue()`	`HEAD -> (4) -> (5) <- TAIL`
`front()`	`HEAD -> (4) -> (5) <- TAIL`	4

Resources

USFCA interactive demo of Queue (Linked List Implementation).