Skip to main content

Linked List Data Structure

Linked list is an linear data structure, that are contain nodes. every node of a linked list are contain at least two fields. data field and reference fields. data field is used to store information of data. and reference field are used to store the address (reference) of other linked list node. If there is no reference of other node then reference field are assigned to NULL (None) value.

Linked list node Structure

Location of node are not contiguous manner. And data field is single variable or group of multiple variable that is depends upon situations. and some of cases data field are not used. But reference at least one reference field are required. So linked list is combination of single or multiple nodes.

Linked list

First node of linked list are used to access all other. in this example head variable are store first node address of linked list. and last node reference field is null. NULL is indicates end of linked list. That is a singly linked list. here of using only one reference.

Type of Linked List

Commonly linked list are categorized in four section.

Single linked list

This is simplest form of linked list. there is one reference are used to point to next linked list node.

Single Linked list 
//C Program Insert linked list node at beginning of linked list
#include<stdio.h>
#include <stdlib.h> //for malloc function

//create structure
struct Node{
    int data;
    struct Node*next;
};
//function prototype
void insert(struct Node**,int);
void display(struct Node*);
//insert Node element
void insert(struct Node**head,int value){
  //Create dynamic node
    struct Node*node=(struct Node*)malloc(sizeof(struct Node));
    if(node==NULL){
        printf("Memory overflow\n");
    }else{
        node->data=value;
        node->next=*head;
        *head=node;
    }
}
//display element of Node
void display(struct Node*temp){
    
    if(temp==NULL){
        printf("Empty linked list");
    }
    while(temp!=NULL){
        printf("%d  ",temp->data);
        temp=temp->next;
    }
}
int main(){
    //create node pointer
    struct Node*head=NULL;
    //insert element of linked list
    insert(&head,8);
    insert(&head,7);
    insert(&head,6);
    insert(&head,5);
    insert(&head,4);
    insert(&head,3);
    insert(&head,2);
    insert(&head,1);
    //display all node
    display(head);
}

Output

1  2  3  4  5  6  7  8
//C++ Insert linked list node at beginning of linked list
#include<iostream>
using namespace std;

//create structure
struct Node{
    int data;
    struct Node*next;
};
class Link{
public:
    void insert(struct Node**,int);
    void display(struct Node*);
};

//insert Node element
void Link::insert(struct Node**head,int value){
        //Create dynamic node
    struct Node*node=new Node;
    if(node==NULL){
        cout<<"Memory overflow\n";
    }else{
        node->data=value;
        node->next=*head;
        *head=node;
    }
}
//display element of Node
void Link:: display(struct Node*temp){
    if(temp==NULL){
        cout<<"Empty linked list";
    }
    while(temp!=NULL){
        cout<<temp->data<<" ";
        temp=temp->next;
    }
}
int main(){
    //create node pointer
    struct Node*head=NULL;
    //create object
    Link obj;
    //insert element of linked list
    obj.insert(&head,8);
    obj.insert(&head,7);
    obj.insert(&head,6);
    obj.insert(&head,5);
    obj.insert(&head,4);
    obj.insert(&head,3);
    obj.insert(&head,2);
    obj.insert(&head,1);
    //display all node
    obj.display(head);
}

Output

1  2  3  4  5  6  7  8
#Python Insert linked list node at
#Beginning of linked list
class Node:
  def __init__(self,data):
    self.data=data
    self.next=None

#create class Linked    
class Linked:
  def __init__(self):
    #Assign default value
    self.head=None
    
  #insert new node to Linked  
  def insert(self,data):
    node=Node(data)
    node.next=self.head
    self.head=node

  def display(self):
    temp=self.head
    print("Linked Elements : "),
    while(temp!=None):
      print(temp.data),
      temp=temp.next
    else :
      print("\n")
#Create Object of class Linked
Linked=Linked()
#Perform Linked operation
Linked.insert(8)
Linked.insert(7)
Linked.insert(6)
Linked.insert(5)
Linked.insert(4)
Linked.insert(3)
Linked.insert(2)
Linked.insert(1)
Linked.display()

Output

Linked Elements :  1 2 3 4 5 6 7 8 
//java insert linked list element
public class SingleLinkedList{

