Facebook Page Twitter Page LinkedIn Page
× Data Structures Data Structures Resources


A linked list is a linear data structure, in which the elements are stored in the form of a node. Each node contains two sub-elements. A data part that stores the value of the element and next part that stores the pointer to the next node as shown in the below image:

Linked List Node

The first node also known as HEAD is always used as a reference to traverse the list. The last node points to NULL. Linked list can be visualized as a chain of nodes, where every node points to the next node.

Linked List

Types of Linked List

The types of linked list are mentioned below:

  • Singly Linked List: can be traversed only in forward direction.
  • Doubly Linked List: can be traversed in forward and backward directions.
  • Circular Singly Linked List: Last element contains link to the first element as next.
  • Circular Doubly Linked List: Last element contains link to the first element as next and the first element contains link of the last element as previous.

Implementation of Singly Linked List

Representation:

In C, a node can be created using structure. In C++, singly linked list can be created using a class and a Node using structures. The LinkedList class contains Node as class member.

In Java, Python, C# and PHP, singly linked list can be represented as a class and a Node as a separate class. The LinkedList class contains a reference of Node class type.

//node structure
struct Node {
    int data;
    Node* next;
};

class LinkedList {
  public:
    Node* head;
  public:
    //constructor to create an empty LinkedList
    LinkedList(){
      head = NULL;
    }
};
//node structure
struct Node {
  int data;
  struct Node* next;
};
# node structure
class Node:
  #constructor to create a new node
  def __init__(self, data):
    self.data = data
    self.next = None

#class Linked List
class LinkedList:
  #constructor to create an empty LinkedList
  def __init__(self):
    self.head = None
//node structure
class Node {
    int data;
    Node next;
};

class LinkedList {
  Node head;
  //constructor to create an empty LinkedList
  LinkedList(){
    head = null;
  }
};
//node structure
class Node {
  public int data;
  public Node next;
};

class LinkedList {
  public Node head;
  //constructor to create an empty LinkedList
  public LinkedList(){
    head = null;
  }  
};
//node structure
class Node {
  public $data;
  public $next;
}

class LinkedList {
  public $head; 

  //constructor to create an empty LinkedList
  public function __construct(){
    $this->head = null;
  }
};

Create a Singly Linked List

Let us create a simple singly linked list which contains three data nodes.

#include <iostream>
using namespace std;

//node structure
struct Node {
    int data;
    Node* next;
};

class LinkedList {
  public:
    Node* head;
  public:
    //constructor to create an empty LinkedList
    LinkedList(){
      head = NULL;
    } 
};

// test the code  
int main() {
  //create an empty LinkedList
  LinkedList MyList;

  //Add first node.
  Node* first = new Node();
  first->data = 10;
  first->next = NULL;
  //linking with head node
  MyList.head = first;       

  //Add second node.
  Node* second = new Node();
  second->data = 20;
  second->next = NULL;
  //linking with first node
  first->next = second; 

  //Add third node.
  Node* third = new Node();
  third->data = 30;
  third->next = NULL;
  //linking with second node
  second->next = third;

  return 0;
}
#include <stdio.h>
#include <stdlib.h>

//node structure
struct Node {
  int data;
  struct Node* next;
};

// test the code  
int main() {
  //create the head node with name MyList
  struct Node* MyList = NULL;

  //Add first node.
  struct Node* first;
  //allocate second node in the heap
  first = (struct Node*)malloc(sizeof(struct Node));  
  first->data = 10;
  first->next = NULL;
  //linking with head node
  MyList = first; 

  //Add second node.
  struct Node* second;
  //allocate second node in the heap
  second = (struct Node*)malloc(sizeof(struct Node));  
  second->data = 20;
  second->next = NULL;
  //linking with first node
  first->next = second;

  //Add third node.
  struct Node* third;
  //allocate third node in the heap
  third = (struct Node*)malloc(sizeof(struct Node));  
  third->data = 30;
  third->next = NULL;
  //linking with second node
  second->next = third; 

  return 0; 
}
# node structure
class Node:
  #constructor to create a new node
  def __init__(self, data):
    self.data = data
    self.next = None

#class Linked List
class LinkedList:
  #constructor to create an empty LinkedList
  def __init__(self):
    self.head = None

# test the code   
# create an empty LinkedList                 
MyList = LinkedList()

#Add first node.
first = Node(10)
#linking with head node
MyList.head = first

#Add second node.
second = Node(20)
#linking with first node
first.next = second

#Add third node.
third = Node(30)
#linking with second node
second.next = third
//node structure
class Node {
    int data;
    Node next;
};

