LinkedList is a linear but somewhat complex data structure in the world of computer science. Linked lists are basically used just normal list or arrays in terms of usage, but the internal working of them is completely different. Let’s look at how the linked list works and implement a linked list using Java.
The items of a linked list are known as Nodes and each nodes have two parts: data and a pointer pointing to the next node of the linked list. The first node is usually called the head and the last node is the tail. In case of a singly linked linked list, the pointer of the tail is null. However, for a circular linked list, the pointer of the tails points to the first node i.e the head. This architecture of a node having two parts change in case of doubly linked list where each node contains three parts. One part stores the data and two other pointer elements which points to the next node and other one pointing to the previous node. Now, let’s implement linked lists using java.
class Node {
int value;
Node next;
Node(int value){
this.value = value;
this.next = null;
}
}We declare a class named Node which contains two elements, the data which will be stored in the value variable and the pointer to the next node which will be stored in the variable next of type Node itself, since it is going to store the details of another node itself.
Like any other data structures we will discuss the common operations on this as well: Insertion of data, Deletion of data (by index and by value), Accessing data (Read).
Add a New Node in Linked List
Let us look at the first method addNode(int value) which inserts a data in the linked list. At first we initialize a new object of the class Node along with the value passed in the constructor, which will act as the new node to be inserted in the linked list. If we find the list to be currently empty, then the head pointer (which is also a node) is found to be null and we set the head as this new initialized node. If the head is not null i.e the list is not empty, we are finding the last node of this list. For this, we initialize another node named tail with the head value. We continue to loop unless the next pointer of this tail is null. If the next pointer of the tail is null it signifies that we are at the last node. Now, we set the next pointer of this tail tail.next as the new node initialized at the very beginning.
public void addNode(int value) {
Node newNodeToAdd = new Node(value);
if(head == null) {
this.head = newNodeToAdd;
} else {
Node tail = this.head;
while (tail.next != null) {
tail = tail.next;
}
tail.next = newNodeToAdd;
}
}Delete a Node in Linked List by value
Now, since we know the process to insert a new node in a linked list, let’s look at the process to delete a node from the linked list by the value of the node. Let us look at the method deleteNodeByIndex(int value) which deletes a node from the linked list based on the value present in the linked list. We start this method by maintaining two pointers, one pointing to the current node and one to the previous node.
The intuition behind deleting a node is to find the node which we intend to delete, then once we find that, we set the next pointer of the previous node to the next node of the current node (which we tend to delete). To make it easier, if we have a linked list A -> B -> C (i.e A pointing to B and B pointing to C), then if we have to delete the node B then we update the next pointer of A to point to C. Thus, the list now becomes A -> C. We start by looping over the list starting from the head to check if the next is not null and the value in the node is not that of the value to be deleted. And we continue to loop by updating the previous node as the current node and the current node to the next node.
public void deleteNodeByValue(int value){
Node currentNode = this.head;
Node previousNode = null;
if(currentNode.value == value) {
this.head = currentNode.next;
} else {
while(currentNode.next != null && currentNode.value != value) {
previousNode = currentNode;
currentNode = currentNode.next;
}
}
// Current node won't be null if the value is found
if (currentNode != null) {
// Setting the previous node's next pointer to the current node's pointer.
// So A->B->C will be come A->C. because A is previousNode and B is the currentNode
previousNode.next = currentNode.next;
} else {
System.out.println("Value to be deleted is not present in the linked list");
}
}Delete a Node in Linked List by index
To delete a node by index, we delete the node by the same principle of deleting a node in a linked list by value. But, here we work on maintaining one variable named index. We initialize index at 0, and continue to increase it’s value by 1 in the loop to traverse the linked list. Here also, we loop the list starting from head and by checking if the next is not null along with the index being the position at which we want to delete the node.
public void deleteNodeByIndex(int index) {
Node currentNode = this.head;
Node previousNode = null;
int indx = 0;
if(index == 0) {
this.head = currentNode.next;
}
while(currentNode.next != null && index != 0) {
if(indx == index) {
// Delete
previousNode.next = currentNode.next;
break;
} else {
previousNode = currentNode;
currentNode = currentNode.next;
indx++;
}
}
}Printing the nodes in a list
Now, we know how we can loop over a linked list starting from the head and checking whether the next node is null or not. To print the linked list, we continue to loop over in the same way and print the value of the node.
public void showList() {
Node currentNode = this.head;
while(currentNode != null) {
System.out.println(currentNode.value);
currentNode = currentNode.next;
}
}Final Program
public class LinkedList {
// Creating a sub class Node. This will act as each node of a linkedlist
class Node {
int value;
Node next;
Node(int value){
this.value = value;
this.next = null;
}
}
Node head;
public void addNode(int value) {
Node newNodeToAdd = new Node(value);
if(head == null) {
this.head = newNodeToAdd;
} else {
Node tail = this.head;
while (tail.next != null) {
tail = tail.next;
}
tail.next = newNodeToAdd;
}
}
public void deleteNodeByValue(int value){
Node currentNode = this.head;
Node previousNode = null;
if(currentNode.value == value) {
this.head = currentNode.next;
} else {
while(currentNode.next != null && currentNode.value != value) {
previousNode = currentNode;
currentNode = currentNode.next;
}
}
// Current node won't be null if the value is found
if (currentNode != null) {
// Setting the previous node's next pointer to the current node's pointer.
// So A->B->C will be come A->C. because A is previousNode and B is the currentNode
previousNode.next = currentNode.next;
} else {
System.out.println("Value to be deleted is not present in the linked list");
}
}
public void deleteNodeByIndex(int index) {
Node currentNode = this.head;
Node previousNode = null;
int indx = 0;
if(index == 0) {
this.head = currentNode.next;
}
while(currentNode.next != null && index != 0) {
if(indx == index) {
// Delete
previousNode.next = currentNode.next;
break;
} else {
previousNode = currentNode;
currentNode = currentNode.next;
indx++;
}
}
}
public void showList() {
Node currentNode = this.head;
while(currentNode != null) {
System.out.println(currentNode.value);
currentNode = currentNode.next;
}
}
public static void main(String[] args) {
LinkedList linkedList = new LinkedList();
linkedList.addNode(11);
linkedList.addNode(12);
linkedList.addNode(13);
linkedList.addNode(14);
linkedList.addNode(15);
linkedList.showList();
System.out.println("--------------------");
linkedList.deleteNodeByIndex(0);
System.out.println("After deleting by index");
linkedList.showList();
System.out.println("--------------------");
linkedList.deleteNodeByValue(14);
System.out.println("After deleting by value");
linkedList.showList();
}
}
Output:
11
12
13
14
15
--------------------
After deleting by index
12
13
14
15
--------------------
After deleting by value
12
13
15