SE250:March 20

Minutes

Minute taker: dols008

Hypertext textbook

The hypertext textbook page is up on the wiki.

Add drafts to the work in progress section of the textbook. Production quality stuff will be taken from the work in progress section and put in the final version, with added polish. More names are needed from people committing to doing sections. There is a table on the wiki you can add your upi to. It is possible to change your mind later.

We're starting a new topic. Between now and next lab we'll get started on both linked lists and hashing.

Linked lists

The building block of a linked list is a "cons cell" (so named for historical reasons). It has two parts, a payload (your value/data) and a pointer, which points to the next cons cell. The pointer contained in the final cons cell is set to nil to indicate that there is nothing following it.

Linked lists have different properties to array based lists. Array based lists are in a big contiguous block of memory. This makes it very expensive to add items to the front of the list. It's much cheaper to insert elements in a linked list, because the existing items don't have to be moved. You can just change the pointers in two of the existing cells to splice the new element in. Linked lists have very different performance characteristics as compared with array based lists.

Writing a linked list

A struct for a linked list would be a typical exam question.

struct {
  element_t value;
  ???* next;
}

What should the type of the pointer be? What if it was element_t*? It would point to the value of the next cons cell, but you couldn't access the pointer in that cell. It needs to be a pointer to a cons cell.

typedef int element_t;

typedef
struct Cons {
  element_t value;
  struct Cons* next;
} Cons;

When the C compiler looks at the "next" variable, it hasn't yet read the entire declaration of Cons, so it doesn't know exactly what a Cons is. But it knows Cons* is a pointer, and that's enough to know how big it is.

Using cons cells

Cons *nil = 0; // Not necessary, but improves readability.

int main() {
  Cons c1, c2, c3;

  c1.value = 1;
  c2.value = 2;
  c3.value = 3;

  c1.next = &c2;
  c2.next = &c3;
  c3.next = nil;

  return 0;
}

Setting c1.next to the address of c2 gives us the link between c1 and c2. c2 is linked to c3 similarly. c3.next is set to nil to indicate that it's the end of the list. It's not necessary that we call it nil, but it differentiates the end of a list from just an integer 0 or an as-yet unused pointer, making our intent clear.

Printing out a list

First we rough out a simple version of the print_list function that will work perfectly for an empty list.

void print_list( Cons* list ) { // Must be a pointer, so that we can print empty lists.
  // Format it nicely.
  printf( "List[" );

  printf( "]" );
}

Testing our print_list function:

Cons *nil = 0;

int main() {
  Cons c1, c2, c3;

  c1.value = 1;
  c2.value = 2;
  c3.value = 3;

  c1.next = &c2;
  c2.next = &c3;
  c3.next = nil;

  print_list( nil ); /* expect: List[] */
  print_list( &c1 ); /* expect: List[1,2,3] */

  return 0;
}

It worked for the empty list, and printed the 3 item list as an empty list as expected.

Linked lists fit very well with a declarative style of programming with shared memory structures. We're not expected to understand that yet.

Filling out the list printing function:

void print_list( Cons* list ) {
  Cons *lp;

  printf( "List[" );
  for( lp = list; lp != nil; lp = lp->next )
    if ( lp->next == nil) // Avoid printing an extra comma.
      printf( "%d", lp->value );
    else
      printf( "%d,", lp->value );
  printf( "]" );
}

The magic is in the for loop. We initialise lp to point to the first cell in the list. If lp is not nil, we print the value stored in the cons cell and set lp to point to whatever that cell has as it's next. Repeat until lp is nill.

You could do the same using a while loop, like this:

lp = list;
while ( lp != nill ) {
  if (lp ->next == nil )
    printf( "%d", lp->value );
  else
    printf( "%d,", lp->value );
  lp = lp->next;
}

Meeting closed.

Dols008 20:18, 20 March 2008 (NZST)