Week 4 - Linked Lists

Learning objectives

  • Implement common operations, using either iteration or recursion, in a linked list
  • Reason about the efficiency of algorithms working on an array based or linked list
Your midterm must be taken this week. Make sure it is scheduled! See discussion board.

Day 1

List Iterators

  • Watch this video on list iterators:

  • Read Liang Ch 20.5

Do the LinkedList Iterator WS

Day 2

Linked Lists vs Arrays

When should we use the different kinds of lists? Watch this video comparing Linked vs Array lists:

Review for Midterm

Check out the Midterm Study Guide from the Files link. It has some tips on what to review and some practice questions.

Day 3

Take midterm

Day 4

Recursion & Linked Lists

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.

  • Watch this video:

  • Do the LinkedList - Recursion CPPLab. I highly recommend drawing out some pictures while you work on the problems!

Assignment 2

This week doesn't involve any new programming (other than the Recursion CPPLab which you can safely save for next week). You should be using this week to chip away at assignment 2.