class LinkedList {
  Node head;
  //constructor to create an empty LinkedList
  LinkedList(){
    head = null;
  }  
};

// test the code 
public class Implementation { 
  public static void main(String[] args) {
    //create an empty LinkedList 
    LinkedList MyList = new LinkedList();

    //Add first node.
    Node first = new Node();
    first.data = 10;
    first.next = null; 
    //linking with head node
    MyList.head = first;

    //Add second node.
    Node second = new Node();
    second.data = 20;
    second.next = null; 
    //linking with first node
    first.next = second;

    //Add third node.
    Node third = new Node();
    third.data = 30;
    third.next = null; 
    //linking with second node
    second.next = third;
  }
}
using System;

//node structure
class Node {
  public int data;
  public Node next;
};

class LinkedList {
  public Node head;
  //constructor to create an empty LinkedList
  public LinkedList(){
    head = null;
  }   
};

// test the code 
class Implementation { 
  static void Main(string[] args) {
    //create an empty LinkedList
    LinkedList MyList = new LinkedList();

    //Add first node.
    Node first = new Node();
    first.data = 10;
    first.next = null; 
    //linking with head node
    MyList.head = first;

    //Add second node.
    Node second = new Node();
    second.data = 20;
    second.next = null; 
    //linking with first node
    first.next = second;

    //Add third node.
    Node third = new Node();
    third.data = 30;
    third.next = null; 
    //linking with second node
    second.next = third; 
  }
}
<?php
//node structure
class Node {
  public $data;
  public $next;
}

class LinkedList {
  public $head;

  //constructor to create an empty LinkedList
  public function __construct(){
    $this->head = null;
  }  
};

// test the code  
//create an empty LinkedList 
$MyList = new LinkedList();

//Add first node.
$first = new Node();
$first->data = 10;
$first->next = null;
//linking with head node
$MyList->head = $first;

//Add second node.
$second = new Node();
$second->data = 20;
$second->next = null;
//linking with first node
$first->next = $second;

//Add third node.
$third = new Node();
$third->data = 30;
$third->next = null;
//linking with second node
$second->next = $third;
?>

Traverse a Singly Linked List

A singly linked list can be traversed using a temp node. Keep on moving the temp node to the next one and displaying its content. At the end of the list, the temp node will become NULL.

#include <iostream>
using namespace std;

//node structure
struct Node {
    int data;
    Node* next;
};

class LinkedList {
  public:
    Node* head;
  public:
    //constructor to create an empty LinkedList
    LinkedList(){
      head = NULL;
    }

    //display the content of the list
    void PrintList() {
      Node* temp = head;
      if(temp != NULL) {
        cout<<"\nThe list contains: ";
        while(temp != NULL) {
          cout<<temp->data<<" ";
          temp = temp->next;
        }
      } else {
        cout<<"\nThe list is empty.";
      }
    }   
};

// test the code  
int main() {
  //create an empty LinkedList
  LinkedList MyList;

  //Add first node.
  Node* first = new Node();
  first->data = 10;
  first->next = NULL;
  //linking with head node
  MyList.head = first;       

  //Add second node.
  Node* second = new Node();
  second->data = 20;
  second->next = NULL;
  //linking with first node
  first->next = second; 

  //Add third node.
  Node* third = new Node();
  third->data = 30;
  third->next = NULL;
  //linking with second node
  second->next = third;

  //print the content of list
  MyList.PrintList();
  return 0; 
}

The above code will give the following output:

The list contains: 10 20 30
#include <stdio.h>
#include <stdlib.h>

//node structure
struct Node {
  int data;
  struct Node* next;
};

//display the content of the list
void PrintList(struct Node* head_ref) {
  struct Node* temp = head_ref;
  if(head_ref != NULL) {
    printf("\nThe list contains: ");
    while (temp->next != NULL) {
      printf("%i ",temp->data);
      temp = temp->next;    
    }
    printf("%i ",temp->data);
  } else {
    printf("\nThe list is empty.");
  }   
}

// test the code  
int main() {
  //create the head node with name MyList
  struct Node* MyList = NULL;

  //Add first node.
  struct Node* first;
  //allocate second node in the heap
  first = (struct Node*)malloc(sizeof(struct Node));  
  first->data = 10;
  first->next = NULL;
  //linking with head node
  MyList = first; 

  //Add second node.
  struct Node* second;
  //allocate second node in the heap
  second = (struct Node*)malloc(sizeof(struct Node));  
  second->data = 20;
  second->next = NULL;
  //linking with first node
  first->next = second;

  //Add third node.
  struct Node* third;
  //allocate third node in the heap
  third = (struct Node*)malloc(sizeof(struct Node));  
  third->data = 30;
  third->next = NULL;
  //linking with second node
  second->next = third; 

  //print the content of list
  PrintList(MyList);
  return 0; 
}