  static class Node{
    int data;
    Node next;
  }
  static Node head;
  //Class constructors
  SingleLinkedList(){
    head=null;
  } 
  //insert Queue element
  static void insert(int value){
    //Create Queue node
    Node node=new Node();
    node.data=value;
    node.next=head;
    head=node;
  }
  //display all Linked List elements
  static void display(){
    if(head!=null){
      System.out.print("Linked list Element :");
      Node temp=head;
      while(temp!=null){
        System.out.print("  "+temp.data);
        temp=temp.next;
      }
    }else{
      System.out.println("Empty Linked list"); 
    }
  }

  public static void main(String[] args) {
    
    SingleLinkedList obj=new SingleLinkedList();
    obj.insert(8);
    obj.insert(7);
    obj.insert(6);
    obj.insert(5);
    obj.insert(4);
    obj.insert(3);
    obj.insert(2);
    obj.insert(1);
    obj.display();
  }
}

Output

Linked list Element :  1  2  3  4  5  6  7  8
using System;
//node class
public class Node{
   public  int data;
   public  Node next;
}
class Program
{
    Node head;
    public Program(){
        head=null;
    }
    //insert node of linked list
    public void insert(int data){
        Node element=new Node();
        element.data=data;
        element.next=head;
        head=element;
    }
    //display linked list nodes value
    public void display(){
        if(head==null){
            Console.Write("Empty List");
        }else{
            Node temp=head;
            while(temp!=null){
                Console.Write("  {0}",temp.data);
                temp=temp.next;
            }
            
        }
    }
    static void Main()
    {
        Program obj=new Program();
        obj.insert(8);
        obj.insert(7);
        obj.insert(6);  
        obj.insert(5);  
        obj.insert(4);
        obj.insert(3);  
        obj.insert(2);   
        obj.insert(1); 
        obj.display();
    }
}

Output

1  2  3  4  5  6  7  8

In this example newly created node are inserted in beginning of linked list. this process are very simple and commonly used to implement stack data structure.

Doubly linked list

Doubly linked list are used two references are hold the address of next and previous nodes. this linked list are traversal of both direction.

Doubly Linked list 
//C Program to create doubly linked list
#include <stdio.h>
#include <stdlib.h> //for malloc function

//create structure
struct Node{
    int data;
    struct Node*next;
    struct Node*prev;
};
struct Node*head,*tail;
//function prototype
void insert(int);
void forwardPrint();
void backwardPrint();
//insert Node element
void insert(int value){
  //Create dynamic node
    struct Node*node=(struct Node*)malloc(sizeof(struct Node));
    if(node==NULL){
        printf("Memory overflow\n");
    }else{
        node->data=value;
        node->next=head;
        node->prev=NULL;
        if(head!=NULL){
          head->prev=node;
        }
        if(tail==NULL){
            tail=node;
        }
        head=node;
    }
}
//display element of Node
void forwardPrint(){
    
    if(head==NULL){
        printf("Empty linked list");
    }
    else{
        printf("\nForward Element :");
        struct Node*temp=head;
        while(temp!=NULL){
            printf("%d  ",temp->data);
            temp=temp->next;
        }
    }

}
//display element of Node
void backwardPrint(){
    
    if(tail==NULL){
        printf("Empty linked list");
    }
    else{
        printf("\nBackward Element :");
        struct Node*temp=tail;
        while(temp!=NULL){
            printf("%d  ",temp->data);
            temp=temp->prev;
        }
    }

}
int main(){
    //set node pointer value
    head=NULL;
    tail=NULL;
    //insert element of linked list
    insert(8);
    insert(7);
    insert(6);
    insert(5);
    insert(4);
    insert(3);
    insert(2);
    insert(1);
    //display all node
    forwardPrint();
    backwardPrint();
}

Output

Forward Element :1  2  3  4  5  6  7  8  
Backward Element :8  7  6  5  4  3  2  1  
//C++ Program to create doubly linked list

#include<iostream> 
using namespace std;
//create structure
struct Node{
    int data;
    struct Node*next;
    struct Node*prev;
};
class DoublyList{
    struct Node*head,*tail;
    public:
        DoublyList();
        void insert(int);
        void forwardPrint();
        void backwardPrint();
};
//set inital value
DoublyList::DoublyList(){
    head=NULL;
    tail=NULL;
}

