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

Schedule

Day 1

Todo:

  • Wrap up assignment 1 if you haven't already.

Day 2

Todo:

  • Do the Ch 27 Exercises - SimpleLinkedList

Day 3

Todo:

  • Check out your Assignment 2 repository. You should be ready to start the first two parts.

Day 4

Todo:

  • Do the Ch 27 Exercises - LinkedList & DLL

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.

This optional video reviews the basic concepts of linked lists.


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, generally we don't want to depend on doing things like .at(10) in a linked list.

This video review the topic:


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.

This optional video review the topic:


Linked Lists Wrapup

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

This video reviews Doubly Linked Lists:


While this one reviews Linked Lists vs Arrays: