Chapter Review Questions

1. LIFO.

   1. What does LIFO stand for?

   2. Which data structure follows LIFO order?

2. FIFO.

   1. What does FIFO stand for?

   2. Which data structure follows FIFO order?

3. Why is collections.deque preferred over a plain Python list for implementing a queue?

4. Stacks with Python lists.

   1. When using a Python list as a stack, which end is the “top” — index 0 or the last index?

   2. Which list methods correspond to push and pop?

5. Write code to push the values 1, 2, 3 onto a stack, then pop and print each value. What order do they print in?

6. What does None represent in a singly linked list?

7. Trace what happens to the head pointer when you call prepend on an empty linked list, then call it again on the resulting one-element list.

8. Index access performance.

   1. What is the time complexity of index access (lst[i]) for a Python list?

   2. What is it for a linked list?

   3. Why do they differ?

9. Given the linked list 5 -> 10 -> 20 -> None, show the state after calling remove(10).

10. Trade-offs between linked lists and Python lists.

    1. Name one situation where a linked list has a performance advantage.

    2. Name one situation where a Python list is faster.