Linked List

A linked list is a collection of data structures that are linked together.

A linked list is a series of links that contain items. Each link is connected to another link. After the array, the linked list is the most commonly used data structure. The following are key terms to comprehend the notion of Linked List.

It consists of 3 parts:-

(i) Link – A linked list’s links can each store data known as elements.

(ii) Next – Each link in a linked list encompasses a Next link to the next link.

(iii) First – A Linked List contains its connection link to the first link, which is called First.

Characteristics of Linked List:-

(i) The first link element in a Linked List is called the first.

(ii) Each link has a data field(s) as well as a link paddock called next.

(iii) Each link is connected to its next link via its next link.

(iv) To indicate the conclusion of the list, the last link contains a null link.

Types of Linked List :

• Singly Linked List − Item navigation is forward only.
• Doubly Linked List − Items can be navigated forward and backward.
• Circular Linked List − The last item contains link of the first element as next and the first element has a link to the last element as the previous.

Basic Operations

Following are the basic operations supported by a list.

• Insertion − Adds an element at the beginning of the list.
• Deletion − Deletes an element at the beginning of the list.
• Display − Displays the complete list.
• Search − Searches an element using the given key.
• Delete − Deletes an element using the given key.

• Insert Last − Adds an element at the end of the list.
• Delete Last − Deletes an element from the end of the list.
• Insert After − Adds an element after an item of the list.
• Delete − Deletes an element from the list using the key.
• Display forward − Displays the complete list in a forward manner.
• Display backward − Displays the complete list in a backward manner.

Singly Linked List – A Singly Linked List is a subset of a generic linked list. Each node in a single linked list links only to the next column in the sequence, therefore if we started traversing the list starting with the first node, we can only travel in one way.

Insertion – Following code explains inserion operation on singly linked list

#include<stdio.h>  

#include<stdlib.h>  

void beginsert(int);  

struct node  

{  

    int data;  

    struct node *next;  

};  

struct node *head;  

void main ()  

{  

    int choice,item;  

    do   

    {  

        printf(“\nEnter the item which you want to insert?\n”);  

        scanf(“%d”,&item);  

        beginsert(item);  

        printf(“\nPress 0 to insert more ?\n”);  

        scanf(“%d”,&choice);  

    }while(choice == 0);  

}  

void beginsert(int item)  

    {  

        struct node *ptr = (struct node *)malloc(sizeof(struct node *));  

        if(ptr == NULL)  

        {  

            printf(“\nOVERFLOW\n”);  

        }  

        else  

        {  

            ptr->data = item;  

            ptr->next = head;  

            head = ptr;  

            printf(“\nNode inserted\n”);  

        }  

    }  

Deletion – Following code demonstrate deletion operation.

#include<stdio.h>  

#include<stdlib.h>  

void create(int);  

void begdelete();  

struct node  

{  

    int data;  

    struct node *next;  

};  

struct node *head;  

void main ()  

{  

    int choice,item;  

    do   

    {  

        printf(“\n1.Append List\n2.Delete node\n3.Exit\n4.Enter your choice?”);  

        scanf(“%d”,&choice);  

        switch(choice)  

        {  

            case 1:  

            printf(“\nEnter the item\n”);  

            scanf(“%d”,&item);  

            create(item);  

            break;   

            case 2:  

            begdelete();  

            break;   

            case 3:  

            exit(0);  

            break;    

            default:  

            printf(“\nPlease enter valid choice\n”);  

        }  

    }while(choice != 3);  

}  

void create(int item)  

    {  

        struct node *ptr = (struct node *)malloc(sizeof(struct node *));  

        if(ptr == NULL)  

        {  

            printf(“\nOVERFLOW\n”);  

        }  

        else  

        {  

            ptr->data = item;  

            ptr->next = head;  

            head = ptr;  

            printf(“\nNode inserted\n”);  

        }  

    }  

void begdelete()  

    {  

        struct node *ptr;  

        if(head == NULL)  

        {  

            printf(“\nList is empty”);  

        }  

        else   

        {  

            ptr = head;  

            head = ptr->next;  

            free(ptr);  

            printf(“\n Node deleted from the begining …”);  

        }  

    }