¤ Home » Programming » C Tutorial » Self Referential Data Structure in C - create a singly linked list

Self Referential Data Structure in C - create a singly linked list

A self referential data structure is essentially a structure definition which includes at least one member that is a pointer to the structure of its own kind. A chain of such structures can thus be expressed as follows.

struct name {
		member 1;
		member 2;
		. . .
		struct name *pointer;
};

The above illustrated structure prototype describes one node that comprises of two logical segments. One of them stores data/information and the other one is a pointer indicating where the next component can be found. .Several such inter-connected nodes create a chain of structures.


The following figure depicts the composition of such a node. The figure is a simplified illustration of nodes that collectively form a chain of structures or linked list.


Such self-referential structures are very useful in applications that involve linked data structures, such as lists and trees. Unlike a static data structure such as array where the number of elements that can be inserted in the array is limited by the size of the array, a self-referential structure can dynamically be expanded or contracted. Operations like insertion or deletion of nodes in a self- referential structure involve simple and straight forward alteration of pointers.


Linear (Singly) Linked List

A linear linked list is a chain of structures where each node points to the next node to create a list. To keep track of the starting node's address a dedicated pointer (referred as start pointer) is used. The end of the list is indicated by a NULL pointer. In order to create a linked list of integers, we define each of its element (referred as node) using the following declaration.

struct node_type {
	int data;
	struct node_type *next;
};
struct node_type *start = NULL;

Note: The second member points to a node of same type.


A linear linked list illustration:


Example

Let us now develop a C program to manipulate linked lists. For this purpose we introduce a few basic functions, which can be used to create a list, displaying its contents, inserting into a list and deleting an existing element. We also introduce two functions reverse and recReverse for reversing the elements of the list.

When a list is created a pointer called start is used to indicate the beginning of the list. A function createNode, creates a node and returns a pointer to it. The function insert is used to insert a new node in an existing list provided the data is not already present in the list. If it is not present, we place the data in a manner so that the new element is appended at the end of the list.

#include <stdio.h> 

struct node_type {
	int data;
	struct node_type *next;
};
typedef struct node_type list;

void showList();	//displays list contents
list *reverse();	//reverses the list
list *insert();
list *createNode();
list *delete();
list *find();

main()
{
	list *temp, *start = NULL; //start will point to first node of the list
	char c = 'y';
	int n;

	while(c != 'n' && c != 'N')
	{
		printf("\nEnter the data: ");
		scanf("%d",&n); getchar(); fflush(stdin);
		temp = createNode();
		temp->data = n;
		temp->next = NULL;
		if(!find(start,temp->data)) 
			start = insert(start,temp);

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

	c = 'y';
	while(c != 'n' && c != 'N')
	{
		printf("\nEnter the data to be deleted: ");
		scanf("%d",&n); getchar(); fflush(stdin);
		if(find(start, n)) start = delete(start, n);

		printf("\nDo you want to delete another data from the list? (y/n):");
		scanf("%c", &c) ; fflush(stdin);
	}
	printf("\nTHE LIST AFTER DATA DELETION IS: "); showList(start); printf("\n\n");

	start = reverse(start);
	printf("\nTHE REVERSED 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);
}


/* Recursive function to create and insert a new node at the end of the list */
list *insert(list *st, list *ndt)
{ 
	if(!st) return(ndt); 
	st->next = insert(st->next, ndt);
	return(st);
}


/*
 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(st->data == dt)
			return (st);
		else
			st = st->next;
	return(st);
}

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


/* Function to reverse the list */
list *reverse(list *l) 
{
	list *nxt, *temp;
	if(!l) return(l);
	else
	{
		nxt = l->next;
		l->next = NULL;
		while(nxt)
		{
			temp = nxt->next;
			nxt->next = l;
			l = nxt;
			nxt = temp;
		}
		return(l); 
	}
}


/* Recursive function for deleting a node from the list */
list *delete(list *st, int n)
{
	list *tmp;
	if(!st) return(st);
	if(st->data == n)
	{
		tmp = st;
		st = st->next;
		free(tmp);
		return(st);
	}
	st->next = delete(st->next,n);
	return(st);
}



Exercises

1. Identify which one of the following declaration correctly defines a self referential data structure.

a) struct class_1 {
	char name[31];
	. . .
	struct class_2 *c;
   };

b) struct class_1 {
	char name[31];
	. . .
	struct class_1 *c;
   };

c) struct class_1 {
	char name[31];
	. . .
	struct class_1 c;
   };

2. Identify the errors (if any) in the following C programs.

a) The function addList inserts a new node (nw) at the beginning of the list pointed to by the start pointer.

addList(list *start, list *nu)
{
	if(start)
		start = nu;
	else
		nw->nxt = start;
}

b) The function displayList (start pointer is passed as an argument) recursively displays all the nodes in the list.

displayList(list *st)
{
	if(!st) return;
	printf("%d ", st->data);
	displayList(st->nxt);
}


Share:




comments powered by Disqus


Buy Domain & Hosting from the most reliable and trusted company - WebServicesWorldWide.com.

Looking to build a website?
Launch a 20 page website in 1 day at only Rs.200/month or US$ 3.19/month. Hosting & Email included.





About the Author

Rajeev Kumar
CEO, Computer Solutions
Jamshedpur, India

Rajeev Kumar is the primary author of How2Lab. He is a B.Tech. from IIT Kanpur with several years of experience in IT education and Software development. He has taught a wide spectrum of people including fresh young talents, students of XLRI, industry professionals, and govt. officials.

Rajeev has founded Computer Solutions & WebServicesWorldwide.com, and has hands-on experience of building variety of web applications and portals, that include - SAAS based ERP & e-commerce systems, independent B2B, B2C, Matrimonial & Job portals, and many more.



Copyright © How2Lab.com. All rights reserved.

Refer a friend | Sitemap | Disclaimer | Privacy Policy