Permalink
Find file
Fetching contributors…
Cannot retrieve contributors at this time
124 lines (89 sloc) 4.46 KB
= Linked Lists =
If we store our arrays on the heap and use `realloc` we can get dynamically-sized lists of data (called vectors). Can we implement Haskell-style lists that are composed on linked-together cells? Well, if we look at a Haskell list definition:
data List a = Nil | Cons a (List a)
Each cell is a value and another cell:
struct list {
void *data;
struct list *next;
}
How should we specify that there is no next cell (like Nil from the Haskell definition)? We can use the special reserved pointer value NULL (which is address 0).
What is the `void *`? How can we point to nothing? Well, since every pointer value is the same size, the compiler doesn't actually need to know what sort of pointer it is to store the value. A `void *` is a way of telling the compiler "just forget about what sort of data this points at". The developer must remember what sort of data it is, and switch back to a specifically typed pointer before any pointer arithmetic or dereferencing will work. This is similar to the parametric polymorphism we use in Haskell, in that we can operate on the structure without knowing the type of the values, but when we do want to operate on the values the compiler cannot help us, and we must explicitly state the correct type.
#include <stdlib.h>
struct list *cons(void *data, struct list *next) {
struct list *new = malloc(sizeof(*new)); /* Should check return for NULL */
new->data = data;
new->next = next;
return new;
}
int main(int argc, char *argv[]) {
struct list *lst, *iter;
int a = 5, b = 12, c = 24;
/* WARNING: do not let a, b, c go out of scope */
lst = cons(&a, cons(&b, cons(&c, NULL)));
iter = lst;
for(iter = lst; iter; iter = iter->next) {
printf("%d\n", *(int*)(iter->data));
}
/* You should free the list */
return EXIT_SUCCESS;
}
The `for` construct here is very similar to the `while` loops we've seen before. In fact, a `for` loop can always be translated into a `while` loop in the following way:
for(expr1; expr2; expr3) statement;
expr1; while(expr2) {statement; expr3;}
== Doubly-linked ==
The lists we've seen so far are also called singly-linked lists. This is because you can only traverse them on one direction: forwards. Given any particular cell you can only see cells that come after it. What if we wanted to be able to go in both directions?
struct dbl_list {
void *data;
struct dbl_list *prev;
struct dbl_list *next;
};
struct dbl_list *incons(void *data, struct dbl_list *prev, struct dbl_list *next) {
struct dbl_list *lst = malloc(sizeof(*lst)); /* Should check return for NULL */
lst->data = data;
lst->prev = prev;
lst->next = next;
if(next) {
next->prev = lst;
}
if(prev) {
prev->next = lst;
}
return dbl_list;
}
struct dbl_list *cons(void *data, struct dbl_list *next) {
return incons(data, NULL, next);
}
void print_prev_next_int(struct dbl_list *lst) {
if(lst->prev) {
printf("PREV: %d\n", *(int*)(lst->prev->data));
}
printf("%d\n", *(int*)(lst->data));
if(lst->next) {
printf("NEXT: %d\n", *(int*)(lst->next->data));
}
}
int main(int argc, char *argv[]) {
struct list *lst, *iter;
int a = 5, b = 12, c = 24;
/* WARNING: do not let a, b, c go out of scope */
lst = cons(&a, cons(&b, cons(&c, NULL)));
print_prev_next_int(lst->next);
/* You should free the list */
return EXIT_SUCCESS;
}
== Trees ==
Lists are just a special case of trees. A tree starts at some node (the "head" or "root") and can have one or more "child" nodes. If a tree always has just one "child" then we call that a list. If a tree always has two children we call it a binary tree:
struct binary_tree {
void *data;
struct binary_tree *left;
struct binary_tree *right;
};
If each node can have an arbitrary number of children, we call that a rose tree:
struct rose_tree {
void *data;
struct rose_tree **children;
};
A "level" of a tree is defined by the distance from the nodes at that level to the root. So the root node is at level 0, it's children are at level 1, etc.
A "balanced" tree is a tree where every level except the bottom-most is full (this only makes sense for tree with fixed number of children per node).
The "height" of a tree is the number of levels in the tree.
Many specific uses of trees require various structural properties to be maintained (such as "the tree is always balanced", or "children on the left of a node have lower values than the value at the node"), which can make constructing them more or less complex.