CSC161 2010F, Class 48: Linked Lists (2)

Overview:
* Problems with basic node structures.
* A solution: Wrapping nodes.
* An API.
* Implementing basic operations.
* Deletion.

Admin:
* Exam 3 is now ready.  
  * Typos are likely.
  * I will reward those who attend class today with a solution to one
    exam problem of their choice.
* Have a great Turkey break 
  * Even if you're already in Smallpop
* Coming up: Doubly linked lists 

Problems with basic node structures:
* Duplicate links create sharing problems
* Loops
* Collecting "garbage" can be hard.

Solution:
* Build a wrapper struct that hides the underlying nodes.
struct list {
  struct node *head; // The first element in the list
  struct node *tail; // The last element in the list
  int length;
}

API
* Append something to the end of the list
  list_append (struct list *lst, char *str);
* Find the length
  list_length (struct list *lst)
* Find the first element
  list_first (struct *list *lst)
* Add something to the front
  list_prepend (struct list *lst, char *str)
* Print it out
  list_print (struct list *lst)
* Delete something from the list
  list_delete (struct list *lst)

How do we implement prepend?

How do we implement print