Generic Linked List in Java
A linear data structure known as a Linked List stores values in nodes. As we already know, each node has two properties: its value and a link to the node after it if the node exists. The wrapper classes for Linked Lists include Integer, Boolean, Float, Character, Double, etc. Such a "generic" Linked List Data Type that can hold values of any data type is something we can construct.
A Linked List's six main member functions are as follows:
- add (data): It extends the Linked List by one element.
- add (position, data): Adds an element to any legitimate location in the Linked List using the syntax.
- remove(key): eliminates the node from the Linked List that holds the key.
- clear(): eliminates everything in the entire Linked List.
- empty(): function determines whether the Linked List is empty or not.
- length(): it returns the Linked List's length.
Note: The time complexity for adding and subtracting operations is O(N), and for other operations, it is O(1).
An example of an integer Linked List with the values 100, 200, 300, and 400 are shown below.
Program
Filename: Example.java
// Generic Linked List Implementation in Java
// importing every class for input-output
import java.io.*;
// Class
// Main Class
public class Example {
// main driver method
public static void main(String[] args) {
// Integer List
// Creating a new empty Integer Linked List
list < Integer > list1 = new list < > ();
System.out.println("Integer Linked List created as list1 :");
// A list object's above elements being added
// Element 1: 100
list1.add(100);
// Element 2: 200
list1.add(200);
// Element 3: 300
list1.add(300);
// Display message only
System.out.println("list1 after adding 100,200 and 300 :");
// Print the above List of elements
System.out.println(list1);
// Removing 200 from list1
list1.remove(200);
// Display message only
System.out.println("list1 after removing 200 :");
// Print the revised List of elements, then re-display it.
System.out.println(list1);
// String Linked List
// the creation of a new, empty String Linked List
list < String > list2 = new list < > ();
System.out.println( "\nString Linked List created as list2");
// Adding elements to the above List object
// Element 1: hello
list2.add("hello");
// Element 2: world
list2.add("world");
// Display message only
System.out.println("list2 after adding hello and world :");
// Print current elements only
System.out.println(list2);
// Now, adding element 3: "OKAY" at position 2
list2.add(2, "OKAY");
// Display message only
System.out.println("list2 after adding OKAY at position 2 :");
// now print the updated List again
// after inserting the element at the second position
System.out.println(list2);
// Float Linked List
// Creating a new empty Float Linked List
list < Float > list3 = new list < > ();
// Display message only
System.out.println("\nFloat Linked List created as list3");
// Adding elements to the above List
// Element 1: 20.25
list3.add(20.25f);
// Element 2: 50.42
list3.add(50.42f);
// Element 3: 30.99
list3.add(30.99f);
// Display message only
System.out.println("list3 after adding 20.25, 50.42 and 30.99 :");
// Print List elements
System.out.println(list3);
// Display message only
System.out.println("Clearing list3 :");
// Now.clearing this list using the clear() method
list3.clear();
// Now, print the above list again
System.out.println(list3);
}
}
// Class 1
// Helper Class (Generic node class for Linked List)
class node < T > {
// Data members
// 1. Storing value of the node
T data;
// 2. Storing the address of the next node
node < T > next;
// Parameterized constructor to assign value
node(T data) {
// This keyword refers to the current object itself
this.data = data;
this.next = null;
}
}
// Class 2
// Helper class (Generic Linked List class)
class list < T > {
// Generic node instance
node < T > head;
// Data member to store the length of the list
private int length = 0;
// Default constructor
list() {
this.head = null;
}
// Method to add a node at the end of the List
void add(T data) {
// Creating a new node with the given value
node < T > temp = new node < > (data);
// Checking if the list is empty
// and assigning a new value to the head node
if (this.head == null) {
head = temp;
}
// If the list already exists
else {
// Temporary node for traversal
node < T > X = head;
// Iterating till the end of the List
while (X.next != null) {
X = X.next;
}
// Adding a new valued node at the end of the list
X.next = temp;
}
// Increasing length after adding a new node
length++;
}
// Method to add a new node at any given position
void add(int position, T data) {
// Checking if the position is valid
if (position > length + 1) {
// Display message only
System.out.println("Position Unavailable in Linked List");
return;
}
// If the new position is head, then replace the head node
if (position == 1) {
// Temporary node that stores previous head
// value
node < T > temp = head;
// New valued node stored in the head
head = new node < T > (data);
// New head node pointing to the old head node
head.next = temp;
return;
}
// Temporary node for traversal
node < T > temp = head;
// Dummy node with a null value that stores previous
// node
node < T > prev = new node < T > (null);
// iterating to the given position
while (position - 1 > 0) {
// The preceding node is being assigned
prev = temp;
// incrementing next node
temp = temp.next;
// decreasing position counter
position--;
}
// previous node now points to the new value
prev.next = new node < T > (data);
// new value now points to the former current node
prev.next.next = temp;
}
// Method to remove a node from the list
void remove(T key) {
// NOTE
// dummy node is used to represent the node before
// the current node Since in a Single Linked List we
// cannot go backward from a node. We use a dummy
// node to represent the previous node. In case of
// head node, since there is no previous node, the
// previous node is assigned to null.
// Dummy node with a null value
node < T > prev = new node < > (null);
// Dummy node pointing to head node
prev.next = head;
// Next node that points ahead of the current node
node < T > next = head.next;
// Temporary node for traversal
node < T > temp = head;
// Boolean value that checks whether the value be
// deleted exists or not
boolean exists = false;
// If the head node needs to be deleted
if (head.data == key) {
head = head.next;
// Node to be deleted exists
exists = true;
}
// Iterating over Linked List
while (temp.next != null) {
// We convert the value to be compared into Strings
// and then compare using
// String1.equals(String2) method
// Comparing the value of the key and current node
if (String.valueOf(temp.data).equals(
String.valueOf(key))) {
// If the node to be deleted is found previous
// node now points to the next node skipping the
// current node
prev.next = next;
// node to be deleted exists
exists = true;
// As soon as we find the node to be deleted
// we exit the loop
break;
}
// Previous node now points to the current node
prev = temp;
// Current node now points to the next node
temp = temp.next;
// Next node points the node ahead of current
// node
next = temp.next;
}
// Comparing the last node with the given key value
if (exists == false &&
String.valueOf(temp.data).equals(
String.valueOf(key))) {
// If found, the last node is skipped over
prev.next = null;
// Node to be deleted exists
exists = true;
}
// If the node to be deleted exists
if (exists) {
// Length of Linked List reduced
length--;
}
// If the node to be deleted does not exist
else {
// Print statement
System.out.println("Given Value is not present in Linked List");
}
}
// Method to clear the entire Linked List
void clear() {
// Head now points to null
head = null;
// length is 0 again
length = 0;
}
// Method checks whether the List is empty or not
boolean empty() {
// Checking if the head node points to null
if (head == null) {
return true;
}
return false;
}
// Method returns the length of Linked List
int length() {
return this.length;
}
// Method to display the Linked List
// @Override
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 + " }";
}
}
Output
