Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email
Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!

How to Implement Generic LinkedList in java

Last Updated on July 31, 2023 by Mayank Dham

Mastering the Linked List data structure is of utmost importance when gearing up for interviews. A comprehensive grasp of Linked Lists can offer significant advantages during coding interviews.

In this tutorial, we will learn how to implement a generic linked list in java that can work with multiple data types. A Linked List is a linear Data Structure, which consists of a group of nodes, which are stored at random addresses. Each node consists of 2 parts:

Data: The Data which is stored at the particular address.
Reference: The address of the next node of the linked list.

What is a Generic Linked List in Java?

A generic linked list, also known as a template linked list or a polymorphic linked list, is a data structure that allows for the storage of elements of different data types in a single linked list. In programming languages that support generics or templates, such as C++ or Java, a generic linked list can be created using templates or generic classes.

The idea behind a generic linked list is to provide a flexible and reusable data structure that can hold elements of various data types without the need to create separate linked lists for each data type. This allows for code reusability and simplifies the implementation of algorithms that need to work with different types of data.

For example, a generic linked list could store integers, strings, or custom objects, making it a versatile tool in various programming applications. The ability to work with different data types while maintaining the structure and functionality of a linked list makes generic linked lists a powerful and efficient data structure in modern programming languages.

In this article, we will learn how to implement a generic LinkedList class that can work with multiple data types.

We will implement the following member functions in our LinkedList class:

  • addNode(T data) – This method will add a new element at the end of LinkedList.
  • addNode(int position, T data) – This method will add a new element at a particular position in the LinkedList.
  • removeNode(T key) – This method will remove a node from the LinkedList.
  • clearList() – This method will clear the whole LinkedList.
  • isEmpty() – This method will check whether a LinkedList is empty or not.
  • length() – This method will return the length of the LinkedList.

Note: Here, T represents the type of data which will be stored in the linked list.

Example 1: Implementation of add(T data), add(int position, T data), removeNode(T key)

Code:

class node<t> {

    // Stores data of the node
    T data;
    // Store address of the node
    node<t> next;

    // Constructor
    node(T data) {

        this.data = data;
        this.next = null;
    }
}

class list<t> {

    // Head of the node
    node<t> head;

    //Store length of the linked list
    private int len = 0;

    // Constructor
    list() {
        this.head = null;
    }

    // Method addNode(T data): This method add a new element at the end
    void addNode(T data) {

        // creating a new generic node
        node<t> temp = new node<>(data);

        // check if list is empty
        if (this.head == null) {
            head = temp;
        }

        // if list exists
        else {

            node<t> X = head;

            // Iterate the List
            while (X.next != null) {
                X = X.next;
            }

            X.next = temp;
        }

        // Increase the len after adding new node
        len++;
    }

    // Method addNode(int pos,T data): It will add a new element at a particular position
    void addNode(int pos, T data) {

        // Check position if its valid or not
        if (pos > len + 1) {

            System.out.println("Position not found");
            return;
        }

        // if new node is to be added in the beginning
        if (pos == 1) {
            node<t> temp = head;
            head = new node<t>(data);
            head.next = temp;
            return;
        }

        // Temporary node to store previous head
        node<t> temp = head;
        node<t> prev = new node<t>(null);
        // Interating
        while (pos - 1 > 0) {
            prev = temp;
            temp = temp.next;
            pos--;
        }
        prev.next = new node<t>(data);
        prev.next.next = temp;
    }

    // Method removeNode(T key): It will remove a node from the LinkedList
    void removeNode(T key) {
        node<t> prev = new node<>(null);
        prev.next = head;
        node<t> next = head.next;
        node<t> temp = head;

        // This will check whether the value is present or not
        boolean exists = false;

        if (head.data == key) {
            head = head.next;

            // Node is present which we will want to remove
            exists = true;
        }

        while (temp.next != null) {

            // Convert the value to be compared to string
            if (String.valueOf(temp.data).equals(String.valueOf(key))) {

                prev.next = next;
                exists = true;

                break;
            }
            prev = temp;

            temp = temp.next;

            next = temp.next;
        }

        if (exists == false && String.valueOf(temp.data).equals(String.valueOf(key))) {
            prev.next = null;

            exists = true;
        }

        // When the node which we want to delete exists
        if (exists) {

            // reduce the len of linked list
            len--;
        }

        // If it does not exist
        else {
            System.out.println("Not found in linked list");
        }
    }

    public String toString() {

        String S = "{";

        node<t> X = head;

        if (X == null)
            return S + "}";

        while (X.next != null) {
            S += String.valueOf(X.data) + "->";
            X = X.next;
        }

        S += String.valueOf(X.data);
        return S + "}";
    }
}

public class LinkedList {
    public static void main(String[] args) {
        // Creating new linked list of int type
        list<integer> list1 = new list<>();
        list1.addNode(1);
        list1.addNode(25);
        list1.addNode(69);

        list1.addNode(2, 35);

        System.out.println("Original list 1: " + list1);

        list1.removeNode(69);

        System.out.println("New list 1 after removing a node from the list: " + list1);

        System.out.println();

        // Create new linked list of string type
        list<string> list2 = new list<>();

        list2.addNode("prepbytes");
        list2.addNode("Algorithm");

        System.out.println("Original list 2: " + list2);

        list2.addNode(1, "Data");

        System.out.println("New list 2 after adding element: " + list2);
    }
}

