Java – Implement singly linked list

In this article, we will implement a singly linked list with our own classes and without using java Collection framework.
Though java provides its own LinkedList class, with methods to add, remove a node, traverse the list etc., but it is important to implement it ourselves for a better understanding.
Also, it is an important interview question.

Singly Linked List
A singly linked list consists of nodes connected to each other. Each node contains a value and a reference to the next node as shown below.
Note that the last node references no node and so its next reference is null.
Linked List Implementation
A linked list consists of multiple nodes. Each node consists of a value and a reference to the next node.

To implement a linked list, we will design two classes:
1. Class that represents a single node
2. Class that represents the linked list and contains methods to add and remove nodes, modify value of nodes, get size of linked list etc.

1. Node implementation in java
A node contains a value and a reference to the next node. So, below is the class that represents a single node of linked list.

class Node {
  private int value;
  private Node next;
 
  // constructor
  public Node(int value) {
    this.value = value;
  }
}

Note that next will hold reference to next node and hence, it is of type Node.
2. Linked List implementation
Below is the class that represents a linked list.

public class LinkedList {

  private Node first;
  private Node last;
  private int size;

}

It contains three instance variables representing first and last nodes of the list. Note that the type of these variables is Node.
Third variable is the size or the total number of nodes in the list. It is initially set to 0, meaning that the list is empty.

Since a node class is tightly coupled to linked list and there is no meaning of accessing a node outside of linked list, Node  class should be nested inside LinkedList as an inner class.

So, updated LinkedList class would be

public class LinkedList { 
  private Node first; 
  private Node last; 
  private int size;

  private class Node {
    private int value; 
    private Node next;
  }
}

where first and last are the first and last nodes of linked list respectively.

Adding nodes to linked list
For adding a node, first create a node. Next, we need to insert it at the appropriate position.

There are two positions to add a node to a linked list.
1. Add node at the beginning of list
There are two scenarios here.
A. The list is empty. In this case, the first and last variables of linked list should be set to the new node.
next of new node will be null as shown below.

B. The list has one or more nodes. In this case, next variable of first node should be set to first and first should be set to new node as shown below.
addFirst() method based on above algorithm is given below

public void addFirst(int value) {
  // create a node
  Node node = new Node(value);
  // check if list is empty
  if (first == null) {
    // set first and last to same node
    first = node;
    last = node;
  } else {
    // point next of new node to first
    node.next = first;
    // make new node as first node
    first = node;
  }
  size++;
}

2. Add node to the end of list
Create a new node. Then check for the list to be empty.
A. If it is empty, set first and last to the node, since it will be the only node as below.

B. If the list is not empty, point next of last node to this node. Set last to this node, since this will now be the end node. Refer below image

addLast() method based on the above algorithm is given below

public void addLast(int value) {
  Node node = new Node(value);
  // check if list is empty
  if (first == null) {
    // set first and last to this node
    first = node;
    last = node;
  } else {
    // point last node to new node
    last.next = node;
    // make new node as last
    last = node;
  }
}

Removing node from linked list
Removing or deleting a node involves breaking the reference of the deleted node and of the node that points to it.
1. Removing the first node
To remove the first node, set the next reference of the deleted node to the first node reference.
This will make the second node as the first and break the reference of the deleted node, making it eligible for garbage collection as shown below

Notice how the first(or deleted) node becomes isolated.
Code for removeFirst() method is given below.

public void removeFirst() {
  // check for empty list
  if(first == null) {
    throw new NoSuchElementException();
  }
  /* assign first to the node 
  referenced by its next */
  first = first.next;
}

2. Removing the last node
To remove the last node,
A. Find the node before the last node,
B. Set its next to null.
C. Set last to the node found in Step A, as shown in the image below

To find the second last node, we need to traverse the list starting from the first using a while loop.
Loop will iterate till the next of the current node is null, which means the end of list.

In every loop iteration, next  of current node is compared with the last variable, which holds the reference to the last node.
As soon as both are equal, we get the second last node and the loop is terminated with break statement.
This is because next of second last node will be pointing to the last node of the list.

Once we find the second last node(Step A), it can be removed using Steps B and C. removeLast() method implementation is given below.