//insert Node element
void DoublyList:: insert(int value){
  //Create dynamic node
    struct Node*node=new Node;
    if(node==NULL){
        cout<<"Memory overflow\n";
    }else{
        node->data=value;
        node->next=head;
        node->prev=NULL;
        if(head!=NULL){
            head->prev=node;
        }
        if(tail==NULL){
            tail=node;
        }
        head=node;
    }
}
//display element of Node
void DoublyList::forwardPrint(){
    
    if(head==NULL){
        cout<<"Empty linked list";
    }
    else{
        cout<<"\nForward Element :";
        struct Node*temp=head;
        while(temp!=NULL){
            cout<<" "<<temp->data;
            temp=temp->next;
        }
    }

}
//display element of Node
void DoublyList::backwardPrint(){
    
    if(tail==NULL){
        cout<<"Empty linked list";
    }
    else{
        cout<<"\nBackward Element :";
        struct Node*temp=tail;
        while(temp!=NULL){
            cout<<" "<<temp->data;
            temp=temp->prev;
        }
    }

}
int main(){
    DoublyList obj=DoublyList();

    //insert element of linked list
    obj.insert(8);
    obj.insert(7);
    obj.insert(6);
    obj.insert(5);
    obj.insert(4);
    obj.insert(3);
    obj.insert(2);
    obj.insert(1);
    //display all node
    obj.forwardPrint();
    obj.backwardPrint();
}

Output

Forward Element : 1 2 3 4 5 6 7 8
Backward Element : 8 7 6 5 4 3 2 1
//java insert doubly linked list element
public class DoublyList{

  static class Node{
    int data;
    Node next;
    Node prev;
  }
  static Node head,tail;
  //Class constructors
  DoublyList(){
    head=null;
    tail=null;
  } 
  //insert Queue element
  static void insert(int value){
    //Create Queue node
    Node node=new Node();
    node.data=value;
    node.next=head;
    node.prev=null;
    if (head!=null) head.prev=node;
        
    if(tail==null) tail=node;
    head=node;
  }
  //display all Linked List elements
  static void forwardPrint(){
    if(head!=null){
      System.out.print(" Forward Element :");
      Node temp=head;
      while(temp!=null){
        System.out.print("  "+temp.data);
        temp=temp.next;
      }
    }else{
      System.out.println("Empty Linked list"); 
    }
  }

  //display all Linked List elements
  static void backwardPrint(){
    if(head!=null){
      System.out.print("\nBackward Element :");
      Node temp=tail;
      while(temp!=null){
        System.out.print("  "+temp.data);
        temp=temp.prev;
      }
    }else{
      System.out.println("Empty Linked list"); 
    }
  }

  public static void main(String[] args) {
    
    DoublyList obj=new DoublyList();
    obj.insert(8);
    obj.insert(7);
    obj.insert(6);
    obj.insert(5);
    obj.insert(4);
    obj.insert(3);
    obj.insert(2);
    obj.insert(1);
    obj.forwardPrint();
    obj.backwardPrint();
  }
}

Output

 Forward Element :  1  2  3  4  5  6  7  8
Backward Element :  8  7  6  5  4  3  2  1
#Python Insert Doubly linked list node at
#Beginning of linked list
class Node:
  def __init__(self,data):
    self.data=data
    self.next=None
    self.prev=None

#create class Linked    
class Linked:
  def __init__(self):
    #Assign default value
    self.head=None
    self.tail=None
    
  #insert new node to Linked  
  def insert(self,data):
    node=Node(data)
    node.next=self.head
    if(self.head!=None):
      self.head.prev=node
    if(self.tail==None):
      self.tail=node
    self.head=node

  def forwardPrint(self):
    temp=self.head
    print("Forward Elements : "),
    while(temp!=None):
      print(temp.data),
      temp=temp.next
    
    print("\n")
  def backwardPrint(self):
    temp=self.tail
    print("Backward Elements : "),
    while(temp!=None):
      print(temp.data),
      temp=temp.prev
    print("\n")      
#Create Object of class Linked
Linked=Linked()
#Perform Linked operation
Linked.insert(8)
Linked.insert(7)
Linked.insert(6)
Linked.insert(5)
Linked.insert(4)
Linked.insert(3)
Linked.insert(2)
Linked.insert(1)
Linked.backwardPrint()
Linked.forwardPrint()

Output

Backward Elements :  8 7 6 5 4 3 2 1 

Forward Elements :  1 2 3 4 5 6 7 8 

//C# insert doubly linked list node
using System;
public class Node{
   public  int data;
   public  Node next;
   public Node prev;
}
class Program
{
    Node head,tail;
    public Program(){
        head=null;
    }
    public void insert(int data){
        Node element=new Node();
        element.data=data;
        element.next=head;
        element.prev=null;
        if(head!=null) head.prev=element;
        if(tail==null) tail=element;
        head=element;
    }
    public void backwardPrint(){
        if(head==null){
            Console.Write("Empty List");
        }else{
            Console.Write("backward :");
            Node temp=head;
            while(temp!=null){
                Console.Write("  {0}",temp.data);
                temp=temp.next;
            }
            
        }
    }
   
