Self Referential Data Structure in C - create an ordered singly linked list

The process of creation of an ordered singly linked list involves inserting a new node maintaining an order either ascending or descending. It revolves around three basic operations, viz.

1. Insertion at the beginning of the list.
2. Insertion somewhere in the middle, i.e. anywhere other than at the beginning or at the end.
3. Appending at the end.

To understand how to carry out the above three types of operations on a list so as to create an ordered list, let us look at an example.

Consider that we have to write a program which will take in words from the user and build a lexically ordered list. For ease of understanding, we will assume that the user provides the following 4 words � bat, mat, cat, ant.

The list will initially begin as an empty list. We will use a start pointer to point to the first node in the list. Each node will have a pointer element that will point to the next node in lexical order. The pointer in the last node of the list will point to NULL to indicate end of the list.

When the program begins, the list is empty. So our start pointer will point to NULL.

The user now feeds in the first word, viz. bat. Since bat is the first node to be inserted, this node address is assigned to start.

To maintain the increasing order (lexically) the data for the next node mat is to be inserted after bat. Since there are no other nodes at present, essentially the node mat is appended at the end of the list.

To implement such an operation we use two pointers prev and curr. Both these pointers initially point to the first node of the list (same as start). Then curr is traversed to point to the next node in the sequence. The pointer prev will always follow behind curr and will remain one position behind. When initially curr is pointing to the first node, viz. bat, we compare the node element bat with mat and find that mat is lexically bigger than bat, so we move curr to the next node, letting prev remain one node behind. Now, prev points to bat and curr points to NULL. We know that prev->next will give us a handle to the pointer element of the first node. So, to attach mat after bat, we assign the address of mat to prev->next.

Thus the operation will entail the following statements. The image following the statements illustrate the effect of the statements.

curr = start
prev = curr

curr = curr->next (curr points to NULL)

prev->next = newNode (Since newNode points to mat, mat gets attached after bat)
newNode->next = curr (since curr points to NULL, newNode->next will remain NULL)

For the next insertion, curr and prev are again reset to start. To insert a new node cat the previously mentioned steps are repeated. The comparison of new node information (cat) and current node information (bat) indicates that cat should appear after bat. Hence, curr is made to point to next node that stores mat and the process of comparing new node and current node information continues. The prev pointer follows curr, and points to the first node of the, list (bat).

The next comparison finds cat is to be placed before mat (pointed to by curr), Hence the new node information cat is to be inserted in between bat (pointed to by prev) and mat (pointed to by curr). To achieve the requisite insertion, prev->next is made to point to the new node created to accommodate cat and newNode->next is made to point to the node pointed to by curr i.e. newNode->next = curr.

The next node to be inserted contains data ant, which is to be placed before the first element's data in the list i.e. before bat. Here the comparison with the first node indicates that the new node is to be inserted before bat that means the start needs to be redefined. This context is trapped by comparing the address of prev and curr. If both of them are stuck at start, it indicates insertion is to take place at the beginning.

Here is the full C program to implement the above. Review the program carefully and also run it to develop full understanding of the above concept.

#include <stdio.h> 

struct node_type {
	char data[21];
	struct node_type *next;
};
typedef struct node_type list;

void showList();
list *sortInsert();
list *createNode();
list *find();

main()
{
	list *newnode, *start = NULL; //start will point to first node of the list
	char c = 'y';
	char word[21];

	while(c != 'n' && c != 'N')
	{
		printf("\nEnter the word: ");
		scanf("%s",word); fflush(stdin);
		newnode = createNode();
		strcpy(newnode->data, word);
		newnode->next = NULL;
		if(!find(start,newnode->data)) 
			start = sortInsert(start,newnode);
		printf("\nTHE LIST SO FAR: "); showList(start); printf("\n\n");

		printf("\nDo you want to add new data in the list? (y/n): ");
		scanf("%c",&c); getchar(); fflush(stdin);
	}
	printf("\nTHE SORTED LIST IS: "); showList(start); printf("\n\n");
}


/* Function to create a Node. Allocates memory for a new node. */
list *createNode()
{
	list *new; 
	new = (list *)malloc(sizeof(list));
	return(new);
}

list *sortInsert(list *start, list *newnode)
{ 
	list *prev,*curr;

	if(start==NULL)
	{
		//List is empty. Insert first node
		return(newnode);
	}

	//The code below will be executed when list is not empty
	curr = start;
	prev = curr;

	if(strcmp(newnode->data,curr->data)<0)
	{
		//new node < first node. Insert at the beginning.
		start = newnode;
		newnode->next = curr;
		return(start);
	}

	//The code below will be executed when new node is to
	//be inserted anywhere in the middle or at the end
	while(curr!=NULL)
	{
		curr = curr->next;
		if(curr==NULL)
		{
			//We have reached the end. Attach node to the end.
			prev->next = newnode;
			newnode->next = curr;
			return(start);
		}
		else
		{
			if(strcmp(newnode->data,curr->data)<0)
			{
				prev->next = newnode;
				newnode->next = curr;
				return(start);
			}
			prev = prev->next;
		}
	}

	return(start);
}

/*
 Function to search a data item in the list and return the node address
 that matches data. In case no match found, returns NULL
*/
list *find(list *st, int dt)
{
	while(st)
		if(strcmp(st->data,dt) == 0)
			return (st);
		else
			st = st->next;
	return(st);
}

void showList(list *temp) 
{
	while(temp)
	{
		printf("%s ", temp->data);
		temp = temp->next;
	}
	printf("\n");
}

Lab Work

1) A character string can be stored in a linked list where each node stores a character as shown below for the string The City of joy.

Write a C program to implement each of the following operations.

1. Read a string and convert it into a list. The function must return a pointer to the header node.
2. Convert a list of characters to a character string.
3. Check whether a given character is present in the string str. If so, count the number of occurrences of this character. Besides the number of occurrence, the function must rerun the pointer to the node of the list corresponding to the first occurrence.
4. Verify whether a string str1 is a substring of another string str2. If so, the function returns a pointer to the node of the list corresponding to str2 that indicates beginning of str1.
5. Substitute a sub-string of length m of a string str1 beginning at k-th character by another string str2 (the length of str2 need not be equal to m). The function must return a pointer to the header of the modified string.

2) Write a C program to perform each of the following operations on linked lists.

1. Count the number of nodes in a list.
2. Insert all elements after the n-th element of the list.
3. Delete the n-th element of a list.
4. Interchange the elements of two nodes of a list.
5. Concatenate two lists.
6. Copy a list into a second list.
7. Place the elements of a list in ascending order (assume suitable partial ordering relation between the elements of the list).
8. Split a list into two lists, so that successive nodes are placed alternative in the two newly created lists.
9. Merge two sorted lists such that merged list remains sorted.