Edit: and even among "interview puzzle data structures", stacks and queues have much simpler semantics than linked lists.