How to Implement Generic LinkedList in java

Introduction

One of the most crucial data structures to learn while preparing for interviews is the Linked List. In a coding interview, having a thorough understanding of Linked Lists might be a major benefit.

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.

LinkedList can not contain only one type of data type, but it can contain String, Integer, Float, etc., so to overcome this, we have to use “generic list” which can store values of any type. Generic allows us to store data of any data type such as String, Integer, Float, etc., in the linked list.

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 {

    // Stores data of the node
    T data;
    // Store address of the node
    node next;

    // Constructor
    node(T data) {

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

class list {

    // Head of the node
    node 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 temp = new node<>(data);

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

        // if list exists
        else {

            node 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 temp = head;
            head = new node(data);
            head.next = temp;
            return;
        }

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

    // Method removeNode(T key): It will remove a node from the LinkedList
    void removeNode(T key) {
        node prev = new node<>(null);
        prev.next = head;
        node next = head.next;
        node 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 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 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 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 {

    // Stores data of the node
    T data;
    // Store address of the node
    node next;

    // Constructor
    node(T data)
    {

        this.data = data;
        this.next = null;
    }
}
class list {

    // Head of the node
    node 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 temp = new node<>(data);

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

        else {

            node 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 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 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 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.

This article explains how to implement generic Linked List in java. If you want to solve more questions on Linked List, which our expert mentors curate at PrepBytes, you can follow Prepbytes (Linked Lists).
How to Implement Generic LinkedList in java.md
Displaying How to Implement Generic LinkedList in java.md.

Previous post C program to Reverse a Linked List
Next post Deleting A Node In A Linked List In C

Leave a Reply

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