How to implement singly linked list in Java using Generics

Linked list is a popular data structure for writing programs and lots of questions from linked list is asked in various data structures and algorithmic interviews. Though Java provides a sound implementation of Doubly linked list as java.util.LinkedList, all these interview questions require you to code linked list in Java. If you are not comfortable to make a linked list, it would be really difficult to solve questions like reversing a linked list or finding middle element of linked list. Java 5 brought another twist of this kind of questions, now interview expects you to write a type-safe implementation of linked list using Generics. This raise difficulty level as writing parameterized class is not easy in Java, and it requires a good understanding of Generics fundamental.

This question also offers you an opportunity to become a better programmer, solving data structure based questions are a lot better than trying trivial examples, It not only helps to improve programming skill but also prepares you for Java interviews.

I have already shared an implementation of linked list without generics in an earlier post of unit testing linked list in Java, and here we will see a type safe, parameterized implementation of singly linked list in Java.



How to implement linked list in Java using Generics

Linked list is a data structure which is used to store data in the form of nodes. As opposed to an array, which stores data in a contiguous memory location, linked list stores data at different places. Each node contains a data and a reference part, reference part contains an address or next node. In short linked list is a list of nodes, which are linked together. See the difference between linked list and array in Java  for more differences.


In order to create a linked list in Java, we need two classes a Node and a SinglyLinkedList class which contains the address of first element and various methods to operate on linked list.

There are mainly two kinds of linked list, Singly and Doubly linked list. Singly linked list allows you to traverse in one direction, while doubly linked list allows you to traverse in both forward and reverse direction. In this example, we will implement singly linked list, with an append() method which insert elements at the tail.

How to implement linked list in Java using Generics


Java Program to implement Singly linked list 
package datastructure;

/**
  * Type Safe implementation of linked list in Java with Generics.
  * This example creates a singly linked list with append(), isEmpty() and length() method.

  * @author Javin
  */
public class SinglyLinkedList {
    private Node head;  // Head is the first node in linked list

    public boolean isEmpty(){
        return length() == 0;
    }
 
    public void append(T data){
        if(head == null){
            head = new Node(data);
            return;
        }
        tail().next = new Node(data);
    }
 
    private Node tail() {
        Node tail = head;
     
        // Find last element of linked list known as tail
        while(tail.next != null){
            tail = tail.next;
        }      
        return tail;
     
    }
 

 
    @Override
    public String toString(){
        StringBuilder sb = new StringBuilder();
        Node current = head;
        while(current != null){
           sb.append(current).append("-->");
           current = current.next;
        }    
        if(sb.length() >=3){
            sb.delete(sb.length() - 3, sb.length()); // to remove --> from last node
        }
     
        return sb.toString();
    }

    public int length() {
       int length = 0;
       Node current = head;  // Starts counting from head - first node
       while(current != null){
           length ++;
           current = current.next;
       }
       return length;
    }

 
    // Node is nested static class because it only exists along with linked list
    // Node is private because it's implementation detail, and should not be exposed
    private static class Node {
        private Node next;
        private T data;

        public Node(T data) {
            this.data = data;
        }

        @Override
        public String toString() {
            return data.toString();
        }
    }
}

Now, let's create a sample program to test this linked list implementation.

Test Program to test Singly linked list
/**
  * Java program to create singly linked list of String and Integer type,
  * to check type safety.
  * @author Javin
  */
public class LinkedListTest {

    public static void main(String args[]) {

        // Creating Singly linked list in Java of String type
        SinglyLinkedList singlyLinkedList = new SinglyLinkedList();
        singlyLinkedList.append("Java");
        singlyLinkedList.append("JEE");
        singlyLinkedList.append("Android ");
        //singlyLinkedList.append(2); // compile time error
     
        System.out.println("Singly linked list contains : " + singlyLinkedList);
        System.out.println("length of linked list : " + singlyLinkedList.length());
        System.out.println("is this linked list empty : " + singlyLinkedList.isEmpty());
     
        SinglyLinkedList iList = new SinglyLinkedList();
        iList.append(202);
        iList.append(404);
        //iList.append("one"); // compilation error - Trying to insert String on integer list
        System.out.println("linked list : " + iList);
        System.out.println("length : " + iList.length());
    }
 
}

Output
Singly linked list contains: Java-->JEE-->Android
the length of linked list: 3
is this linked list empty: false
linked list: 202-->404
Length: 2

That's all on how to make linked list in Java using Generics. As a follow-up question, Interview may ask you to implement circular linked list, or implement doubly linked list in Java. You can also use them as an exercise to improve your coding skills. Apart from implementing a different kind of linked list, Interviewer is also interested on implementing various methods e.g. insert a node at the start, middle and end of linked list, delete a node from the start, middle and end of linked list, sorting elements of linked list, searching a node in linked list etc. If you have time, you can find a lot of good questions on linked list, but remember first to start with implementing singly linked list in Java.


Further Reading
How to implement Binary Search tree in Java? (solution)
How to find the length of singly linked list? (answer)
How to implement QuickSort using recursion in Java? (solution)
How to check if a linked list contains a loop or cycle in Java? (answer)
How to remove duplicates from ArrayList in Java (solution)
150 Programming Questions and Solutions for Interviews (book)


No comments:

Post a Comment