Linked lists are a fundamental data structure used in computer science, and Java provides its own linked list implementation. However, there may be times when you want to create your own custom linked list. Implementing a custom generic linked list in Java can be a valuable learning experience and provide greater flexibility, performance, and an opportunity to practice your coding skills. This article will discuss the benefits of creating a custom linked list and how to implement one in Java.
Benefits of creating your own custom generic linked list
You might wonder why we would create our custom generic linked list even though Java provides a generic linked list that can smoothly perform basic operations. There can be many reasons to do so based on one’s requirements.
- Customization: The built-in Java LinkedList may not exactly meet your needs. For example, you might need a linked list that behaves differently or provides additional functionality.
- Performance: In certain cases, a custom linked list implementation may be more efficient than Java’s implementation. For example, if you have a specific use case that requires a certain data structure or algorithm, you can optimize the implementation for that specific case.
Creating a custom generic linked list
We will create our linked list in a series of steps.
- How to make a generic linked list?
- How to make our internal node structure?
- How to keep track of the head node?
- How to add new nodes in the linked list?
- How to print a linked list?
Let’s look at them one by one.
How to make a generic linked list?
We will use the generic feature of java and make our class in the following way –
public class LinkedList<T> {
}
As we have used Type T, our class can accept any data type now and make our linked list generic.
How to make our internal node structure?
A Linked List usually comprises a data field and a next field.
- “data” field holds the value, or we can say it contains the actual data.
- “next” field contains the information about the next node, or we can say it points to the next node in the linked list
Below is the structure for the same –
class Node {
private T value; // the data value of type T
private Node next; // to point to the next node
//constructor
private Node(T value) {
this.value = value;
this.next = null;
}
}
We have made one “Node” class representing a node in the linked list. Node class constructor is a parameterized constructor accepting a single parameter of any data type.
Right now, our Linked List class looks like this –
public class LinkedList<T> {
class Node {
private T value;
private Node next;
private Node(T value) {
this.value = value;
this.next = null;
}
}
}
How to keep track of the head node?
A head node is the first node in the linked list.
After making our linked list class generic and describing the node structure, the next thing is to know how we will keep track of our head node while making a linked list.
We will make a new data member named head of type Node in our Linked List class.
private Node head;
public class LinkedList<T> {
private Node head;
class Node {
private T value;
private Node next;
private Node(T value) {
this.value = value;
this.next = null;
}
}
}
Now, the head variable in our class will keep track of the first node in our Linked List and in this way, we can always access the head node and its content.
How to add new nodes in the linked list?
We know that Linked List is made up of nodes. So, now the question is, how do we add nodes to our List?
We Will make an add() method, which could add the nodes to our list.
- add() method should only have one argument to accept the value to be added in the node.
- It should accept any data type so that our list can be generic.
- And it should add the node at the end of the linked list.
Creating add method
We can make a new Node using the below line of code.
Node node = new Node(element);Add the newly created node to the Linked List. As the Linked list is empty, so the newly created node will become the head using the code below.
void add(T element) {
Node node = new Node(element);
// adding head node
if (this.head == null) {
this.head = node;
}
}
Any more nodes will be added to the end of the Linked List. If a node’s next variable value is null, it means the current node is the last node of the list, and any new node will be added afterwards.
So, we will iterate until the last node and add a new node, as shown by the code below.
Node iterator = this.head;
while (iterator.next != null) {
iterator = iterator.next;
}
iterator.next = node;
Note: The above code complexity is O(n), where n is the length of the Linked List. We can optimize it by storing the last node so we don’t have to iterate the whole list to reach the last node. This will make our code run faster and in O(1) complexity.
Here is our final add() method.
void add(T element) {
Node node = new Node(element);
// adding head node
if (this.head == null) {
this.head = node;
}
// adding other nodes
else {
Node iterator = this.head;
while (iterator.next != null) {
iterator = iterator.next;
}
iterator.next = node;
}
}
How to print a linked list?
We can iterate over the whole list to print the data individually until no node is left.
void print() {
Node iterator = head;
while (iterator != null) {
System.out.println(iterator.value + " ");
iterator = iterator.next;
}
}
So, here is our custom generic Linked List, which can add elements and print the whole list.
public class LinkedList<T> {
private Node head;
class Node {
private T value;
private Node next;
private Node(T value) {
this.value = value;
this.next = null;
}
}
void add(T element) {
Node node = new Node(element);
if (this.head == null) {
this.head = node;
} else {
Node iterator = this.head;
while (iterator.next != null) {
iterator = iterator.next;
}
iterator.next = node;
}
}
void print() {
Node iterator = head;
while (iterator != null) {
System.out.println(iterator.value + " ");
iterator = iterator.next;
}
}
public static void main(String[] args) {
LinkedList<Integer> integerLinkedList = new LinkedList<>();
integerLinkedList.add(10);
integerLinkedList.add(20);
integerLinkedList.add(30);
integerLinkedList.print();
LinkedList<String> stringLinkedList = new LinkedList<>();
stringLinkedList.add("Hello");
stringLinkedList.add("Codekru");
stringLinkedList.print();
}
}
Output –
10
20
30
Hello
Codekru
We have just written functions to add elements to a list and print it to keep our post simple. You can also similarly make methods to remove nodes or print the length of the linked list or any other.
I hope you find this helpful. If you have any doubts or concerns, you can write to us in the comments or mail us at admin@codekru.com