Linked List Structures in C

A linked list is a collection in which each element is a node that contains the location of the next node. Thus, each element in the collection contains two parts, the data and then the link to the next element. These links can be used to chain the nodes together; this chain is the collection, proper. We mark the collection with a pointer to the first element in the list; the name of the list is interchangeable with the name of the pointer to the start of the list.

As mentioned, the elements of a list are nodes. A node in a linked list is a structure that has at least two fields. One of the two fields is a data field; the other is a pointer that contains the address of the next node in the sequence. The nodes in a linked list are called self-referential structures. Each instance of the structure will contain a link to another instance of the same type.

typedef struct {
	int key;
	int iData;
	double dData;
} DATA;

typedef struct listNode {
	DATA data;
	struct listNode *link;
};

We will create two utility functions to make the process of creating nodes a little faster. The first function will create the data structure that holds the information. The second structure will actually create the node that contains the data structure as well as the node structure itself, which is the data plus a pointer to the next node. Since we will not know what the next node is, if there even will be one, we will set this link to NULL.

//create and return a pointer to the data structure
DATA *createData(int iData, double dData) {
	static int keyValue = 1;
	DATA * rData = (DATA *)malloc(sizeof(DATA));
	if (rData != NULL) {
		rData->key = keyValue++;
		rData->iData = iData;
		rData->dData = dData;
	}
	return rData;
}

//create and return a pointer to the node structure
listNode *createNode(int iData, double dData) {
	listNode *rNode = (listNode *)malloc(sizeof(listNode));
	if (rNode != NULL) {
		rNode->data = createData(iData, dData);
		//set the link to NULL
		rNode->link = NULL;
	}
	return rNode;
}

Finally, let’s create one more utility function to quickly show the data contents on the screen.

void displayNode(listNode *node) {
	DATA *temp = node->data;
	printf("Node #%d: %d %f\n", temp->key, temp->iData, temp->dData);
}

One of the features of a linked list is that there is no need for the nodes to be physically adjacent to each other, as they are dynamically allocated in memory. The beginning of the list is identified with a pointer to the start or head of the list. This pointer is known as the head pointer, because it points to the list’s head. A linked list must always have a head pointer.

We can use the head node as a jumping off point for listing all the members in the list. Our function for displaying all of the nodes will call the function for displaying a single node from within a loop that checks for the end of the list by looking to see if the node’s link is set to null.

void displayAllNodes(listNode *head) {
	listNode *temp = head;
	if (temp != NULL) {
		do {
			displayNode(temp);
			temp = temp->link;
		} while (temp->link != NULL);
	}
}

Next, let’s create a function to insert a node anywhere in the list. To do so, we need to determine an insertion point. We will determine this point using the node’s unique identifier number that was assigned at the time of its creation. Once we have found the right node, we will insert the new node after it. We find out what node the preceding node is pointing to, and we have the new node point to it. Then, we have the preceding node change so that it is pointing to the new node. Thus, the new node is inserted into the chain of nodes.


//finds the node by the indexed key number stored
//in the data section of the node
listNode * findNode(listNode *theHead, int index) {
	listNode *temp = theHead;
	listNode *returnNode = NULL;
	while (temp != NULL) {
		if (temp->data->key == index) {
			return temp;
		}
		temp = temp->link;
	}
	//returns NULL if index isn't found
	return temp;
}


listNode *insertNode(listNode *theNode, listNode *theHead, int index) {
	listNode *prevNode = findNode(theHead, index);
	listNode *temp = NULL;
	if (prevNode != NULL) {
		temp = prevNode->link;
		prevNode->link = theNode;
		theNode->link = temp;
	}
	return theNode;
}

Alright, so let’s bring it all together in one program.

#include <stdlib.h>

typedef struct {
	int key;
	int iData;
	double dData;
} DATA;

typedef struct listNode {
	DATA *data;
	struct listNode *link;
};

DATA *createData(int iData, double dData);
listNode *createNode(int iData, double dData);

listNode * findNode(listNode *theHead, int index);
listNode *insertNode(listNode *theNode, listNode *theHead, int index);

