How to implement linked list data structure in Java using Generics? Example (original) (raw)

The linked list is a popular data structure for writing programs and lots of questions from a linked list are 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 creating your own a linked list, it would be really difficult to solve questions like reversing a linked list or finding the 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 expect you to write a type-safe implementation of the linked lists using Generics.

This raises 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 first go through a comprehensive online course on Data Structure and Algorithms to at least get an understanding of basic data structures like an 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 that 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 data and a reference part, the reference part contains an address or next node.

In the 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 the first element and various methods to operate on a linked list.

There are mainly two kinds of a linked list, a Singly and Doubly linked list. The singly linked list allows you to traverse in one direction, while the doubly linked list allows you to traverse in both forward and reverse directions.

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 these best Data Structure and Algorithms courses from Udemy and Coursera.

Java Program to implement a Singly linked list

I have already shared the implementation of the 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 a 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, the 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, the Interviewer is also interested in implementing various methods like inserting a node at the start, middle, and end of a linked list, delete a node from the start, middle, and end of a linked list, sorting elements of a linked list, searching a node in a 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.

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)
Top 10 Algorithms courses for Java Programmers (courses)
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 an 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 it with your friends and colleagues. If you have any questions 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 this list of free Data Structure and Algorithms courses for beginners and experienced programmers.