0440949 Andreas van Cranenburgh
opdr week 2 Datastructuren

C4.3
Algorithm concatSList(l, m):
	#input: two lists l and m.
	#output: the concatenated list
	getLastNode(l).next = m.next
	return l.header

#note: this algorithm will modify list l, but avoiding this seems to be
#	beyond the scope of this exercise.

getLastNode(node):
	#input: a node
	#output: the last node
	if node.next == NULL:
		return node
	else:
		return getLastNode(node.next)

The running time seems to be O(l), since the only thing that has to be done is
to find the last node of l, the length of list m doesn't matter. The rest of
the operations are constant so they are to be ignored for the running time.

C4.4
Algorithm concatSList(l, m)
	#input: two lists l and m.
	#output: the concatenated list
	temp = getLastNode(l)
	temp.next = m.next
	m.previous = temp
	l.trailer = m.trailer
	return l.header

Again the running time is O(l), the only difference is that there are more constant instructions, which don't prolong the running time. Note: getLastNode is the same as the one given before.

C4.13
Algorithm countList(node):
	#input: a node to start from.
	#output: the length of the list starting from node.
	if node.next == NULL:
		return 1
	else:
		return 1 + countList(node.next)