SE250:lab-4:Maintainers report

Introduction

Linked lists are a way to store data with structures so that the programmer can automatically create a new place to store data whenever necessary. Specifically, the programmer writes a struct or class definition that contains variables holding information about something, and then has a pointer to a struct of its type. Each of these individual struct or classes in the list is commonly known as a node.

C-Programming Website

Analysis

This lab tested our understanding on Linked Lists. We were introduced to the code in the lecture and had to use that knowledge to write the fuctions.

Most of the class was comfortable with the first few functions and had similar codes for them:

Length Function

Write a function int length(Cons*) to return the number of elements in the list.

int length(Cons* list) {
	int length = 0;

	for( ; list != nil; list = list->tail ) {
		length++;
	}

	return length;
}

Returning element in named position

The most commonly used code for this was as follows:

//To return the element in the first position
element_t first(Cons* list) {
	return list->head;
}

 //To return the element in the second position
element_t second(Cons* list) {
	return list->tail->head;
}

//To return the element in the third position
element_t third(Cons* list) {
	return list->tail->tail->head;
}

//To return the element in the fourth position
element_t fourth(Cons* list) {
	return list->tail->tail->tail->head;
}

nth element

Few of the students found the nth element function hard to write. This was perhaps due to lack of clear understanding of linked lists. But eventually, everyone did manage to finish the task.

So common code for the function was:

element_t nth(int i, Cons* list) {
    int n;
    for (n=0; n < i; n++) {
        list = list->tail;
    }
    return list->head;
}

Equal function

This just compared the two linked lists to see if they had exactly the same elements in identintical order. This question was well received among the students. The code was:

int equal(Cons* list, Cons* list2) {
    while((list != nil) | (list2 != nil)) {
	if (list->head != list2->head)
	    return 0;
	list = list->tail;
	list2 = list2->tail;
     }
    return 1;
}

Find Function

It started to get a little more complicated and required more thought from this point onwards.

The code was:

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

	return nil;
}

Copy Function

Several student did not get up to this question at all as the previous ones were time consuming. However, the students who did attempt this question found it hard and required assistance to complete it.

Cons* copy_list(Cons* list) {
	Cons *newList, *currentElement, *previousElement;

	if (list == nil) {
		return list;     edit: Should we be returning newList here? Otherwise it isn't a copy.
	} else {
 		newList = cons(list->head, nil); 
  		list = list->tail;
  		previousElement = newList;
  
 		for ( ; list != nil; list = list->tail) {
  			currentElement = cons(list->head, nil);
			previousElement->tail = currentElement;
			previousElement = currentElement;
		}
  
 		return newList;
	}
 }

Append

Not too many students managed to finish it. However Braedon's code was:

Cons* append(Cons* list1, Cons* list2) {
	Cons *newList, *currentElement, *previousElement;

	if (list1 == nil) {
		return list2;
	} else {

		newList = cons(list1->head, nil);
		list1 = list1->tail;
		previousElement = newList;

		for ( ; list1 != nil; list1 = list1->tail) {
			currentElement = cons(list1->head, nil);
			previousElement->tail = currentElement;
			previousElement = currentElement;
		}

		for ( ; list2 != nil; list2 = list2->tail) {
			currentElement = cons(list2->head, nil);
			previousElement->tail = currentElement;
			previousElement = currentElement;
		}

		return newList;

	}

} 

nappend

Not too many got this far. Braedon's code seemed to be the most comprehendable code of them all. Thus, we have decided to use his code:

 Cons* nappend(Cons* list1, Cons* list2) {
 	Cons *newList;
 
 	if (list1 == nil) {
 		return list2;
 	} else {
 
  		newList = list1;
 
 		for ( ; list1->tail != nil; list1 = list1->tail);

 		list1->tail = list2;
 
 		return newList;

 	}
 } 

Reverse

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

nreverse

This was very complicated and only few students managed it.

The following code is Rajitha's:

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;
}

Conclusion

The lab was quite long and many students weren't able to finish the entire lab. Most of them got only half way through it. However, it was a good lab but the unanimous opinion was that more briefing be done before the lab so that everyone had a clear idea as to what was to be done instead of wasting lab time to understand concepts. Although the code was briefly explained in the lecture, it would be more helpful if the 'LL.c' was explained at the beginning of the lab.