public void removeLast() {
  // temp variable pointing to first node
  Node current = first;
  // iterate till the last node
  while(current.next != null) {
   // check if it's the second last node
   if(current.next ==  last) {
     break;
   }
   // move current node forward
   current = current.next;
 }
 // make second last node, the last node
 last = current;
 // set next of second last node to null
 last.next = null;
 // reduce 
 size--;
}

Find index of node
Next, we need to find the index of a node with given value.
For this, iterate over the list from start till end and increment an integer counter.
In every iteration, compare the value of current node with this value. If the value of the node and the value to compare match, terminate the loop.

indexOf() method is written below.

public int indexOf(int value) {
  int index = 0;
  // temp variable pointing to first node
  Node current = first;
  while(current != null) {
    /* compare the value of node 
    with required value */
    if(current.value == value) {
      return index; 
  }
  // increase counter
  index++;
  // move to next node
  next = current.next;
  }
  // node not found
  return -1;
}

indexOf() will return -1 if there is no node with the given value.

Check node of value with contains()
This method will accept a value and check if the node with this value exists in the list or not.
It will return true if the value is found and false, if no node with this value is present in the list.

To implement contains(), we can use indexOf() and compare the returned value with -1.
If it is -1, node is not present and contains() will return false, otherwise it will return true.

public boolean contains(int value) {
  return indexOf(value) != -1;
}

Size of list
In this section, we will implement size() method. It will return the size or length or the total number of elements in the list.

It will simply return the value of variable size of LinkedList class. We have been increasing this value of this variable every time a new node is added and decreasing it, when a node is removed.
Thus, size contains the total number of nodes in the list.

public boolean size() {
  return size;
}

There is another way of implementing size(), where we need to iterate the linked list starting from the beginning till the end and increasing a counter variable by 1 in every iteration.

In this case, we would not need to maintain size variable. But, the time complexity with this approach would be O(n) while the time complexity of above method is O(1), which is obviously better.

Delete node by value
This method should accept a value and delete the node whose value matches it. Deleting a node means removing its reference with other nodes.

There are two scenarios here:
A. Value of first node matches with the value.
For this, compare the value of first with the value. If both are the same, point first to first.next and set first.next to null breaking all the references of the first node.
Refer the image below.

This is the same as removing first node.

B. Iterate the list from the beginning and in each iteration compare the value of the next node. If values match, point the next of current node to the next of the next node.
This will break the reference of the next node and it will stand deleted. We also need to check if the next node of the current node is the last node of the list.

In this case, last will point to the next node. Code for deleteByValue() is given below

public void deleteByValue(int value) {
  Node current = first;
  // check if first node matches value
  if(current.value == value) {
    // move first reference to next
    first = current.next;
    /* set next reference of first to null
    This isolates the first node */
    current.next = null;
    // node deleted, return back
    return;
  }
  // loop further from second node
  while(current.next != null) {
    // check if next node matches
    if(current.next.value == value) {
      // check for last node
      if(current.next == last) {
        // mark this node as last
        last = current;
        // isolate the node to delete
        current.next = null;
      } else {
        // update next node to the one after deleted node
        current.next = current.next.next;
      }
      size--;
      // node deleted, terminate the loop
      break;
    }
    // check for next node 
    current = current.next;
  }
}

Printing the list
Finally, we implement a method that prints the value of each node of the list as below.

public void print() {
  Node current = first;
  System.out.println("List: [");
  while(current != null) {
    System.out.println("  Node: [ value = " + current.value+" ]");
    current = current.next;
  }
  System.out.println("]");
}

Checking empty list
This method will check if there are any nodes in the list, that is, it is empty or not.
There are two ways to implement this method as per our current design.
1. Check if first variable is null. This means that first node is not initialized or the list is empty.
2. Compare size variable with 0, which also implies the list being empty.

public boolean isEmpty() {
  return first == null;
  // OR
  // return size == 0;
}

Linked list example
Below is the complete code of LinkedList class with all the methods implemented above, along with a main program which demonstrates all the operations listed till now.

public class LinkedList { 
  private Node first; 
  private Node last; 
  private int size;

