Linked list: A linked list is a self referential structure which contain a member field that point to the same structure type. In simple term, a linked list is collections of nodes that consists of two fields, one containing the information about that node, item and second contain the address of next node. Such a structure is represented as follows:
struct node
{ int item;
struct node *next;
};
Info part can be any of the data type; address part should always be the structure type.
Linked lists are of following types:
1. Linear Singly linked list: A list type in which each node points to the next node and the last node points to NULL.
2. Circular linked list: Lists which have no beginning and no end. The last node points back to the first item.
3. Doubly linked list or Two-way linked list: These lists contain double set of pointers, one pointing to the next item and other pointing to the preceding item. So one can traverse the list in either direction.
4. Circularly doubly linked list: It employs both the forward and backward pointer in circular form.
A program to demonstrate simple linear linked list is given below:
#include < stdio. h>
#include < stdlib . h>
#define NULL 0
#define NULL 0
{
int number;
struct linked_list *next;
};
typedef struct linked_list node;
void main()
{
node *head;
void create(node *p);
int count(node *p);
void print(node *p);
clrscr();
head=(node *)malloc(sizeof(node));
create(head);
printf("\n");
print(head);
printf("\n");
printf("\n Number of items = %d \n",count(head));
getch();
}
void create(node *list)
{
printf("Input a number\n");
printf("(type -999 to end) : ");
scanf("%d",&list->number);
if(list->number == -999)
list->next=NULL;
else
{
list->next=(node *)malloc(sizeof(node));
create(list->next);
}
return;
}
void print(node *list)
{
if(list->next!=NULL)
{
printf("%d - ->",list->number);
if(list->next->next == NULL)
printf("%d",list->next->number);
print(list->next);
}
return;
}
int count(node *list)
{
if(list->next == NULL)
return(0);
else
return(1+count(list->next));
}
