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.