Outline:

1. Questions?
2. Recap: stack implementations
   • mutable list vs fixed array vs growing array
   • time complexity
3. Linked lists
   • overview
   • implementation: Exercise
   • time complexity
   • building a stack with a linked list
4. Wrap-up

What’s next

• Quiz 3 will be next Monday and cover the following Quiz Learning Objectives:
  • SK 1: stack ADT
  • SK 2: stack time complexity
  • LT 1: linked lists
  • LT 2: linked-list time complexity
  • [if space] KF 1: variables and/or KF 3: loops
• Assignment 3 is due next Wednesday

What you should do now:

• The readings (see below)
• Complete Part A of Assignment 3

Reading assignment (to be completed by the next class):

Linked lists (from today):

• Singly Linked Lists

Queues (for next time):

• Queues
• Circular queue