Header File

/************************************************
 *
 * Header for linked list program
 *
 * A list is a pointer to a node. A node is
 * a simple struct with an integer field and
 * a pointer to the next node. The list has
 * a head node with no data and the real list
 * starts with the second node (if there is
 * one.)
 *
 * This list is a circular list, the last item
 * points at the head node.
 *
 * Peter Casey 11/30/00
 *
 ************************************************/

struct node {
	int data;
	struct node *next;
};

typedef struct node  NODE;
typedef struct node *LIST;

/**************************************************
 *  Create a new list.
 *
 *  input: size - the number of items in the list
 *
 *  return: A LIST is returned (or NULL)
 *************************************************/
LIST createList(int size);

/**************************************************
 *  Add a new node to the list with item as
 *  the data.
 *
 *	input: head - the list
 *		   item - the data
 *************************************************/
void addItemToList(LIST head, int item);

/**************************************************
 *  Find the last item in the list
 *
 *  return a pointer to the last item or NULL
 *************************************************/
LIST findLastItem(LIST head);

/**************************************************
 *  Create an empty list with only a head node.
 *
 *  return: A LIST with no items in it.
 *************************************************/
LIST createEmptyList();

/**************************************************
 *  Search a list for a particular item.
 *
 *  input:  head   - the list to search
 *          target - the item to search for
 *
 *  return: A LIST containing the item found
 *					(or NULL if not found)
 *************************************************/
LIST search(LIST head, int target);

/**************************************************
 *  Delete an item from the list.
 *
 *  input:  head - The list
 *		    item - The item before the item
 *				   to delete
 *
 *  The item is a pointer to the item before the
 *  one to delete. This allows an easy delete by
 *  reseting items next pointer to jump over the
 *  actual item to delete.
 *
 *	You must search for a value in the list and
 *	get back the pointer before you can delete.
 *
 *	You could write a helper function to do both
 *  actions at once.
 *************************************************/
 void deleteItem(LIST head,
			     LIST item);

/**************************************************
 *  Print a list.
 *
 *  input: head - The list to print
 *
 *************************************************/
 void printList(LIST head);

C Source File

/****************************************************
 *
 * Linked List example.
 *
 *   Not fully tested but works for the basics.
 *
 *	 Look in the header file for more info.
 *
 * Peter Casey 11/30/00
 *
 *****************************************************/

#include <stdio.h>
#include <stdlib.h>
#include "linked_list.h"

#define TARGET     2
#define LIST_SIZE  7

void main() {
	LIST listHead;
	LIST item;
	int target = TARGET;

	listHead = createList(LIST_SIZE);
	printList(listHead);

	item = search(listHead, target);

	if (item != NULL) {
		int data;

		data = item->next->data;
		printf("found item, value is %d\n", data);
		deleteItem(listHead, item);
	}
	else
		printf("%s\n", "item not found");

	printList(listHead);
	addItemToList(listHead, 10);
	printList(listHead);
}

void addItemToList(LIST head, int item) {
	LIST newItem = malloc(sizeof(NODE));
    LIST lastItem;

    if (head == NULL) {
	   head = createEmptyList();
	}

	lastItem = findLastItem(head);

	newItem->data = item;

	if (lastItem == NULL) {
		head->next = newItem;
	}
	else {
		lastItem->next = newItem;
	}

	newItem->next = head;
}

LIST findLastItem(LIST head) {
	LIST mover = head->next;

	if (mover != NULL) {
		while (mover->next != head) {
			mover = mover->next;
		}
	}

	return mover;
}

LIST createEmptyList() {
	LIST empty = malloc(sizeof(NODE));

	empty->next = NULL;

	return empty;
}

LIST createList(int size) {
	LIST list;
	LIST mover;
	int counter;

	if (size > 0) {
		list = createEmptyList();
		mover  = malloc(sizeof(NODE));

		list->next = mover;
		mover->data = 1;

		for (counter = 2 ; counter <= size; counter++) {
			mover->next = malloc(sizeof(NODE));
			mover = mover->next;
			mover->data = counter;
		}

		mover->next = list;
	}

	return list;
}

LIST search(LIST head, int target) {
	int found = 0;
	LIST mover = head;

	if (mover != NULL) {
		found = (mover->next->data == target);

		while (!found && (mover->next->next != head)) {
			found = (mover->next->data == target);
			if (!found) {
				mover = mover->next;
			}
		}
		if (!found) {
			found = (mover->next->data == target);
		}
	}

	if (found)
		return mover;
	else
		return NULL;
}

void deleteItem(LIST head,
			    LIST item) {

	if (item != NULL) {
		LIST temp = item->next;
		item->next = temp->next;
		free(temp);
	}

	return;
}

void printList(LIST head) {
	LIST mover = head->next;

	if (mover != NULL) {
		printf("%d\n", mover->data);
		mover = mover->next;
		while (mover != head) {
			printf("%d\n", mover->data);
			mover = mover->next;
		}
	}
	else {
		printf("%s\n", "empty list");
	}
}