SE250:lab-4:rwan064

Introduction

This lab was about implementing methods to create, modify and print Linked Lists.

All the code made in the lab available HERE

Implementing Linked Lists

Below is the code (that was given) that defines what an element is and also the structure of a Cons cell. It also defines the nil cell which is used to define the end of a list and also an empty list.

typedef int element_t;

typedef
struct Cons {
  element_t head;
  struct Cons* tail;
} Cons;

static Cons NIL = { 0, &NIL };
Cons* nil = &NIL;

When writing the functions that work with the Linked Lists it helps to draw images of the Cons cells to visualize what happens with the pointers, as shown below.

File:List.jpg

The order in which I did the functions made it simpler to do the later functions because they would use the previous ones. e.g. the element_t nth(int i, Cons* ) function used the int length( Cons* ) function to check if the i'th value actually exists in the list. It also makes the functions simpler and easier to read and debug.

• Finding the length of a List

int length( Cons *list )
{
    Cons *cp;
    int i = 0;
    for ( cp = list; cp != nil; cp = cp->tail ) {
        i++;
    }
    return i;
}

This function is very simple. You just go through the List as you do in the void print_list( Cons* ) function, except that you have a variable that is incremented by one each time you access an element in the list. Hence the counter will be equal to the number of elements in the list and that number is returned.

• Finding the nth element of a List

element_t nth( int i, Cons *list )
{
    if ( length( list ) >= i ) {
        Cons *cp = list;
        int count;
        for ( count = 0; count < (i-1); count++ ) {
            cp = cp->tail;
        }
        return cp->head;
    }
    else {
        return 0;
    }
}

This function uses the previously defined int length( Cons* ) function to check if there can be an ith element in the list specified. Then a for loop is used to go through the list (i - 1) times (because the you only need to call cp->tail once for the 2nd element, twice for the third and so on) and the value (cp->head) at that Cons cell is returned.

• Checking if two Lists are equal

int equal( Cons *xs, Cons *ys )
{
    if ( length( xs ) == length( ys ) ) {
        Cons *cp;
        int i = 1;
        for ( cp = xs; cp != nil; cp = cp->tail ) {
            if ( cp->head != nth( i, ys ) ) {
                return 0;
            }
            i++;
        }
        return 1;
    }
    else {
        return 0;
    }
}

• Destructively reversing the List

Cons *nreverse( Cons *xs )
{
    Cons *prev = xs;
    Cons *cp = xs->tail;
    prev->tail = nil;
    while ( cp != nil ) {
        Cons *t = cp->tail;
        cp->tail = prev;
        prev = cp;
    cp = t;
    }
    return prev;
}

File:Nreverse.jpg

As illustrated in the image above, I used three variables to keep track of the elements in the List. prev remembers the previous element in the list, cp is the current element and t is the next element in the list. The code simply reverses the pointers and returns the last element in the List. Which effectively reverses the list without allocating any new memory.

Conclusions

Overall the lab was short and simple. The code got harder to write at the end but drawing diagrams and visualizing the pointers really helped understand what was happening. All the functions are very similar in that it uses the same basic code to go through the List.

One of the most important things I learned from this lab was that drawing diagrams of pointers, variables and structures really helps in not just writing the code but also debugging. It also helps in making the code as simple as possible.