# 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.

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.

### 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:
Buy Domain & Hosting from a trusted company
Web Services Worldwide