Week 3 - 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

Day 1

Day 2

Day 3

  • Linked List Improvements
  • Check out your Assignment 2 repository. You should be ready to start the first two parts, even though you are not yet done with Linked Lists.

Day 4

  • Linked Lists Wrapup
  • Do the Ch 27 Exercises - LinkedList & DLL This DLL worksheet has some guidance that may help with the logic for some of the exercises: DLL Worksheet. Here is the key

Linked Lists Basics

Read Ch 27.3-27.7, then do the linked list basics worksheet that is linked above.

Don't underestimate the power of drawing a diagram and running code by hand while you are trying to understand or debug an algorithm.

Linked Lists Indexing

Continue reading Ch 27.8-27.10. The focus of those sections is indexing into a linked list. Doing so is much less efficient than indexing into an array, but it is necessary if we want to do something like .at(10) in a linked list.

Linked Lists Improvements

Read 27.11 and 27.12. These sections talk about some improvements we can make to a linked list to make certain operations more efficient.

Linked Lists Wrapup

Finish reading Ch 27, covering Doubly Linked Lists, a review of BigO, and a comparison of arrays and linked lists.