Linked List Example

llfunb.c

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

struct boxtype
{
	int val;
	struct boxtype *link;
};

struct boxtype *makeNode(int x)
{
	struct boxtype *tmp;
	tmp = malloc(sizeof(struct boxtype));
	tmp->val = x;
	tmp->link = NULL;
	return tmp;
}

int listLength(struct boxtype *front)
{
	int len = 0;
	// ptr to a link within a struct
	struct boxtype *mov;
	// set the ptr to the first struct
	mov = front;
	// while the link isn't null
	while (mov != NULL)
	{
		// add 1 to len
		len++;
		// traverse to the next struct
		mov = mov->link;
	}

	return len;
}
int maxVal(struct boxtype *nodes)
{
	int *valpoint;
	// set the inital max value
	// to zero as it's small
	int max = 0;
	// traverse while we have nodes
	while (nodes != NULL)
	{
		// if our max value
		// is less than the node value
		if (max < nodes->val)
		{
			// set the max value
			// to the node value
			max = nodes->val;
		}
		// traverse to the next node
		// by setting our current node
		// to the pointer of the next one.
		nodes = nodes->link;
	}
	// return the max value.
	return max;
}
struct boxtype *maxLoc(struct boxtype *nodes)
{
	struct boxtype *max;
	// make a single struct with an
	// initial value of 0
	max = makeNode(0);
	// traverse while we have nodes
	while (nodes != NULL)
	{
		// if our max value is less
		// than the node value
		if (max->val < nodes->val)
		{
			// move our "max" node to point
			// at the "nodes" node containing
			// the maximum value.
			max = nodes;
		}
		// traverse to the next node
		nodes = nodes->link;
	}
	// return the pointer "max"
	// which is the location
	// of the node containing the
	// maximum value.
	return max;
}
int isEmpty(struct boxtype *node)
{
	if (node == NULL)
	{
		// list is empty
		return 1;
	}
	// list is not empty
	return 0;
}
int isInList(struct boxtype *first, int num)
{
	struct boxtype *traverse;
	traverse = first;
	while (traverse != NULL)
	{
		if (traverse->val == num)
		{
			return 1;
		}
		else
		{
			traverse = traverse->link;
		}
	}
	return 0;
}
struct boxtype *getLoc(struct boxtype *front, int num)
{
	struct boxtype *valpoint;
	struct boxtype *traverse;
	// point "traverse" to the location of the
	// "front" node (not really needed)
	traverse = front;
	// while we have nodes
	while (traverse != NULL)
	{
		// if the value of the node equals
		// the number we're searching for
		if (traverse->val == num)
		{
			// point the "valpoint" node
			// equal to the location of
			// the "traverse" / "front" node
			valpoint = traverse;
		}
		// traverse down the list
		traverse = traverse->link;
	}
	// return valpoint which contains
	// the pointer to where the value is
	return valpoint;
}
void printList(struct boxtype *front)
{
	struct boxtype *walk;
	walk = front;
	while (walk != NULL)
	{
		printf("%d ", walk->val);
		walk = walk->link;
	}
	printf("\n");
}
struct boxtype *insertBack(struct boxtype *first, int num)
{
	struct boxtype *last, *node;
	// verify that first element is null
	if (first != NULL)
	{
		// set last  = first &
		//  make a node
		last = first;
		node = makeNode(num);
		// while the link isn't null
		while (last->link != NULL)
		{
			// traverse to end
			// of link
			last = last->link;
		}
		// set the link of the last element
		// to our new node struct
		last->link = node;
	}
	else
	{
		// make the first node
		// because the first element
		// doesnt exist
		first = makeNode(num);
	}
	return first;
}
struct boxtype *insertFront(struct boxtype *first, int num)
{
	struct boxtype *node;
	node = makeNode(num);
	node->link = first;
	first = node;
	return first;
}
struct boxtype *insertAfter(struct boxtype *start, struct boxtype *loc, int val)
{
	struct boxtype *node, *after;
	after = start;
	while (after != NULL)
	{
		// check if our location
		// is = to the location of the
		// struct we want to remove
		if (after == loc)
		{
			// create new struct node
			node = makeNode(val);
			// set the link of the new node
			// to the link that the one before
			// was pointing to
			node->link = after->link;
			// now point the one before to our new node
			after->link = node;
			// break the while loop.
			break;
		}
		// continue traversing
		after = after->link;
	}
	return start;
}
struct boxtype *removeThisOne(struct boxtype *start, struct boxtype *loc)
{
	struct boxtype *traverseBehind, *rmLoc;
	// verify first element exists
	if (start != NULL)
	{
		int count = 0;
		rmLoc = start;
		traverseBehind = start;
		// if the list only contains 1 item that has no link, then this
		// function must have been called to remove the single item
		if (rmLoc->link == NULL)
		{
			start = NULL;
		}
		// while we're not at the end

		while (rmLoc != NULL)
		{
			// check if list has only 1 struct
			if (listLength(rmLoc) == 1)
			{
				//remove the one item
				rmLoc = NULL;
				break;
			}
			if (listLength(rmLoc) == 2)
			{
				//remove the one item
				rmLoc->link = NULL;
				break;
			}

			// check if location is at the beginning of the list
			if (count == 0 && rmLoc == loc)
			{
				start = rmLoc->link;
				break;
			}
			// if it's not at the beginning of the list
			// check if equal
			if (rmLoc == loc)
			{
				// set the last node to the node after rmLoc
				// thus removing the rmLoc node
				traverseBehind->link = rmLoc->link;
				break;
			}

			// continue traversing
			rmLoc = rmLoc->link;
			if (count > 0)
			{
				// traverse 1 behind the "rmLoc" node
				traverseBehind = traverseBehind->link;
			}
			count++;
		}
	}
	return start;
}