void displayNode(listNode *node); 
void displayAllNodes(listNode *head);

int main()
{
	listNode *listHead = createNode(42, 1.618);
	listNode *current = createNode(73, 192.168);
	
	listHead->link = current;

	current->link = createNode(1999, 25.806975);

	current = current->link;

	current->link = createNode(404, 1.5122);

	displayAllNodes(listHead);

	//insert a node
	current = createNode(8088, 802.11);
	insertNode(current, listHead, 3);

	current = createNode(47, 15.3465);
	insertNode(current, listHead, 1);

	printf("\n\nAfter inserting nodes\n");
	displayAllNodes(listHead);

    return 0;
}

//create and return a pointer to the data structure
DATA *createData(int iData, double dData) {
	static int keyValue = 1;
	DATA * rData = (DATA *)malloc(sizeof(DATA));
	if (rData != NULL) {
		rData->key = keyValue++;
		rData->iData = iData;
		rData->dData = dData;
	}
	return rData;
}

//create and return a pointer to the node structure
listNode *createNode(int iData, double dData) {
	listNode *rNode = (listNode *)malloc(sizeof(listNode));
	if (rNode != NULL) {
		rNode->data = createData(iData, dData);
		//set the link to NULL
		rNode->link = NULL;
	}
	return rNode;
}


void displayNode(listNode *node) {
	DATA *temp = node->data;
	printf("Node #%d: %d %f\n", temp->key, temp->iData, temp->dData);
}

void displayAllNodes(listNode *head) {
	listNode *temp = head;
	if (temp != NULL) {
		do {
			displayNode(temp);
			temp = temp->link;
		} while (temp != NULL);
	}
}

//finds the node by the indexed key number stored
//in the data section of the node
listNode * findNode(listNode *theHead, int index) {
	listNode *temp = theHead;
	listNode *returnNode = NULL;
	while (temp != NULL) {
		if (temp->data->key == index) {
			returnNode = temp;
                        break;
		}
		temp = temp->link;
	}
	//returns NULL if index isn't found
	return temp;
}


listNode *insertNode(listNode *theNode, listNode *theHead, int index) {
	listNode *prevNode = findNode(theHead, index);
	listNode *temp = NULL;
	if (prevNode != NULL) {
		temp = prevNode->link;
		prevNode->link = theNode;
		theNode->link = temp;
	}
	return theNode;
}

To delete a node, we must remove the node from the linked list by altering the pointers in the nodes, and then physically remove the node to be deleted from the heap.

To delete a node, we first must find its preceding node, then alter it to link to the node that comes after the node we wish to delete. The we use the free() function to delete the node from memory.

Let’s create a function that will find the node previous to the node we are looking for.


//returns the head of the list
listNode * deleteNode(listNode *theHead, int index) {
	listNode *temp = theHead;
	listNode *toDelete = NULL;
	//check to see if head is the value to be deleted
	if (temp->data->key == index) {
		toDelete = temp;
		theHead = temp->link;
	}
	else {
		//try to find the requested record to delete
		temp = findPrevNode(theHead, index);
		if (temp != NULL) {
			toDelete = temp->link;
			temp->link = toDelete->link;
		}
	}

	if (toDelete != NULL) {
		free(toDelete);
	}
	return theHead;

}

Finally, let’s test the delete node function in main().

int main()
{
	listNode *listHead = createNode(42, 1.618);
	listNode *current = createNode(73, 192.168);
	
	listHead->link = current;

	current->link = createNode(1999, 25.806975);

	current = current->link;

	current->link = createNode(404, 1.5122);

	displayAllNodes(listHead);

	//insert a node
	current = createNode(8088, 802.11);
	insertNode(current, listHead, 3);

	current = createNode(47, 15.3465);
	insertNode(current, listHead, 1);

	printf("\n\nAfter inserting nodes\n");
	displayAllNodes(listHead);

	listHead = deleteNode(listHead, 1);
	listHead = deleteNode(listHead, 3);

	printf("\n\nAfter deleting nodes\n");
	displayAllNodes(listHead);

    return 0;
}
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