Linked list is one of the fundamental,simplest and most common data structures in C programming language.A linked list is a data structure consisting of a group of nodes which together represent a sequence.Each node comprises of data and a link to the next node in the sequence.
Advantages of Linked List over an array-
1.Linked list is a dynamic data structure whose length can be increased or decreased at run time.An array is a static data structure that is length of array cannot be altered at run time.
2.In an array, all the elements are kept at consecutive memory locations while in a linked list the elements (or nodes) may be kept at any location but still connected to each other through pointers.The list elements can easily be inserted or removed without reallocation or reorganization of the entire structure because the data items need not be stored contiguously in memory or on disk.
3.Linked lists are preferred mostly when we don’t know the volume of data to be stored.
Creating a Linked List-
A block in a linked list is represented through a structure-
typedef struct node_type
{
int data;
struct node_type *link;
} node;
The value ‘data’ can be any value while the pointer ‘link’ contains the address of next block of this linked list.
The ‘next’ pointer of the last node would contain a NULL.
A node is created by allocating memory to a structure in the following way-
struct node_type *ptr = (struct node_type*)malloc(sizeof(struct node_type));
The pointer ‘ptr’ now contains address of a newly created node.
To assign a value to the node-
ptr->val = data;
To assign its next pointer,the address of next node-
ptr->next = NULL;
The first node of the list is known as head node.
Algorithm-
//initialization
head->data=X;
head->next=NULL;
PROCEDURE-
//let the new node be temp
//inserted at the beginning
temp->data=X;
temp->next=head;
head=temp;
REPEAT PROCEDURE
Code-
[cpp]
//Insertion at the beginning of the list
typedef struct node_type
{
int data;
struct node_type *link;
} node;
typedef node *list;
list head;
//value to be entered in the list is dat which is the input
scanf("%d",&dat);
//creating the first node
head=(list)malloc(sizeof(node));
head->data = dat;
head->link=NULL;
list temp;
//dat!=99 denotes stopping condition
while(dat!=99)
{
scanf("%d",&dat);
//creating node
temp=(list)malloc(sizeof(node));
temp->data=dat;
temp->link=head;
//since inserted at the beginning
// the new node will become the head
head=temp;
}
//Printing the list
temp=head; //initialization
while(temp!=NULL)
{
printf("%d ",temp->data);
//going to next node
temp=temp->next;
}
[/cpp]
