How to implement linked list data structure in Java using Generics

The linked list is a popular data structure for writing programs and lots of questions from a linked list is asked in various Programming Job interviews. Though Java API or JDK provides a sound implementation of the linked list data structure as java.util.LinkedList, a doubly linked list, you don't really need to implement a linked list of your own for writing production code, but all these interview questions require you to code a linked list in Java for solving coding problems. If you are not comfortable to create your own a linked list, it would be really difficult to solve questions like reversing a linked list or finding middle element of a linked list in one pass.

The Java 5 release also brought another twist on the linked list based questions from Java interviews, now Interviewers expects you to write a type-safe implementation of linked list using Generics.

This raise difficulty level as writing a parameterized class is not easy in Java, and it requires a good understanding of Generics fundamentals like how Generics works and how to use it for creating your own type-safe class.

Btw, 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.

Btw, if you are not familiar with the linked list data structure itself, I suggest you to first go through a comprehensive course on Data Structure and Algorithms like Data Structures and Algorithms: Deep Dive Using Java on Udemy to at least get an understanding of basic data structures like array, linked list, binary tree, hash tables, and binary search tree. That will help you a lot in solving coding problems.




How to implement a linked list in Java using Generics

A 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. It complements array data structure by solving the problems array has like it needs contiguous memory and insertion and deletion is very difficult in an array.

Instead, you can easily add or remove elements from a linked list which makes it an ideal data structure for your growing needs. If you are interested to learn more about array vs linked list data structure, please see the difference between the 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 a linked list.

There are mainly two kinds of linked list, a Singly and Doubly linked list. The 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 a singly linked list, with an append() method which inserts elements at the tail.

Btw, If you are not very familiar with a linked list data structure itself or want to learn more about how linked list works and its pros and cons, you should first read a comprehensive online course on data structure and algorithms like Algorithms and Data Structures - Part 1 and 2 on Pluralsight, one of the best course to learn data structure and algorithms.


How to implement linked list in Java using Generics




Java Program to implement a Singly linked list

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

Here is our Java program to create your own, type-safe linked list in Java.


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.



How to test Singly linked list in Java

/**
  * 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 a linked list in Java using Generics. As a follow-up question, Interview may ask you to implement a circular linked list or implement a 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 in implementing various methods like 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 practice a lot of coding problems on the linked list here, but remember first to start with implementing a singly linked list in Java.

Further Learning
Data Structures and Algorithms: Deep Dive Using Java
Algorithms and Data Structures - Part 1 and 2
Data Structures in Java: An Interview Refresher
Cracking the Coding Interview - 189 Questions with Solutions


Other Array related coding Interview Questions for practice:
  • How to implement a Binary Search tree in Java? (solution)
  • How to check if a linked list contains a loop or cycle in Java? (answer)
  • How to reverse a linked list in Java? (solution)
  • How to reverse a linked list without recursion in Java? (solution)
  • How to find the Kth element from the tail of a linked list? (solution)
  • TOp 30 linked list coding problems from Interviews (questions)
  • How to remove duplicates from an array in Java? [solution]
  • 30+ Array-based Coding Problems from Interviews (questions)
  • How to check if an array contains a number in Java? [solution]
  • 10 Free Data Structure and Algorithms Courses for Programmers [courses]
  • Write a program to find the missing number in integer array of 1 to 100? [solution]
  • How do you reverse an array in place in Java? [solution]
  • 50+ Data Structure and Algorithms Coding Problems from Interviews (questions)
  • 10 Algorithms Books Every Programmer should read [books]
  • 10 Algorithms courses to Crack Coding Interviews [courses]

Thanks for reading this article so far. If you like this article then please share with your friends and colleagues. If you have any question or doubt then please let us know and I'll try to find an answer for you. As always suggestions, comments, innovative and better answers are most welcome.

P. S. - If you are looking for some Free Algorithms courses to improve your understanding of Data Structure and Algorithms, then you should also check the Easy to Advanced Data Structures course on Udemy.

1 comment:

  1. The code is not running. It is giving error 'T cannot be resolved to a type'

    ReplyDelete