In this article, we will be creating a LinkedList implementation in Java and perform several operations such as insert a node at the end, insert a node at a given index, delete a node, insert the head node and traversal of a linked list.
What is LinkedList
Linked list is a linear data structure containing interconnected nodes through pointers. Since there is no concept of pointers in Java, each node holds the reference of another node but the last element of the linked list refers to NULL, meaning the end of the list.
Linked list can grow and shrink in size dynamically without wasting any memory. Hence, we prefer a linked list for quick insertion and deletion, unlike an Array List. A linked list is memory efficient but takes some extra memory for pointers that points to the next node.
Linked List Implementation
As discussed above, linked list is an interconnected node, let us define the node first.
Linked List Node Implementation
Following is the type declaration for a node of a linked list.
public class Node { private int data; private Node nextNode; public Node(int data){ this.data = data; } public int getData() { return data; } public void setData(int data) { this.data = data; } public Node getNextNode() { return nextNode; } public void setNextNode(Node nextNode) { this.nextNode = nextNode; } }
It contains a reference of another node called as nextNode and the data as a member variable which can be of any other data type.
Linked List Declaration
The first node of the linked list is called head and this is the starting point of any linked list. Whenever we want to traverse a linked list we start with the head pointer. Below is our class template for linked list.
public class CustomLinkedList {
private Node head;
public CustomLinkedList(){
}
...
}
Now, let us start implementing the different operations that can be performed on a Linked list.
Insertion in a Linked List
Insertion can be done at 3 places in a linked list. We can either insert at head, tail or at a particular location.
Insertion at Head and Tail
The method accepts the data and creates a new Node. If this is the first insertion, then the head is null and hence this new node is assigned to head.
Else, we can traverse the list until we reach the last node. The last node will have the next reference pointing to null. Once, we reached the last node, we can assign the reference of new node to the last node. Now, this new node becomes the last node of the linked list which is again pointing to null.
public void insert(int data){
Node newNode = new Node(data);
if(this.head == null){
head = newNode;
}else {
Node currentNode = head;
while(currentNode.getNextNode() != null){
currentNode = currentNode.getNextNode();
}
currentNode.setNextNode(newNode);
}
}
public void insertHead(int data){
Node newNode = new Node(data);
newNode.setNextNode(head);
head = newNode;
}
Insertion at a Particular Node
Traverse to the node where we want to insert the new node. Now, we can set the next node reference of current node as a next node reference of the new node to be inserted and the next node reference of current node as the new node that to be inserted.
public void insertAt(int index, int data){
Node nodeToBeInserted = new Node(data);
Node node = head;
for(int i = 0; i< index -1; i++){
node = node.getNextNode();
}
nodeToBeInserted.setNextNode(node.getNextNode());
node.setNextNode(nodeToBeInserted);
}
Deletion of a Node
To delete a node, simply assign the next reference of a particular node to be deleted to the next node reference of the previous node.
public void deleteNodeAt(int index){
Node node = head;
for(int i = 0; i< index -1; i++){
node = node.getNextNode();
}
node.setNextNode(node.getNextNode().getNextNode());
}
Traversing a Linked List
We can recursively traverse a linked list using while loop untill we reach the last node. The last node of a linked list points to NULL object.
public void display(){
if(head != null){
Node currentNode = head;
while(currentNode.getNextNode() != null){
System.out.println(currentNode.getData());
currentNode = currentNode.getNextNode();
}
System.out.println(currentNode.getData());
}
}
Reversing a Linked List
To reverse a linked list, we need 3 pointers - previous, current and next. Initially, current pointer points to the head node and in each iteration, the next node of current node points to the previous node and we shift all the pointers one step ahead, meaning the previous pointer now points to the current node and current pointer points to the next node.
public Node reverse(){
Node previous = null;
Node current = head;
Node next;
while (current != null){
next = current.getNextNode();
current.setNextNode(previous);
previous = current;
current = next;
}
return previous;
}
Check Loops in Linked List
To check for any existing loop in a linked list, we need to traverse every node of the linked list and put the node info in a Map where the key of the Map will be the Node and value can be the count of node present in the linked list. Once, the count is greater than 1 means duplicate node and hence a loop exists in the list.
Below is the Java implementation for the same.
public boolean checkLoop(){
boolean loopExists = false;
Map<Node, Integer> map = new HashMap<>();
Node tempNode = head;
while (tempNode != null){
if(map.get(tempNode) == null){
map.put(tempNode, 1);
}else {
map.put(tempNode, 2);
loopExists = true;
break;
}
tempNode = tempNode.getNextNode();
}
return loopExists;
}
Linked List Runner
Now let us test our linked list implementation with a main class.
public class LinkedListRunner {
public static void main(String [] args){
CustomLinkedList customLinkedList = new CustomLinkedList();
customLinkedList.insert(5);
customLinkedList.insert(10);
customLinkedList.insert(15);
customLinkedList.insert(20);
customLinkedList.display();
customLinkedList.insertAt(2, 100);
System.out.println("********");
customLinkedList.display();
System.out.println("********");
customLinkedList.deleteNodeAt(2);
customLinkedList.display();
System.out.println("********");
customLinkedList.insertHead(50);
customLinkedList.display();
}
}
Conclusion
In this article, discussed about LinkedList implementation in Java and perform several operations such as insert a node at the end, insert a node at a given index, delete a node, insert the head node and traversal of a linked list.
