CSC161 2010F, Class 47: Linked Lists (1)

Overview:
* Review: Entries in K&R Hash Tables
* Lists in Scheme
  * Implementation
  * Central Methods
* Representing pairs in C.
* A simple list API.
* ColLABorative

Admin:
* For tomorrow, please review the code from today's class.
* Exam 3 will be distributed tomorrow.
* Yes, we have class on Wednesday.
  * But if you have to leave early to avoid snow, I'll not be too cruel

What does a K&R-style hash table look like?
* An array of pointers to entries
struct entry *entries;
* Each entry is a linked collection of key/value pairs
struct entry {
  char *key;
  char *value;
  struct entry *next;
}

What is a Scheme list?
* A collection of elements
  * What's the picture of (a b c)?

We could probably represent these in C.
* But we're going to simplify a bit.
* We'll just let the car be a string

struct node {
  // What's in it
  char *data;
  // Pointer to the next one
  struct node *next;
};

Basic Scheme list operations
* car
* cdr
* cons
* null? (we might call it is_null; or just lst == NULL)
* One basic data value null (in C NULL)

List mutators
* set-car! (in C, set_car)
* set-cdr! (in C, set_cdr)

char *
car (struct node *um)
{
  return um->data;  
}

struct node *
cdr (struct node *um)
{
  return um->next;
}

struct node *
cons (char *str, struct node *rest)
{
  struct node *um;
  um = malloc (sizeof (struct node));
  if (um == NULL)
    {
      fprintf (stderr, "Out of memory!  Can't cons.\n");
      exit (42);
    }
  um->data = str;
  um->next = rest;
} // cons

struct node *
set_car (struct node *lst, char *str)
{
  lst->data = str;
  return lst;
} 

struct node *
set_cdr (struct node *lst, struct node *rest)
{
  lst->next = rest;
  return lst;
}

This is potentially dangerous because we have not freed the old cdr.
We can also have fun building looped structures.

Traditionally, we avoid these problems by "wrapping" the nodes in
another structure.

struct node *
append (struct node *lst, char *str)
{
  
}

Other things
* length