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