Output:
Original list 1: {1->35->25->69}
New list 1 after removing a node from the list: {1->35->25}

Original list 2: {prepbytes->Algorithm}
New list 2 after adding element: {Data->prepbytes->Algorithm}

Example 2: Implementation of addNode(T data), isEmpty(), clearList(), length().
Code:

class node<t> {

    // Stores data of the node
    T data;
    // Store address of the node
    node<t> next;

    // Constructor
    node(T data)
    {

        this.data = data;
        this.next = null;
    }
}
class list<t> {

    // Head of the node
    node<t> head;
    
    private int len = 0;

    //constructor
    list() { this.head = null; }
    
    // Method addNode(T data): This method adds a new element at the end
    void addNode(T data)
    {

        // Creating a new generic node
        node<t> temp = new node<>(data);

        if (this.head == null) {
            head = temp;
        }

        else {

            node<t> X = head;

            // Iterate the List
            while (X.next != null) {
                X = X.next;
            }

            X.next = temp;
        }

        // Increase the len after adding new node
        len++;
    }
    // Method clearList(): It will clear the Linked List
    void clearList()
    {
        head = null;
        len = 0;
    }
 
    // Method isEmpty(): It will check whether a list is empty or not
    boolean isEmpty()
    {
        if (head == null) {
            return true;
        }
        return false;
    }
    // Method length(): It will return the length of the linked list
    int length() { 
        return this.len; }

    public String toString()
    {

        String S = "{";

        node<t> X = head;

        if (X == null)
            return S + "}";

        while (X.next != null) {
            S += String.valueOf(X.data) + "->";
            X = X.next;
        }

        S += String.valueOf(X.data);
        return S + "}";
    }
}

public class LinkedList {
    public static void main(String[] args)
    {
        // Creating new  linked list
        list<integer> list1 = new list<>();
        list1.addNode(1);
        list1.addNode(25);
        list1.addNode(69);
        
        

        System.out.println("Original list 1 :"+list1);

        System.out.println("Length of linked list :"+list1.length());

        System.out.println("is list empty:"+list1.isEmpty());
        
        list1.clearList();
        System.out.println("list 1 after clearList method:"+list1);
        
        System.out.println();

        // Create new linked list of string type
        list<string> list2 = new list<>();

        list2.addNode("prepbytes");
        list2.addNode("Algorithm");
        
        System.out.println("Original list 2: "+list2);
        System.out.println("Length of linked list: "+list2.length());

        System.out.println("is list empty: "+list2.isEmpty());
        
        list2.clearList();
        System.out.println("list 2 after clearList method: "+list2);
    }
}

Output:
Original list 1 :{1->25->69}
Length of linked list :3
is list empty:false
list1 after clearList method:{}

Original list 2: {prepbytes->Algorithm}
Length of linked list: 2
is list empty: false
list 2 after clearList method: {}

Time complexity: O(N) for addNode() and removeNode() operations and O(1) for clearList(), isEmpty() and length() operations.

Conclusion
This process of implementation of generic linked list in Java provides a versatile and reusable data structure that can store elements of different data types. By utilizing generics, developers can create a single linked list implementation capable of accommodating various data types, promoting code reusability, and ensuring type safety. Implementing a generic linked list in Java is a fundamental skill for programmers, allowing them to create efficient and adaptable data structures suitable for a wide range of applications.

Here are some FAQs related to the implementation of generic linked list in Java.

FAQs related to how to implement a generic linked list in Java:

Q1. What is a generic linked list in Java?
A generic linked list in Java is a data structure that can hold elements of any data type using generics. It allows for the creation of a single linked list implementation that can store diverse data types efficiently and safely.

Q2. How do you declare a generic linked list class in Java?
To declare a generic linked list class in Java, use angle brackets and a placeholder type (e.g., ). For example, class LinkedList { … } would create a generic linked list class with a type parameter T.

Q2. How do I declare a generic linked list in Java?
To declare a generic linked list in Java, you can use the following syntax: LinkedList, where T is the placeholder for the data type.

Q3. Can I store any data type in a generic linked list?
Yes, a generic linked list can store elements of any data type, including primitive data types, objects, or custom data types defined by classes.

Q4. How does Java’s generics ensure type safety in a generic linked list?
Java’s generics provide compile-time type checking, ensuring that only elements of the specified data type (or its subclasses) can be inserted into the generic linked list.

Q5. How do generics ensure type safety in a linked list?
Generics ensure type safety in a linked list by enforcing that elements added to the list must match the specified type. The Java compiler performs type-checking at compile-time, reducing the risk of runtime errors due to data type mismatches.

Q6. Can I use custom objects with a generic linked list?
Yes, generic linked lists can store custom objects. Simply provide the custom class type as the generic parameter when declaring the linked list class.

Q7. How do I implement basic operations like insertion and deletion in a generic linked list?
In a generic linked list implementation, you can define methods for inserting, deleting, searching, and other common operations. These methods can utilize the generic type parameter to handle elements of any data type.

Leave a Reply

Your email address will not be published. Required fields are marked *