Trace Linked Implementation
Think about a linked implementation of Stack 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 |
|---|---|---|
push(6) | HEAD -> (6) | |
push(10) | HEAD -> (10) -> (6) | |
push(2) | ||
top() | ||
pop() | ||
push(15) | ||
pop() | ||
pop() | ||
push(5) | ||
top() |
Solution
| Operation | Linked List | Value Returned |
|---|---|---|
push(6) | HEAD -> (6) | |
push(10) | HEAD -> (10) -> (6) | |
push(2) | HEAD -> (2) -> (10) -> (6) | |
top() | HEAD -> (2) -> (10) -> (6) | $2$ |
pop() | HEAD -> (10) -> (6) | |
push(15) | HEAD -> (15) -> (10) -> (6) | |
pop() | HEAD -> (10) -> (6) | |
pop() | HEAD -> (6) | |
push(5) | HEAD -> (5) -> (6) | |
top() | HEAD -> (5) -> (6) | $5$ |
Resources
- USFCA interactive demo of Stack (Linked List Implementation).