    public void forwardPrint(){
        if(head==null){
            Console.Write("Empty List");
        }else{
            Console.Write("\nForward :");
            Node temp=tail;
            while(temp!=null){
                Console.Write("  {0}",temp.data);
                temp=temp.prev;
            }
            
        }
    }
    static void Main()
    {
        Program obj=new Program();
        obj.insert(8);
        obj.insert(7);
        obj.insert(6);  
        obj.insert(5);
        obj.insert(4);
        obj.insert(3);  
        obj.insert(2);
        obj.insert(1); 
        obj.backwardPrint();
        obj.forwardPrint();
    }
}

Output

backward :  1  2  3  4  5  6  7  8
Forward :  8  7  6  5  4  3  2  1

Circular single linked list

Circular single list is type of single linked list. that are difference only of is last node, next pointer is store the address of newly inserted node. When linked list are hold single node then next pointer is store self address.

Circular Single Linked list 
//C Program Insert linked list 
//node at beginning of Circular single linked list
#include<stdio.h>
#include <stdlib.h> //for malloc function

//create structure
struct Node{
    int data;
    struct Node*next;
};
struct Node*tail;
//function prototype
void insert(struct Node**,int);
void display(struct Node*);
//insert Node element
void insert(struct Node**head,int value){
  //Create dynamic node
    struct Node*node=(struct Node*)malloc(sizeof(struct Node));
    if(node==NULL){
        printf("Memory overflow\n");
    }else{
        node->data=value;
        node->next=*head;
        if(tail==NULL) tail=node;
        *head=node;
        //point last node next reference pointer to first node
        tail->next=*head;
    }
}
//display element of Node
void display(struct Node*head){
    
    if(head==NULL){
        printf("Empty linked list");
    }
    else{
        struct Node*temp=head;
        while(temp){
            printf("%d  ",temp->data);
            temp=temp->next;
            if(temp==head){
                break; //terminate loop
            }
        }

    }
}
int main(){
    tail=NULL;
    //create node pointer
    struct Node*head=NULL;
    //insert element of linked list
    insert(&head,8);
    insert(&head,7);
    insert(&head,6);
    insert(&head,5);
    insert(&head,4);
    insert(&head,3);
    insert(&head,2);
    insert(&head,1);
    //display all node
    display(head);
}

Output

1  2  3  4  5  6  7  8 
//C Program insert linked list 
//node at beginning of Circular single linked list
#include<iostream>
using namespace std;

//create structure
struct Node{
    int data;
    struct Node*next;
};
class CircularList{
    Node *head,*tail;
public:
    CircularList();
    void insert(int);
    void display();
};
CircularList::CircularList(){
    head=NULL;
    tail=NULL;
}

//insert Node at beginning of list 
void CircularList:: insert(int value){
  //Create dynamic node
    struct Node*node=new Node;
    if(node==NULL){
        cout<<"Memory overflow"<<endl;
    }else{
        node->data=value;
        node->next=head;
        if(tail==NULL) tail=node;
            head=node;
        //point last node next reference 
        //pointer to first node
        tail->next=head;
    }
}
//display element of Node
void CircularList:: display(){
    
    if(head==NULL){
        cout<<"Empty linked list";
    }
    else{
        struct Node*temp=head;
        while(temp){
            cout<<"  "<<temp->data;
            temp=temp->next;
            if(temp==head){
                break; //terminate loop
            }
        }

    }
}
int main(){
    CircularList obj=CircularList();
    //insert element of linked list
    obj.insert(8);
    obj.insert(7);
    obj.insert(6);
    obj.insert(5);
    obj.insert(4);
    obj.insert(3);
    obj.insert(2);
    obj.insert(1);
    //display all node
    obj.display();
}

Output

1  2  3  4  5  6  7  8 
//C Program insert linked list 
//Node at beginning of Circular single linked list
#include<iostream>
using namesspace std;

//create structure
struct Node{
    int data;
    struct Node*next;
};
class CircularList{
    Node *head,*tail;
public:
    CircularList();
    void insert(int);
    void display();
};
CircularList::CircularList(){
    head=NULL;
    tail=NULL;
}