  public void addFirst(int value) { 
    // create a node 
    Node node = new Node(value); 
    // check if list is empty 
    if (first == null) { 
      // set first and last to same node 
      first = node; 
      last = node; 
    } else { 
      // point next of new node to first 
      node.next = first; 
      // make new node as first node 
      first = node; 
    } 
    size++; 
  }

  public void addLast(int value) { 
    Node node = new Node(value);
    // check if list is empty 
    if (first == null) {
      // set first and last to this node 
      first = node; 
      last = node; 
    } else {
      // point last node to new node 
      last.next = node;
      // make new node as 
      last last = node; 
    } 
    size++;
  }

  public void removeFirst() { 
    // check for empty list 
    if(first == null) { 
      throw new NoSuchElementException(); 
    } 
    /* assign first to the node 
    referenced by its next */
    first = first.next; 
    size--;
  }

  public void removeLast() { 
    // temp variable pointing to first node
    Node current = first; 
    // iterate till the last node 
    while(current.next != null) { 
      // check if it is the second last node 
      if(current.next == last) { 
        break; 
      } 
      // move current node forward 
      current = current.next; 
    } 
    // make second last node as the last node 
    last = current; 
    // set the next of second last node to null 
    last.next = null;
    // reduce size
    size--; 
  }

  public int indexOf(int value) { 
    int index = 0; 
    // temp variable pointing to first node Node 
    current = first; 
    while(current != null) { 
      // compare the value of node with required value 
      if(current.value == value) { 
        return index; 
      } 
      // increase counter 
      index++; 
      // move to next node 
      next = current.next; 
    }
    // node not found 
    return -1; 
  }

  public void deleteByValue(int value) { 
    Node current = first;
    // check if first node matches value 
    if(current.value == value) {
      // move reference to first node to next 
      first = current.next;
      // set the next reference of first to null.
      // This isolates the first node 
      current.next = null;
      size--;
      // node deleted, return back 
      return; 
    }
    // loop further from second node 
    while(current.next != null) {
      // check if next node matches 
      if(current.next.value == value) {
        // check for last node 
        if(current.next == last) {
          // mark this node as last 
          last = current;
          // isolate the node to delete 
          current.next = null; 
         } else {
           /* update the next node to
           the one after deleted node */
           current.next = current.next.next; 
         }
         size--;
         // node deleted, terminate the loop 
         break; 
      }
      // check for next node  
      current = current.next; 
    } 
  }

  public boolean size() { 
    return size; 
  }

  public void print() { 
    Node current = first; 
    System.out.println("List: [");
    while(current != null) { 
      System.out.println("  Node: " + 
          "[ value = " + current.value+" ]"); 
      current = current.next; 
    } 
    System.out.println("]");
  }
  

  private class Node { 
    private int value; 
    private Node next; 
  } 
}

Class containing main method for testing our LinkedList class is given below

public class Main {

  public static void main(String[] args) {
    LinkedList list = new LinkedList();
    // add nodes
    list.addFirst(5);
    list.addLast(10);
    list.addLast(15);
    list.addLast(20);
    list.print();
    System.out.println("Size of list: " + list.size());
    System.out.println("Index of node " + 
             "with value 15: " + list.indexOf(15));
    System.out.println("Index of node " + 
             "with value 45: " + list.indexOf(45));
    System.out.println("Is node " +
             "with value 10 present ? " + list.contains(10));
    System.out.println("Is node " + 
             "with value 50 present ? " + list.contains(50));
    System.out.println("\nRemoving last node");

    // remove last node
    list.removeLast();
    list.print();
    System.out.println("Size of list: "+list.size());
    System.out.println("\nRemoving first node");

    // remove first node
    list.removeFirst();
    list.print();
    System.out.println("Size of list: "+list.size());
    System.out.println("\nRemoving node by value");

    // remove by value
    list.removeByValue(10);
    list.print();
    System.out.println("Size of list: "+list.size());
  }
}

Output of this program is

In this article, we implemented a singly linked list using our own custom classes without java Collection api. The linked list has methods to add a node at the beginning and end, remove nodes from beginning, end and with a given value.
It also has methods to check if the list is empty, get the size of list, check if a node with value exists and printing the list.

Hope the article was useful.