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

• Variants of Linked Lists

Tuesday

• Linked List Slicing and Sorting

Wednesday

• Prewatch Linked List vs ArrayList and take reading quiz before class.
• Midterm Review session

Thursday

• Midterm - in class. Pen & Paper.

Topics

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.

• Do the DLL CPPLab

Linked List Slicing and Slicing

• Watch this video on sorting in linked lists. Sorting linked lists is nice, but what we really care about here is how we do jobs differently in a linked list. Pay particular attention to how slicing a list in half and and moving data from one list to another are done:

• Do the LinkedList Sorting CPPLab. The unit tests won't actually run the sort function that is defined. But once you get the helpers (sliceInHalf, stealContents, and mergeInto) working, you can write something simple to see that the sort function works if you like.

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 Class Files link. It has some tips on what to review and some practice questions.