//insert Node at beginning of list 
void CircularList:: insert(int value){
  //Create dynamic node
    struct Node*node=new Node;
    if(node==NULL){
        cout<<"Memory overflow"<<endl;
    }else{
        node->data=value;
        node->next=head;
        if(tail==NULL) tail=node;
            head=node;
        //point last node next reference 
        //pointer to first node
        tail->next=head;
    }
}
//display element of Node
void CircularList:: display(){
    
    if(head==NULL){
        cout<<"Empty linked list";
    }
    else{
        struct Node*temp=head;
        while(temp){
            cout<<"  "<<temp->data;
            temp=temp->next;
            if(temp==head){
                break; //terminate loop
            }
        }

    }
}
int main(){
    CircularList obj=CircularList();
    //insert element of linked list
    obj.insert(8);
    obj.insert(7);
    obj.insert(6);
    obj.insert(5);
    obj.insert(4);
    obj.insert(3);
    obj.insert(2);
    obj.insert(1);
    //display all node
    obj.display();
}

Output

Linked list Element :  1  2  3  4  5  6  7  8
#Python Insert  linked list node at
#Beginning of Circular linked list
class Node:
  def __init__(self,data):
    self.data=data
    self.next=None

#create class CircularList    
class CircularList:
  def __init__(self):
    #Assign default value
    self.head=None
    self.tail=None
    
  #insert new node to Linked list  
  def insert(self,data):
    node=Node(data)
    node.next=self.head
    self.head=node
    if self.tail==None:
      self.tail=node
    self.tail.next=node

  def display(self):
    temp=self.head
    print("Linked list Elements : "),
    while(temp!=None):
      print(temp.data),
      temp=temp.next
      if(temp==self.head):
        break;

    print("\n")

def main():
  #Create Object of class CircularList
  obj=CircularList()
  #Perform obj operation
  obj.insert(8)
  obj.insert(7)
  obj.insert(6)
  obj.insert(5)
  obj.insert(4)
  obj.insert(3)
  obj.insert(2)
  obj.insert(1)
  obj.display()    

if __name__ == '__main__':
  main()
//C# insert node at beginning of 
//Circular single linked list
using System;
public class Node{
   public  int data;
   public  Node next;
}
class Program
{
    Node head,tail;
    public Program(){
        head=null;
        tail=null;
    }
    public void insert(int data){
        //make a new node
        Node element=new Node();
        element.data=data;
        element.next=head;
        head=element;
        if(tail==null) tail=element;

        tail.next=head;
    }
    //display node elements
    public void display(){
        if(head==null){
            Console.Write("Empty List");
        }else{
            Console.Write("Node Elements :");
            Node temp=head;
            while(temp!=null){
                Console.Write("  {0}",temp.data);
                temp=temp.next;
              if(temp==head) break;
            }
            
        }
    }
    static void Main()
    {
        Program obj=new Program();
        //add linked list items
        obj.insert(8);
        obj.insert(7);
        obj.insert(6);  
        obj.insert(5);
        obj.insert(4);
        obj.insert(3);  
        obj.insert(2);
        obj.insert(1); 
        obj.display();
    }
}

Output

Node Elements :  1  2  3  4  5  6  7  8

Circular doubly linked list

Circular Doubly linked list is very similar to doubly linked list, that are only difference is first node prev pointer (previous reference pointer ) is store the address of last node and last node next pointer are used to stored the address of first node of linked list.

Circular doubly Linked list

Operation of Linked list

There are Three main operation of linked list. insert node, search node and delete the node.

Insertion: Insert node of linked list there are possible three different situations. first one is insert node at beginning of linked list. second one is insert node at end of given linked list. and third one is insert node at between of two linked list. In above all program are inserted node at beginning of linked list position. so using of this reference you can are inserted node at end and in between two nodes.

Search data:Finding a specific node element its called searching operation on linked list there are need to teversal linked list to head node to last node and compare node element value. if value are exist found that means search operation is successful done. otherwise node are not exist.

deletion of linked list node there are three possibility of position for as follows. delete beginning node, delete intermediate node, and delete last node.

Complexity Overview

In linked list there are various possibility to insert and delete nodes. here include very common situations.

Operation Complexity
Insertion node at beginning O(1)
Insertion node at end O(1)
Insertion node at middle O(n)
Deletion a node at beginning O(1)
Deletion a node at end O(1)
Deletion a node at middle O(n)
Find node O(n)
Space O(n)
Last updated on by Kalkicode




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment