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

Class Schedule

Monday

  • List Iterators

Tuesday

  • LinkedLists vs ArrayLists
  • Midterm Review

Wednesday

  • Linked Lists & Recursion (Not on midterm, will use next week)

Thursday

Pen-and-paper midterm in class

Topics

List Iterators

  • Watch this video on list iterators:

  • Read Liang Ch 20.5

Do the LinkedList Iterator WS

Linked Lists vs Arrays

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

Review

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

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!