The above code will give the following output:

The list contains: 10 20 30
# node structure
class Node:
  #constructor to create a new node
  def __init__(self, data):
    self.data = data
    self.next = None

#class Linked List
class LinkedList:
  #constructor to create an empty LinkedList
  def __init__(self):
    self.head = None

  #display the content of the list
  def PrintList(self):
    temp = self.head
    if(temp != None):
      print("\nThe list contains:", end=" ")
      while (temp != None):
        print(temp.data, end=" ")
        temp = temp.next
    else:
      print("\nThe list is empty.")

# test the code   
# create an empty LinkedList                 
MyList = LinkedList()

#Add first node.
first = Node(10)
#linking with head node
MyList.head = first

#Add second node.
second = Node(20)
#linking with first node
first.next = second

#Add third node.
third = Node(30)
#linking with second node
second.next = third

#print the content of list 
MyList.PrintList()

The above code will give the following output:

The list contains: 10 20 30
//node structure
class Node {
    int data;
    Node next;
};

class LinkedList {
  Node head;
  //constructor to create an empty LinkedList
  LinkedList(){
    head = null;
  }

  //display the content of the list
  void PrintList() {
    Node temp = new Node();
    temp = this.head;
    if(temp != null) {
      System.out.print("\nThe list contains: ");
      while(temp != null) {
        System.out.print(temp.data + " ");
        temp = temp.next;
      }
    } else {
      System.out.print("\nThe list is empty.");
    }
  }    
};

// test the code 
public class Implementation { 
  public static void main(String[] args) {
    //create an empty LinkedList
    LinkedList MyList = new LinkedList();

    //Add first node.
    Node first = new Node();
    first.data = 10;
    first.next = null; 
    //linking with head node
    MyList.head = first;

    //Add second node.
    Node second = new Node();
    second.data = 20;
    second.next = null; 
    //linking with first node
    first.next = second;

    //Add third node.
    Node third = new Node();
    third.data = 30;
    third.next = null; 
    //linking with second node
    second.next = third;

    //print the content of list
    MyList.PrintList();    
  }
}

The above code will give the following output:

The list contains: 10 20 30
using System;

//node structure
class Node {
  public int data;
  public Node next;
};

class LinkedList {
  public Node head;
  //constructor to create an empty LinkedList
  public LinkedList(){
    head = null;
  } 

  //display the content of the list
  public void PrintList() {
    Node temp = new Node();
    temp = this.head;
    if(temp != null) {
      Console.Write("\nThe list contains: ");
      while(temp != null) {
        Console.Write(temp.data + " ");
        temp = temp.next;
      }
    } else {
      Console.Write("\nThe list is empty.");
    }
  }   
};

// test the code 
class Implementation { 
  static void Main(string[] args) {
    //create an empty LinkedList
    LinkedList MyList = new LinkedList();

    //Add first node.
    Node first = new Node();
    first.data = 10;
    first.next = null; 
    //linking with head node
    MyList.head = first;

    //Add second node.
    Node second = new Node();
    second.data = 20;
    second.next = null; 
    //linking with first node
    first.next = second;

    //Add third node.
    Node third = new Node();
    third.data = 30;
    third.next = null; 
    //linking with second node
    second.next = third;

    //print the content of list
    MyList.PrintList();     
  }
}

The above code will give the following output:

The list contains: 10 20 30
<?php
//node structure
class Node {
  public $data;
  public $next;
}

class LinkedList {
  public $head;

  //constructor to create an empty LinkedList
  public function __construct(){
    $this->head = null;
  }
  
  //display the content of the list
  public function PrintList() {
    $temp = new Node();
    $temp = $this->head;
    if($temp != null) {
      echo "\nThe list contains: ";
      while($temp != null) {
        echo $temp->data." ";
        $temp = $temp->next;
      }
    } else {
      echo "\nThe list is empty.";
    }
  }   
};

// test the code  
//create an empty LinkedList
$MyList = new LinkedList();

//Add first node.
$first = new Node();
$first->data = 10;
$first->next = null;
//linking with head node
$MyList->head = $first;

//Add second node.
$second = new Node();
$second->data = 20;
$second->next = null;
//linking with first node
$first->next = $second;

//Add third node.
$third = new Node();
$third->data = 30;
$third->next = null;
//linking with second node
$second->next = $third;

//print the content of list
$MyList->PrintList();   
?>

The above code will give the following output:

The list contains: 10 20 30