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 your midterm NOW for next week. See discussion board for details!

Day 1

  • Linked List intro

Day 2

  • Linked List Improvements

Day 3

  • Variants of Linked Lists

Day 4

  • 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 CPPLab

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

  • Do the LinkedList - Memory CPPLab

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 CPPLabs.

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

  • Do the DLL CPPLab

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.