More
    CodingC++Linked List Data Structure

    Linked List Data Structure

    Linked List is a multiple blocks of memory linked with each other.

    There are basically three types of Linked List, we will be discussing about each on them in detail.

    Singly Linked List

    Important points:

    • Each block consist of two parts i.e., the data and the address of the next node.
    • Size of a linked list can always be changed (dynamic size) as per requirement.
    • Data is stored in non-contiguous manner. That is why random access of elements are not allowed.
    • Extra memory space for pointers are required.
    • Insertion and deletion of elements is quite easy as compare to arrays.

    Creation of a node in a singly linked list

    Nodes are created using structure i.e.,

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

    Here’s a pictorial representation of a single node in a singly linked list.

    singly linked list

    Creation and traversal of a singly linked list:

    #include<iostream>
    #include<stdlib.h>
    #include<bits/stdc++.h>
    using namespace std;
    
     //node implementation:
    
     struct node{
        int data;
        struct node * next;
     };
    
     //linked list traversal:
    
    void traversal(struct node *ptr){
    while(ptr!=NULL){
    cout<<ptr->data<<" ";
    ptr=ptr->next;}
    }
    int main(){
        //creating and linking three nodes:
       struct node *head;
       struct node *second;
       struct node *third;
       head=(struct node *)malloc(sizeof(struct node));
       second=(struct node *)malloc(sizeof(struct node));
       third=(struct node *)malloc(sizeof(struct node));
       head->data=7;
       head->next=second;
       second->data=10;
       second->next=third;
       third->data=40;
       third->next=NULL;
       traversal(head);
      }
    

    Output:

    7 10 40

    Here’s a pictorial representation of the linked list, which is created using the program above.

    output

    Insertion in a singly linked list:

    #include<iostream>
    #include<stdlib.h>
    #include<bits/stdc++.h>
    using namespace std;
     
     struct node{
        int data;
        struct node * next;
     };
    
     //traversal of the linked list
    
    void traversal(struct node *ptr){
    while(ptr!=NULL){
    cout<<ptr->data<<" ";
    ptr=ptr->next;}
    }
    
    //insertion at the beginning of the linked list
    
    struct node *insertAtBeg(struct node *head, int data){
        struct node *ptr=(struct node *)malloc(sizeof(struct node));
        ptr->next=head;
        ptr->data=data;
        return ptr;
    }
    
    //insertion at a given index (in between)
    
    struct node *insertInBetw(struct node *head, int data,int index){
        struct node *ptr=(struct node *)malloc(sizeof(struct node));
        struct node *p=head;
        int i=0;
        while(i != index-1){
            p=p->next;
            i++;
            }
            ptr->data=data;
            ptr->next=p->next;
            p->next=ptr;
            return head;
            
    }
    
    //insertion at the end 
    
    struct node *insertAtEnd(struct node *head,int data){
        struct node *ptr=(struct node *)malloc(sizeof(struct node));
        struct node *p =head;
        while(p->next != NULL){
            p=p->next;
        }
        ptr->data=data;
        p->next=ptr;
        ptr->next=NULL;
        return head;
    
    }
    
    //insertion after a given node
    
    struct node *insertAfterNode(struct node *head, struct node *prevnode, int data){
        struct node *ptr=(struct node *)malloc(sizeof(struct node));
        ptr->data=data;
        ptr->next=prevnode->next;
        prevnode->next=ptr;
        return head;
    }
    int main(){
       struct node *head;
       struct node *second;
       struct node *third;
       head=(struct node *)malloc(sizeof(struct node));
       second=(struct node *)malloc(sizeof(struct node));
       third=(struct node *)malloc(sizeof(struct node));
       head->data=7;
       head->next=second;
       second->data=10;
       second->next=third;
       third->data=40;
       third->next=NULL;
    }

    In the above code,  seperate functions for all type of insertion is present.We just need to simply call these functions in the main function for inserting elements in our linked list.

    Deletion in a singly linked list:

    #include<iostream>
    #include<bits/stdc++.h>
    using namespace std;
    
    struct node {
        int data;
        struct node *next;
    
    };
    
    //traversal of the linked list
    
    void trav(struct node *head){
        struct node*ptr=head;
        while(ptr !=NULL){
            cout<<ptr->data<<" ";
            ptr=ptr->next;
        }
    }
     
    //Deletion of the first element 
    
    struct node *DltInBeg(struct node *head){
        struct node *ptr=head;
        head=head->next;
        free(ptr);
        return head;
    }
    
    //Deletion of the element in between
    
    struct node *DltInBtw(struct node *head, int index){
        struct node*p=head;
        struct node *q=head->next;
        for(int i=0;i<index-1;i++){
            p=p->next;
            q=q->next;
            }
             p->next=q->next;
             free(q);
             return head;
    
    }
    
    //Deletion of the last element
    
    struct node *DltEnd(struct node*head){
        struct node*p=head;
        struct node*q=head->next;
        while(q->next != NULL){
          p=p->next;
          q=q->next;
        }
        p->next=NULL;
        free(q);
        return head;
    }
    
    //Deletion of any particular given data
    
    struct node *partData(struct node *head,int value){
        struct node *p=head;
        struct node *q=head->next;
        while(q->data != value && q->next !=NULL){
            p=p->next;
            q=q->next;
    
    }
    if(q->data==value){
        p->next=q->next;
        free(q);
    
    }
    return head;
    }
    
    int main(){
         struct node *head;
       struct node *second;
       struct node *third;
       struct node *fourth;
       head=(struct node *)malloc(sizeof(struct node));
       second=(struct node *)malloc(sizeof(struct node));
       third=(struct node *)malloc(sizeof(struct node));
       fourth=(struct node *)malloc(sizeof(struct node));
       head->data=7;
       head->next=second;
       second->data=10;
       second->next=third;
       third->data=40;
       third->next=fourth;
       fourth->data=56;
       fourth->next=NULL;
        return 0;
    }
    

    In the above code, separate functions for all type of deletion is present. We just need to simply call these functions in the main function for deleting elements in our linked list.

    Doubly Linked List

    In doubly linked list each node contain three things i.e., the data, address of the previous and the next node.

    Creation of a node:

    Nodes are created using the structure i.e.,

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

    Here’s a pictorial representation of a single node in a doubly linked list.

    doubly linked list node

    Creation and traversal of a doubly linked list:

    #include<iostream>
    #include<stdlib.h>
    #include<bits/stdc++.h>
    using namespace std;
    
    struct node {
        int data;
        struct node *prev;
        struct node *next;
    };
    
    //traversal of the elements in forward direction
    
    void travForw(struct node *ptr){
        while(ptr != NULL){
            cout<<ptr->data<<" ";
            ptr=ptr->next;
        }
    }
    
    //traversal of the elements in backward direction
    
    void travPrev(struct node *ptr){
        while(ptr != NULL){
            cout<<ptr->data<<" ";
            ptr=ptr->prev;
        }
    }
    int main(){
        struct node *head;
        struct node *second;
        struct node *third;
        struct node *fourth;
        head=(struct node*)malloc(sizeof(struct node));
        second=(struct node*)malloc(sizeof(struct node));
        third=(struct node*)malloc(sizeof(struct node));
        fourth=(struct node*)malloc(sizeof(struct node));
        head->data=10;
        second->data=11;
        third->data=12;
        fourth->data=13;
        head->prev=NULL;
        head->next=second;
        second->prev=head;
        second->next=third;
        third->prev=second;
        third->next=fourth;
        fourth->prev=third;
        fourth->next=NULL;
        //printing elements from left to right
        travForw(head); 
        cout<<endl;
          //printing elements from right to left
        travPrev(fourth);
        return 0;
    }
    

    Output:

    10 11 12 13 
    13 12 11 10
    

    Here’s a pictorial representation of the linked list, which is created using the program above.

    We can traverse, insert, delete similarly as we did in the singly linked list. The only difference in the doubly linked list is that we can traverse from both sides of the list.

    Circular Linked List:

    Circular Linked List – Detailed Article

    Time Complexity:

    In a singly linked list, the time complexity for inserting and deleting an element from the list is O(n).

    In a doubly-linked list, the time complexity for inserting and deleting an element is O(1).

    Read Next: Combinatorial Game Theory | Game of Nim

    Sponsored

    LEAVE A REPLY

    Please enter your comment!
    Please enter your name here

    Subscribe Today

    GET EXCLUSIVE FULL ACCESS TO PREMIUM CONTENT

    Get unlimited access to our EXCLUSIVE Content and our archive of subscriber stories.

    Exclusive content

    Latest article

    More article