Week 4 - Linked Lists

Learning objectives

  • Describe the properties of different kinds of iterators and how they can be implemented for a linked list
  • Reason about the efficiency of algorithms working on an array-based or linked list
  • Implement common operations, using recursion, in a linked list

Schedule

Day 1

Todo:

  • Work on the midterm review guide

Day 2

Todo:

  • Do the Ch 28 Exercises - Slicing
  • Continue on the midterm review guide

Day 3

Todo:

  • Do the Ch 28 Exercises - LinkedListRecursion
This material is not on the midterm!

Day 4

Midterm.

Day 1

  • List Iterators
  • Check out the midterm review guide in the week 4 module.
The midterm will be pen-and-paper and will cover all material up through 28.7 (Day 2 of this week). You should already have made an appointment. If not, do so ASAP. Check the discussion board for details.

Day 2


Day 3

This material is not on the midterm!

Day 4

Take the midterm. If you are doing the midterm on a different day, use this time to work on assignment 2.

List Iterators

Read Ch 28.1-28.4. You won't be responsible for implementing iterators for your code (not that the code is complex), but you should understand how iterators are implemented and what the different kinds of iterators can do.

This optional video reviews the key ideas:


Adapting Algorithms for Linked Lists

Read Ch 28.5-28.7 on adapting algorithms for linked lists.

This video reviews the material:


Recursion and Linked Lists

Read Ch 28-8-28.11.

Any function that we implement with a loop in a linked list can also be done with recursion. Although there aren't many common algorithms for linked lists where recursion makes implementation easier, they are a great place to practice recursively moving through pointer based structures. When we get to Binary Search Trees, which are a similar pointer-based structure, we will need to use recursion to implement many algorithms.

Optional video on the material: