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.