Linked List

We have studied that an array is a linear collection of data elements in which the elements are stored in consecutive memory locations. While declaring arrays, we have to specify the size of the array, which will restrict the number of elements that the array can store.. For example, if we declare an array as int marks[10], then the array can store a maximum of 10 data elements but not more than that. But what if we are not sure of the number of elements in advance? Moreover, to make efficient use of memory, the elements must be stored randomly at any location rather than in consecutive locations. So, there must be a data structure that removes the restrictions on the maximum number of elements and the storage condition to write efficient programs

Linked list is a data structure that is free from the aforementioned restrictions. A linked list does not store its elements in consecutive memory locations and the user can add any number of elements to it. However, unlike an array, a linked list does not allow random access of data. Elements in a linked list can be accessed only in a sequential manner. But like an array, insertions and deletions can be done at any point in the list in constant time.

A linked list, in simple terms, is a linear collection of data elements. These data elements are called nodes. Linked list is a data structure which in turn can be used to implement other data structures. Thus, it acts as a building block to implement data structures such as stacks, queues, and their variations. A linked list can be perceived as a train or a sequence of nodes in which each node contains one or more data fields and a pointer to the next node.

Simple Linked List

Program in C:

 #include <stdio.h>  
 #include <stdlib.h>  
 #include <conio.h>  
 #include <malloc.h>  
 struct node  
 {  
  int data;  
  struct node *next;  
 };  
 struct node *start = NULL;  
 struct node *display(struct node *);  
 struct node *insert_end(struct node *);  
 struct node *insert_after(struct node *);  
 struct node *delete_node(struct node *);  
 int main()  
 {  
  int option;  
  do  
  {  
  printf("\n\n *****MAIN MENU *****");  
  printf("\n 1: Add a node at the end");  
  printf("\n 2: Add a node after a given node");  
  printf("\n 3: Delete a given node");  
  printf("\n 4: Display the list");  
  printf("\n 5: EXIT");  
  printf("\n\n Enter your option : ");  
  scanf("%d", &option);  
  switch(option)  
  {  
   case 1: start = insert_end(start);  
    break;  
   case 2: start = insert_after(start);  
    break;  
   case 3: start = delete_node(start);  
    break;  
   case 4: start = display(start);  
    break;  
  }  
  }while(option !=5);  
  getch();  
  return 0;  
 }  
 struct node *display(struct node *start)  
 {  
  struct node *ptr;  
  ptr = start;  
  while(ptr != NULL)  
  {  
  printf("\t %d", ptr -> data);  
  ptr = ptr -> next;  
  }  
  return start;  
 }  
 struct node *insert_end(struct node *start)  
 {  
  struct node *ptr, *new_node;  
  int num;  
  printf("\n Enter the data : ");  
  scanf("%d", &num);  
  new_node = (struct node *)malloc(sizeof(struct node));  
  new_node -> data = num;  
  new_node -> next = NULL;  
  ptr = start;  
  if(start==NULL)  
  {  
  start=new_node;  
  }  
  else  
  {  
  while(ptr -> next != NULL)  
  ptr = ptr -> next;  
  ptr -> next = new_node;  
  }  
  return start;  
 }  
 struct node *insert_after(struct node *start)  
 {  
  struct node *new_node, *ptr, *preptr;  
  int num, val;  
  printf("\n Enter the data : ");  
  scanf("%d", &num);  
  printf("\n Enter the value after which the data has to be inserted : ");  
  scanf("%d", &val);  
  new_node = (struct node *)malloc(sizeof(struct node));  
  new_node -> data = num;  
  ptr = start;  
  preptr = ptr;  
  while(preptr -> data != val)  
  {  
  preptr = ptr;  
  ptr = ptr -> next;  
  }  
  preptr -> next=new_node;  
  new_node -> next = ptr;  
  return start;  
 }  
 struct node *delete_node(struct node *start)  
 {  
  struct node *ptr, *preptr;  
  int val;  
  printf("\n Enter the value of the node which has to be deleted : ");  
  scanf("%d", &val);  
  ptr = start;  
  if(ptr -> data == val)  
  {  
  start = start -> next;  
  }  
  else  
  {  
  while(ptr -> data != val)  
  {  
   preptr = ptr;  
   ptr = ptr -> next;  
  }  
  if(ptr->next==NULL)  
  {  
   preptr -> next = NULL;  
  }  
  else  
  {  
  preptr -> next = ptr -> next;  
  }  
  }  
  free(ptr);  
  return start;  
 }  

Download Source Code:

Click Here To Download Source Code