struct boxtype *removeBack(struct boxtype *first)
{
	struct boxtype *traverse;
	struct boxtype *traverseBehind;
	if (first != NULL)
	{
		int count = 0;
		traverse = first;
		while (traverse->link != NULL)
		{
			count++;
			if (count == 1)
			{
				// set this node to 1 struct before
				// the normal traverse node
				traverseBehind = first;
			}
			// continue traversing down nodes until
			// we find the last one.
			traverse = traverse->link;
			if (count > 1)
			{
				// continue traversing down nodes
				// 1 behind the "traverse" node
				traverseBehind = traverseBehind->link;
			}
		}
		// This will set the link to
		// the last struct = NULL
		// thus removing it.
		traverseBehind->link = NULL;
	}
	return first;
}
struct boxtype *removeFront(struct boxtype *first)
{
	struct boxtype *next;
	// validates if there's more
	// than one element
	if (first->link != NULL)
	{
		// point our next node
		// to the next element
		// in the "first" list
		next = first->link;
	}
	// if there's only one element in the list
	if (first->link == NULL)
	{
		// remove it
		next = NULL;
	}
	// point "first" to the "next"
	// node which has removed the first element
	first = next;
	// return it.
	return first;
}
int main()
{
	struct boxtype *b, *start;
	int i, x;

	start = NULL;

	for (i = 0; i < 10; ++i)
	{
		x = rand() % 100;
		if (x % 2 == 0)
			start = insertFront(start, x);
		else
			start = insertBack(start, x);
		printList(start);
	}
	printf("Len %d\n", listLength(start));

	while (!isEmpty(start))
	{
		x = start->val;
		printf("%d\n", x);
		start = removeFront(start);
		printList(start);
	}

	while (!isEmpty(start))
	{
		start = removeBack(start);
		printList(start);
	}

	int mv;
	struct boxtype *ml;
	while (!isEmpty(start))
	{
		mv = maxVal(start);
		ml = maxLoc(start);
		printf("big  %d\n", mv);
		start = removeThisOne(start, ml);
		printList(start);
	}

	return 0;
}