SE250:lab-4:dols008

Lab 4 - Linked Lists

I got off to a bad start with this lab, and messed up the length function. I had the terminating condition as list->tail != nil instead of list != nil. Didn't take too long to figure out though. Here's the result:

unsigned length( Cons* list ) {
    unsigned leng;
    for( leng = 0; list != nil; list = list->tail )
	++leng;
    return leng;
}

I just used unsigned because negative lengths obviously aren't possible. Moving on, I decided to write the first, second, etc. functions in terms of the nth function, because the nth function didn't seem that hard. For the nth function, I considered relying on the fact that nil.tail = &nil, but instead opted to write a version which gives up at the end of the list, like this:

element_t nth( unsigned index, Cons* list ) {
    unsigned i;
    for( i = 0; list != nil; list = list->tail, ++i )
	if( i == index )
	    return list->head;
    return 0;
}

The equals function didn't prove to be any trouble:

int equal(Cons* lhs, Cons* rhs) {
    for( ; lhs != nil && rhs != nil; lhs = lhs->tail, rhs = rhs->tail ) // Loop until either list ends
	if( lhs->head != rhs->head )
	    return 0; // If they have contain different data, return false.
    return lhs == nil && rhs == nil; // Return true if the lists are the same length
}

Find was ok too. It occurs to me now I could have simplified it slightly. Oh well.

Cons* find( element_t value, Cons* list ) {
    for( ; list != nil; list = list->tail )
	if( list->head == value )
	    return list;
    return nil;
}

I spent a bit of time thinking about copy list, but it looked like it was going to be a pain getting things in the right order. So I just did it the quick recursive way. I realised later I could have just created the list backwards and filled in the values with a second loop. But here's the recursive way:

Cons* copy_list( Cons* original ) {
    if( original == nil )
	return nil;
    return cons( original->head, copy_list( original->tail ));
}

Append would probably have been a good place to use a pointer to a pointer. But I didn't notice that at the time and ended up with a bit of a special case when xs = nil. Here's my code:

Cons* append( Cons* xs, Cons* ys ) {
    Cons* nxs = copy_list( xs );
    Cons* iter;
    for( iter = nxs; iter != nil; iter = iter->tail ) {
	if( iter->tail == nil ) { // If this is the last element in the list
	    iter->tail = ys; // Then point it's tail to the start of the second list.
	    return nxs;
	}
    }
    return ys; // xs must be nil
}

Nappend was the same but without the copy.

Cons* nappend( Cons* xs, Cons* ys ) {
    Cons* iter;
    for( iter = xs; iter != nil; iter = iter->tail ) {
	if( iter->tail == nil ) {
	    iter->tail = ys;
	    return xs;
	}
    }
    return ys; // xs is nill
}

Reverse was like copy but without the issue of switching the order of everything.

Cons* reverse( Cons* xs ) {
    Cons* newList = nil;
    for( ; xs != nil; xs = xs->tail )
	newList = cons( xs->head, newList );
    return newList;
}

Nreverse finally made me stop, think and draw a diagram. In the end I did it similarly to how I had first thought about doing copy. The idea is that you go through the list setting each cells tail to the item that came before it. But you have to make a note of the cell that comes next before you overwrite it with the previous.

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