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