Linked list

Linked list

Linked list is the liner collection of data elements.Linked list is not store data in contiguous location 

elements are linked using pointers 

why use linked list :

Arrays can be used to store linear data of similar types, but arrays have following limitations

• Size of array is fixed so we should declare max amount of size before we use it So we must know the upper limit on the number of elements in advance.the allocated memory is equal to the upper limit irrespective of the usage
• inserting of an element in the specific location makes the complex and takes more time compared to linked list

Advantages of Linked list over arrays:

• dynamic memory allocation 
• inserting and deleting of element can be made from any specific location.

The linked list has to access sequentially .Random access is not possible

In singly linked list we use one variable for storing data element and another for storing the next element address .

A linked list is represented by a pointer to the first node of the linked list. The first node is called head. If the linked list is empty, then value of head is NULL

Representing Linked using C

struct node 

{

         int data;                     // To store data element

         struct node *link;    //The self referral structure 

}*head                               //Head Pointer is always pointing to first node

C program to implement singly linked list 

#include<stdio.h> #include<stdlib.h> struct Node {   int data;   struct Node *next; }; // Program to create a simple linked // list with 3 nodes int main() {   struct Node* head = NULL;   struct Node* second = NULL;   struct Node* third = NULL;       // allocate 3 nodes in the heap    head = (struct Node*)malloc(sizeof(struct Node));   second = (struct Node*)malloc(sizeof(struct Node));   third = (struct Node*)malloc(sizeof(struct Node));   /* Three blocks have been allocated  dynamically.      We have pointers to these three blocks as first, second and third            head           second           third         |                |               |         |                |               |     +---+-----+     +----+----+     +----+----+     | #  | #  |     | #  | #  |     |  # |  # |     +---+-----+     +----+----+     +----+----+         # represents any random value.    Data is random because we haven’t assigned anything yet  */       head->data = 1; //assign data in first node   head->next = second; // Link first node with the second node       /* data has been assigned to data part of first block (block     pointed by head).  And next pointer of first block points to     second.  So they both are linked.        head          second         third         |              |              |         |              |              |     +---+---+     +----+----+     +-----+----+     | 1  | o----->| #  | #  |     |  #  | #  |     +---+---+     +----+----+     +-----+----+      */        second->data = 2; //assign data to second node   second->next = third; // Link second node with the third node       /* data has been assigned to data part of second block (block pointed by      second). And next pointer of the second block points to third block.      So all three blocks are linked.            head         second         third         |             |             |         |             |             |     +---+---+     +---+---+     +----+----+     | 1  | o----->| 2 | o-----> |  # |  # |     +---+---+     +---+---+     +----+----+      */          third->data = 3; //assign data to third node   third->next = NULL;       /* data has been assigned to data part of third block (block pointed     by third). And next pointer of the third block is made NULL to indicate     that the linked list is terminated here.      We have the linked list ready.             head                 |              |         +---+---+     +---+---+       +----+------+         | 1  | o----->|  2  | o-----> |  3 | NULL |         +---+---+     +---+---+       +----+------+                      Note that only head is sufficient to represent the whole list.  We can     traverse the complete list by following next pointers.    */        return 0; } OUTPUT : 1 2 3  Linked list in c program #include <stdio.h> #include <malloc.h> #include <stdlib.h>   void main() { struct node { int num; struct node *ptr; }; typedef struct node NODE;   NODE *head, *first, *temp = 0; int count = 0; int choice = 1; first = 0;   while (choice) { head = (NODE *)malloc(sizeof(NODE)); printf("Enter the data item\n"); scanf("%d", &head-> num); if (first != 0) { temp->ptr = head; temp = head; } else { first = temp = head; } fflush(stdin); printf("Do you want to continue(Type 0 or 1)?\n"); scanf("%d", &choice);   } temp->ptr = 0; /* reset temp to the beginning */ temp = first; printf("\n status of the linked list is\n"); while (temp != 0) { printf("%d=>", temp->num); count++; temp = temp -> ptr; } printf("NULL\n"); printf("No. of nodes in the list = %d\n", count); } OUTPUT $ cc pgm98.c $ a.out Enter the data item 5 Do you want to continue(Type 0 or 1)? 0   status of the linked list is 5=>NULL No. of nodes in the list = 1   $ a.out Enter the data item 5 Do you want to continue(Type 0 or 1)? 1 Enter the data item 9 Do you want to continue(Type 0 or 1)? 1 Enter the data item 3 Do you want to continue(Type 0 or 1)? 0   status of the linked list is 5=>9=>3=>NULL No. of nodes in the list = 3