Circular Linked Lists

The problem with a linear linked list is that given a point p to a node we cannot reach any of the nodes that precede it. Also, when we traverse the list, an external pointer to the list must be preserved in order to be able to reference the list again.

If we make a small change to the last node in the list we can have a circular list. For the last node, we make the pointer point to the first node rather than to a null pointer. From any point in a circular list it is possible to reach any other point.

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

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

struct node *createCircularList(int data);
struct node *createNode(int data);
struct node *insertNodeAfter(struct node *p, node *newNode);
struct node *appendNode(struct node *pHeader, node *newNode);

void printOutList(char *message, struct node *location);
void printList(struct node*location);

int main()
{
	struct node *head = createCircularList(42);
	struct node *current = head;

	struct node *newNode = createNode(73);
	current = appendNode(head, newNode);

	newNode = createNode(404);
	current = insertNodeAfter(current, newNode);

	newNode = createNode(1138);
	current = insertNodeAfter(head, newNode);

	newNode = createNode(2600);
	current = appendNode(head, newNode);

	printOutList("First Time", head);

	newNode = createNode(3435);
	current = insertNodeAfter(head, newNode);

	newNode = createNode(7749);
	current = insertNodeAfter(current, newNode);

	printOutList("Second Time", head);

    return 0;
}

void printOutList(char *message, struct node *location) {
	printf("\n%s\n", message);
	printList(location);
	printf("\n");
}

void printList(struct node*location) {
	struct node *temp = location;
	do {
		printf("%d\t", temp->data);
		temp = temp->link;
	} while (temp != location);
}

struct node *createCircularList(int data = 0) {
	return createNode(data);
}

struct node *appendNode(struct node *pHeader, node *newNode) {
	struct node *tempNode = pHeader->link;
	while (tempNode->link != pHeader) {
		tempNode = tempNode->link;
	}
	return insertNodeAfter(tempNode, newNode);
}

struct node *insertNodeAfter(struct node *p, node *newNode) {
		//set new node linked to whatever old node is linked to
		newNode->link = p->link;
		//set old node linked to new node
		p->link = newNode;
		return newNode;
}

struct node *createNode(int dataParam) {
	struct node *retNode = (struct node *)malloc(sizeof(struct node));

	retNode->data = dataParam;
	retNode->link = retNode; 

	return retNode;
}

Let’s take a look at the Josephus problem using a circular list. The Josephus problem relates to a real event that occurred in the life of Flavius Josephus, a Jewish Roman historian. According to Josephus, he and his fellow soldiers decided to kill each other rather than surrender to the Roman army. The typical version involves the soldiers standing in a circle and clockwise around themselves, and killing every nth.

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

#define NAME_MAX 256
#define LIST_MAX 10

struct node {
	char name[NAME_MAX];
	node *link;
};

struct node* createNode(const char *name);
struct node* createCircularList(const char *names[], int numNames);
void printCircularList(struct node* head, int nums);
void deleteNodeAfter(struct node *theNode);
void printNode(struct node *theNode);

int main()
{
	//typically this is set to three
	//every third is killed
	int n = 3;
	
	const char *soldiers[LIST_MAX];
	struct node* listHead;
	struct node* position;

	soldiers[0] = "Aaron";
	soldiers[1] = "Benjamin";
	soldiers[2] = "Samuel";
	soldiers[3] = "Caleb";
	soldiers[4] = "Daniel";
	soldiers[5] = "Jacob";
	soldiers[6] = "Elliot";
	soldiers[7] = "Gabriel";
	soldiers[8] = "John";
	soldiers[9] = "Michael";

	//create the list
	listHead = createCircularList(soldiers, LIST_MAX);
	//test to make sure list works
	printCircularList(listHead, LIST_MAX + 4);

	//eliminate every third soldier
	position = listHead;
	do {
		for (int i = 0; i < n-1; i++) { 			
                    position = position->link;
		}
		printf("We will kill ");
		printNode(position->link);
		printf("\n");
		deleteNodeAfter(position);
	} while (position->link != position);

	printNode(position);
	printf(" is left...\n");
	return 0;
}

void deleteNodeAfter(struct node *theNode) {
	struct node*temp = theNode->link;
	theNode->link = temp->link;
	free(temp);
}

void printNode(struct node *theNode) {
	printf("%s", theNode->name);
}

struct node* createCircularList(const char *names[], int numNames) {
	int i = 0;
	node *head, *temp, *tail;
	head = createNode(names[i++]);
	tail = head;
	for (i; i < numNames; i++) { 		
                 temp = createNode(names[i]); 		
                //make the current tail link to the new node 		
                 tail->link = temp;
		//make the new node link back to the head
		temp->link = head;
		//make the new node the tail
		tail = temp;
	}

	return head;

}

void printCircularList(struct node* head, int nums) {
	struct node*temp = head;
	for (int i = 0; i < nums; i++) { 		
                printf("Name: \t%s\n", temp->name);
		temp = temp->link;
	}
}

struct node* createNode(const char *name) {
	node * newNode = (node*)malloc(sizeof(node));
	//copy name to new node
	if (strlen(name) < NAME_MAX) { 		
           strcpy_s(newNode->name, NAME_MAX, name);
	}
	//initialize link to point to itself
	newNode->link = newNode;
	return newNode;
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s