Linked list

  • Linked list can be defined as the collection of nodes that can be randomly stored in the memory.
  • A node contains two fields namely as data and a pointer.
  • The data stores the data or the value given by the user and the pointer holds the address of another node
  • The last node contains the value as NULL, because it does not point any node. 
Linked list


Advantages of linked list :

  • The first advantage is the linked list does not need in contigeous memory allocation. We can store our data in the memory anywhere. 
  • The empty node does not need to be represented in the linked list.
  • We can store values of primitive types or the objects, in singly linked list.
  • The linked list is limited to the memory size and does not need to be declared in advance.

There are various operations that can be carried out in linked list :

  • Creating linked list
  • Insertion in beginning
  • Insertion in random
  • Insertion in last
  • Deletion in beginning
  • Deletion in random
  • Deletion in last

Types of Linked lists :

  • Singly linked list
  • Doubly linked list

Now lets see programs for operations on singly linked list :


1 . Creating linked list


    # include <stdio.h>
    # include < stdlib.h>
    

        struct node
        {
            int data;
            struct node * next;
        }

     void create ( )
    {
        struct node*temp,*p;
        int n,i;


        printf("enter the size");
        scanf("%d",&n);


        for( ; n > 0 ; n-- )
        {
            temp=(struct node*)malloc(sizeof(struct node));
            printf("enter the value");
            scanf("%d",&i);


            temp→data=i;
            temp→next=NULL;

            if(root==NULL)
            {
                root=temp;
            }
            else
            {
                p→next=temp;

            }
                p=temp;
        }
    }

2 . Insertion in beginning

    # include <stdio.h>
    # include < stdlib.h>

    

        struct node
        {
            int data;
            struct node * next;
        }

    void addinfirst ( )
    {
        struct node*temp;
        int i;


        temp=(struct node*)malloc(sizeof(struct node));
        printf("enter the value");
        scanf("%d",&i);


        temp→data=i;

        temp→next=NULL;

        if(root==NULL)
        {
            root=temp;
        }
        else
        {
            temp→next=root;

            root=temp;
        }
    }

3 . Insertion in last

    # include <stdio.h>
    # include < stdlib.h>

       struct node

        {
            int data;
            struct node * next;
        }

    void addinlast ( )
    {
        struct node*temp;
        int i;


        temp=(struct node*)malloc(sizeof(struct node));
        printf("enter the value ");
        scanf("%d",&i);


        temp→data=i;

        temp→next=NULL;

        if(root==NULL)
        {
            root=temp;
        }
        else
        {
            struct node*p;
            p=root;


            while(p→next!=NULL)

            {
                p=p→next;

            }
            p→next=temp;

        }
    }

4 . Insertion in random

    # include <stdio.h>

    # include < stdlib.h>
    
        struct node
        {
            int data;
            struct node * next;
        }

    void addinmiddle ( )
    {
        struct node*temp,*p;
        int i=0,loc,n;
        temp=(struct node*)malloc(sizeof(int));


        if(root==NULL)
        {
            printf("linklist is empty\n\n");
        }


        else
        {
            printf("enter the location");
            scanf("%d",&loc);


            printf("enter the value");
            scanf("%d",&n);


            temp→data=n;

            temp→next=NULL;

            p=root;
            while(i<loc)
            {
                p=p→next;

                 i++;
            }    
            temp→next=p→next;

            p→next=temp;

            printf("node is inserted\n\n");
        }
    }

5 . Deletion in first

    # include <stdio.h>
    # include < stdlib.h>

         struct node

        {
            int data;
            struct node * next;
        }

    void deleteinfirst ( )

    {
        struct node*temp;


        if(root==NULL)
        {
            printf("linklist is empty");
        }


        else
        {
            temp=root;


            root=temp→next;

            temp→next=NULL;

            free(temp);
            printf("node is deleted");
        }
    }

6. Deletion in last

    # include <stdio.h>
    # include < stdlib.h>

    

        struct node
        {
            int data;
            struct node * next;
        }

    void deleteinlast ( )
    {
        struct node*temp;
        if(root==NULL)
        {
            printf("linklist is empty");
        }
        else
        {
            struct node*p;
            temp=root;
            while(temp→next!=NULL)

            {
                p=temp;
                temp=temp→next;

            }
            p→next=NULL;

            free(temp);
            printf("node is deleted");
        }
    }

7. Deletion in random

    # include <stdio.h>
    # include < stdlib.h>

        struct node

        {
            int data;
            struct node * next;
        }

    void deleteinmiddle ( )
    {
        struct node*temp,*p;
        int i=0,loc,n;


        if(root==NULL)
        {
            printf("linklist is empty");
        }


        else
        {    
            printf("enter the location");
            scanf("%d",&loc);
            temp=root;


            while(i<loc)
        {
            p=temp;
            temp=temp→next;

            i++;
        }
            p→next=temp→next;

            free(temp);
            printf("node is deleted\n\n");
        }
    }

8. To display the data in linklist

    # include <stdio.h>
    # include < stdlib.h>
    
        struct node
        {
            int data;
            struct node * next;
        }

    void display ( )
    {
        struct node*temp;
        temp=root;


        if(temp==NULL)
        {
            printf("linklist is empty\n");
        }


        else
       {
            while(temp!=NULL)
            {
                printf("%d\n",temp→data);

                temp=temp→next;

            }
        }
    }


Linked list Part 2

what is data structure ?

Classification of Data Structure