Outline:

1. Circular-array-based queue
   • high-level idea
   • explore time complexity: circular queue via mutable list
2. Doubly linked list
   • high-level idea
3. Comparisons of different list implementations
4. Review

What’s next

• Assignment 2 resubmissions are due Monday at 10pm (feedback will be online soon)
• Assignment 3 is due tonight at 10pm
• Assignment 4 will be released soon
• CS Bits & Bytes this week is the Comps Reveal – come see what kinds of projects next year’s seniors will be doing in Comps, and write up two paragraphs to earn a token for an extra assignment resubmission

What you should do now:

• Finish Assignment 3
• Review

Reminder: Exam Day on Friday

You will see these Quiz Learning Objectives for the first time:

• LT 3: array-based lists
• LT 4: array-based list time complexity
• LT 5: debugging lists
• QQ 1: queue ADT
• QQ 2: queue time complexity

There will also be a packet of learning objectives you’ve seen before, covering everything from Units 1+2 except the five listed above.

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

List implementations (from today):

• Circular queue
• Doubly-linked lists

Another linear ADT (for next Monday):

• Deques