Linked Lists (Mar 19)

Linked lists in memory and in metaphors
Small examples
Looping through linked lists

Illustrations

Barrel

Hands-on activity. Sample of what each person holds:

Implementing in Code

public class MonkeyChain {
   
   // the structure of an item in the list
   class Node { 
      // contains a String (name) 
      //  and knows who's next
      // ... TODO
   }

   // which monkey am I holding on to?
   private Node first;

   // methods to manipulate the list
   // ... TODO
}

"Inner" Class

class Node { 
   // contains a String (name) 
   String name;

   //  and knows who's next
   Node next;

   // construct a new Node
   Node(String birthName) {
      name = birthName;
      next = null; // need to link later
   }
}

Sample 3-node list

Visualization

Exercise: traversing a list

Using while loop, create method printAll() that prints all names in list from first to last (one per line)

Websheet: MonkeyTraverse

Visualization

Insertion at start

first.next.next.... = S is not sustainable

Easier to first tackle insertion at start of list

private void addStart(String newName) {
   Node newFirst = new Node(newName);
  
   // this won't work
   first = newFirst;
   // no matter what comes after it :(
}

(Diagram on board)

Let's fix it! Websheet: MonkeyAddStart

Insertion at end

Alternative to first.next.next...

Must loop (like printAll()), stop just before the end, then add the new node.

Special case will be needed

Websheet: MonkeyAddEnd

Homework

Write void swapFirstTwo() to swap first two nodes

Write Node findKth(int k) to retrieve kth node

Write fast code to insert at end by remembering last node