Ergonomics
tech guide & how tos..
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.
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:
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);
}
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);
}
Defining Pointers to Structures in C
Self Referential Data Structure in C - create an ordered singly linked list
How to move your Email accounts from one hosting provider to another without losing any mails?
How to resolve the issue of receiving same email message multiple times when using Outlook?
Self Referential Data Structure in C - create a singly linked list
Mosquito Demystified - interesting facts about mosquitoes
Elements of the C Language - Identifiers, Keywords, Data types and Data objects
How to pass Structure as a parameter to a function in C?
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 premier engineering colleges & management institutes, and IT professionals.
Rajeev has founded Computer Solutions & Web Services Worldwide. He has hands-on experience of building variety of websites and business applications, that include - SaaS based erp & e-commerce systems, and cloud deployed operations management software for health-care, manufacturing and other industries.