Imperative-Style Linked Lists

October 11, 2013

We will use the well-known imperative language C instead of our usual language Scheme, because writing Scheme like that would make me cry. The basic data type that implements lists is the List, which is a struct; we will hard-wire the data type as int, but you could change that to a pointer to void if you want to be more general:

typedef struct list {
void *data;
struct list *next;
} List;

Instead of providing nil and isNil, we will simply use the built-in NULL for nil and write xs == NULL or xs != NULL to determine if a List is nil. Likewise, getting the components of a pair is so simple we don’t bother to provide functions for them: the head of a list is xs->data and the tail of a list is xs->next.

The insert function adds a new pair to the front of a list by allocating space for the new pair, assigning a value and a pointer to its two fields, and returning the new pair:

List *insert(void *data, List *next) {
List *new;

new = malloc(sizeof(List));
new->data = data;
new->next = next;
return new;
}
Getting the nth item in a list, or counting the length of a list, involves chasing pointers down the list in a while loop. Since C doesn’t have a standard error return, we use our own error function, which writes a message to stderr then exits the program with a return value of 2:

int nth(List *xs, int n) {
while (n > 0) {
if (xs == NULL) {
error(“nth out of bounds”);
}
n–;
xs = xs->next;
}
return xs->data;
}

int length(List *xs) {
int len = 0;
while (xs != NULL)
{
len += 1;
xs = xs->next;
}
return len;
}

Append walks down its first argument, then modifies the NULL pointer at the end of the list to point to its second argument:

List *append(List *xs, List *ys) {
List *new = xs;

while (xs->next != NULL) {
xs = xs->next;
}

xs->next = ys;
return new;
}

Our last function is reverse, which is again destructive, modifying the current list in place by swapping pointers:

List *reverse(List *list) {
List *new = NULL;
List *next;

while (list != NULL)
{
next = list->next;
list->next = new;
new = list;
list = next;
}

return new;
}

We haven’t bothered to collect the garbage we created; shame on me. I admit some trouble programming with C; it’s so ugly compared to Scheme.

You can see the program in action at http://programmingpraxis.codepad.org/JQIFfqOX.

About these ads

Pages: 1 2

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 630 other followers

%d bloggers like this: