============================================================================
           Faculty of Applied Science and Engineering, University of Toronto
                     CSC181: Introduction to Computer Programming, Fall 2000

Tutorial Notes, Week 7
============================================================================

-----------------
Summary of Topics
-----------------

- Linked lists

-------
Example
-------

The following program models an integer list with the following
operations:

- init(): Returns an empty list.

- append(l, d): Appends integer d to list l; that is, it adds it to
  the end of l.

- get(l, i): Returns the element at index i in list l. The elements
  are indexed similar to an array, with the first element at 0 and the
  last element at n-1, where n is the size of the list.

- contains(l, d): Returns true if l list l contains integer d, false
  otherwise.

- size(l): Returns the size of the list.

The underlying data structure of the list is a singly-linked list.

----
Code
----

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>

struct listnode {
	int data;
	struct listnode* next;
};
typedef struct listnode ListNode;
typedef ListNode* ListNodePtr;

struct list {
	struct listnode* front;
	int size;
};
typedef struct list List;
typedef List* ListPtr;

ListPtr listInit(void) {
	ListPtr result = (ListPtr)malloc(sizeof(List));
	assert(result != NULL);

	result->front = NULL;
	result->size = 0;
	return result;
}

void listAppend(ListPtr l, int data) {
	ListNodePtr newNode;
	assert(l != NULL);

	newNode = (ListNodePtr)malloc(sizeof(ListNode));
	assert(newNode != NULL);

	newNode->data = data;
	newNode->next = NULL;

	if (l->front == NULL) {
		l->front = newNode;
	}
	else {
		ListNodePtr current = l->front;
		while (current->next != NULL) {
			current = current->next;
		}
		current->next = newNode;
	}

	l->size++;
}

int listGet(const ListPtr l, const int i) {
	int j;
	ListNodePtr current;
	assert(l != NULL);
	assert(0 <= i && i < l->size);

	for (j = 0, current = l->front; 
		j != i && current != NULL; 
		j++, current = current->next) ;

	return current->data;
}

int listContains(const ListPtr l, const int data) {
	ListNodePtr current;
	assert(l != NULL);

	for (current = l->front; current != NULL; current = current->next) {
		if (current->data == data)
			return 1;
	}

	return 0;
}

int listSize(const ListPtr l) {
	assert(l != NULL);
	return l->size;
}

int main(void) {
	ListPtr l = listInit();
	int i;

	listAppend(l, 2);
	listAppend(l, 5);
	listAppend(l, 7);
	listAppend(l, 6);

	printf("Contents of l:\n");
	for (i = 0; i != listSize(l); i++) {
		printf("%d\n", listGet(l, i));
	}
	printf("--\n");

	printf("Does l contain 7? %s\n", listContains(l, 7) ? "yes" : "no");
	printf("Does l contain 3? %s\n", listContains(l, 3) ? "yes" : "no");
	printf("--\n");
	
	return 0;
}

---
Run
---

Contents of l:
2
5
7
6
--
Does l contain 7? yes
Does l contain 3? no
--