SE250:lab-4:npit006

Linked Listed Length() Function

This was quite a simple operation to implement... it simply involves working through the list until nil is reached.

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

Linked List Indexing Functions

Fairly straightforward again. If n is too big, the program won't crash since the nil cons cell will continually redirect to itself.

element_t first(Cons* list){
	return list->head;
}

element_t second(Cons* list){
	return list->tail->head;
}

element_t third(Cons* list){
	return list->tail->tail->head;
}

element_t fourth(Cons* list){
	return list->tail->tail->tail->head;
}

element_t nth(int n,Cons* list){
	int i; 

	for (i=1;i<n;i++){
		list = list->tail;
	}

	return list->head;
}

Linked List Equal Function

Very straightforward... do a preliminary check for equal lengths, then work through the lists comparing each head value.

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

	return 1;
}

Linked List Find Function

Simple.

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

	return nil;
}

Linked List Copy_List Function

I breezed through the lab up until this point. The problem here was that we naturally read through list from the start to the finish, but when forming another linked list, we naturally write it from the finish to the start.

So my solution was to read from start to finish but also write the duplicate from start to finish. So I assign the first cons cell to duplicateList which remains untouched thereafter as it is required to the point the new linked list. From then on, I connect the tail of the previous Cons cell to the current cons cell until the whole list is copied.

I'm sure a much simpler solution exists, but I'll give that some thought later.

Cons* copy_list(Cons* list){
	Cons *duplicateList, *previousCons, *currentCons;
	
	if (list==nil) return nil;

	previousCons = currentCons = duplicateList = cons(list->head,nil);   
	list=list->tail;

	while (list!=nil){
		currentCons = cons(list->head,nil);
		previousCons->tail = currentCons;
	
		list = list->tail;
		previousCons = currentCons;
	}

    return duplicateList;
}

Linked List Append/nAppend Function

This was fairly straightforward but required a bit of clarification. In order to append list2 to list1 without altering either, a copy of list1 has to be made and linked to list2. List2 can be used in the new list while being available as list 2 as well.

So the basic idea is to clone list1 and retain a reference (segment1), then move through list1 until we anticipate a tail pointing to a nil cell. Once we find it, replace it with a link to list2 and return our reference to the new list.

Cons* append(Cons* list1, Cons* list2){
	Cons *cellPointer,*segment1;
	
	if (list1==nil) return list2;

	cellPointer = segment1 = copy_list(list1);
		
	while (cellPointer->tail!=nil){
		cellPointer = cellPointer->tail;
	}

	cellPointer->tail = list2;
		
	return segment1;
}

nAppend() was simpler to implement than Append for the simple reason that we don't have to clone list1. All we have to do is iterate through it until we find the end and link it to list2.

Cons* nappend(Cons* list1, Cons* list2){
	Cons *cellPointer = list1;
	
 	if (list1==nil) return list2;
	
	while (cellPointer->tail!=nil){
		cellPointer = cellPointer->tail;
	}

	cellPointer->tail = list2;
		
	return list1;
}

Linked List Reverse/nReverse Functions

Since we were required to create a new linked list from the input list, this has a similar structure to copy_list(). But this is even easier because of the fact that it's natural to read a LL from start to end but write one from end to start. Therefore, the reversal of elements has already been done for us. We can simply write to the new LL as we read from the old one.

Cons* reverse(Cons* list){
	Cons *reverseList = cons(list->head,nil);

	while (list->tail!=nil){
		list = list->tail;
		reverseList = cons(list->head,reverseList);
	}

	return reverseList;
}

This was more difficult than reverse() and indeed any of the other functions. This involved reversing the linked list while using the same cells. Due to the fact that linked lists have to be sequentially read, it could never be as simple as swapping element 1 with n-1 and 2 with n-2 etc. (as we could with an array).

My strategy was to leave the head parts as they were and simply reverse the direction of the pointers so that B points to A instead of A pointing to B. But that was slightly more difficult in practice... I'd have to keep track of the cells I'd moved past with a previous pointer.

To start with, the reverse array should end with a nil cons cell, so I assigned nil to previous. With each loop iteration, I set the next (the next element to be dealt with) to where the current one pointed, told the tail to point the other way (in the previous direction) and moved through by assigning current to previous and next to current until a nil cell was anticipated. Since previous = current anticipates the next loop iteration, I have to return previous to return the current one before the loop finished.

Cons* nreverse(Cons* list){
	Cons *previous, *current, *next;

	current = next = list;
	previous = nil;
	
	while (next!=nil){
		next = current->tail;
		current->tail = previous;
		previous = current;
		current = next;
	}

	return previous;
}

Overview

This lab was mostly straightforward, but a bit tricky when it came to some functions. One problem I had was designing my program so that the test case source and the linked list source would work together. As per last year's teaching, I was easily able to insert the Cons structure, preprocessor directives and function prototypes into the header file. But including the nil/NIL definitions in the header was causing the compiler trouble, so upon further research, I found I could declare them with the 'extern' keyword in the header and define them in LL.c.