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.

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.

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.

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