Java - Linked List

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 link to the next node as shown in the below image:

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.

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 Java, 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
class Node {
    int data;
    Node next;
};

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

Create a Singly Linked List

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

//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;
  }
}

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.

//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("The list contains: ");
      while(temp != null) {
        System.out.print(temp.data + " ");
        temp = temp.next;
      }
      System.out.println();
    } else {
      System.out.println("The 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