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

Class Schedule

Monday

  • Linked List intro

Tuesday

  • Linked List Improvements

Wednesday

  • Variants of Linked Lists

Thursday

  • Linked List Sorting

Topics

Linked Lists

  • Watch this video introducing a basic linked list class:

  • Watch this video on programming and debugging tips for linked lists:

  • Read Liang Ch20.0-20.4

  • Do the LinkedList Worksheet

Don't underestimate the power of drawing a diagram and running code by hand while you are trying to understand or debug an algorithm. If you can't draw a diagram of a structure, you don't understand it.

Linked Lists Continued

  • Watch this video on additions we can make to a Linked List to improve the efficiency of certain operations:

  • Do the LinkedList CPP Lab

  • Watch this video on memory management in a linked list:

  • Do the LinkedList - Memory CPP Lab

Doubly Linked Lists

Circular Linked Lists, Doubly Linked Lists

  • Watch this video on different kinds of linked lists:

  • Read Liang Ch20.7

  • Do the DLL Worksheet - it will help you think through the code you need for the CPP Labs.

    Having troubles clearly identifying what something like current->prev->next is doing? Watch this video for tips on how to make things more concrete

Linked List Slicing and Splicing

Watch this video on sorting in linked lists. The most important bit to focus on is how we do tasks like slicing a list in half, or transferring data from one list to another, in a linked list. Often times, it will be a very different strategy than is we were using an array based list.

  • Do the LinkedList Slice Steal WS

Assignment 2

You should already be set to do the first two parts of assignment 2. Get to it! The rest of the material you are learning this week.