Implementation of Doubly Linked List in Java
Introduction:
Linked lists are fundamental data structures that play a crucial role in Data structures. Among the various linked lists, the singly linked list stands out for its simplicity and efficiency in specific scenarios. In this blog post, we’ll dive into implementing singly linked lists, exploring their structure, advantages, and how to harness their power in your code.
Understanding Linked Lists:
A linked list is a data structure where each element, known as a node, contains a data component and a reference (or link) to the next node in the sequence. The last node in the list points to null, indicating the end of the list. The structure allows for easy traversal in one direction, making it efficient for certain operations.
Implementation in Java:
Let’s walk through a basic Java implementation of a singly linked list. We’ll define a Node class to represent each element and a LinkedList class to manage the Node
Solution Approach
The implementation of the LinkedList the class follows common design patterns used in object-oriented programming for linked list manipulation, relying on the concept of nodes and references that point from one node to the next. The solution includes an inner class, Node, to define the structure of each node in the linked list.
Let’s break down the main components of the implementation:
- Node Class: This is a nested helper class within LinkedList. Each instance of Node represents a node in the linked list containing the elements val (the current node's value) and next (a pointer to the next node in the list).
- Dummy Node: A dummy head node, dummy, initialized to Node(), is used to simplify edge cases when modifying the head of the list. The dummy node does not hold any data and is used to reference the first actual element in the linked list.
- Node Count: The size variable tracks the current number of nodes in the linked list, excluding the dummy node. This is crucial for validating indexes and simplifying the adding processes.
Here is how each method is implemented:
- LinkedList(): Initializes the linked list object with a head node and a node count set to 0.
- get(index): Returns the value of the node at the given index by first ensuring the index is within bounds (0 to size-1 ). It then traverses the list from the node after the dummy node using a simple loop up to the desired index.
- addAtHead(val): Adds a new node at 0 index. It inserts the new node before the head. It references next the link to the head of the list. addAtTail(val): Adds a new node at the end of the list. Index by traversing up to the node at the end. Once there, it inserts the new node by adjusting the next references to link the new node into the list.
- addAtIndex(index, val): Adds a new node at a specific index by traversing up to the node just before the target position. Once there, it inserts the new node by adjusting the next references to link the new node into the list. If the given index is greater than size, the method exits without making any changes.
- deleteAtIndex(index): Removes a node from a specific index by first ensuring the index is valid, then finding the node just before the one that should be deleted, and adjusting its next reference to skip the node to be removed.
Example Walkthrough
Let’s walk through a small example to illustrate the implementation of our LinkedList class.
Initialize: Suppose we call LinkedList() constructor.
The linked list is now initialized. It has a dummy node, and the count (size) is set to 0. Currently, the list looks like this: head -> null. addAtHead(1): We want to add a value 1 at the head of the list.
Since the index is 0, the new node with the value 1 is inserted right after the head node. Now the list looks like this: dummy -> 1 -> null. The count (size) is incremented to 1. addAtTail(3): Now, we add a value 3 at the tail of the list.
The new node with the value 3 is inserted after the node with the value 1. The list now looks like this: dummy -> 1 -> 3 -> null. The count (size) is incremented to 1. addAtIndex(1, 2): Next, we insert a value 2 at index 1.
The addAtIndex(1, 2) method will traverse the list and insert the new node with the value 2 between the nodes 1 and 3. The list is now: dummy -> 1 -> 2 -> 3 -> null. The count (size) is updated to 3. get(1): To get the value at index 1.
We call the get(1) method. This method traverses the list and returns the node's value at index 1. This will return 2 since the node at index 1 has the value 2. deleteAtIndex(1): Now, let's delete the node at index 1.
Invoking deleteAtIndex(1) method locates the node just before the target node (the node with the value 1) and updates its next reference to the node after the target node (the node with value 3). The node with the value 2 is now removed from the list. The list becomes: dummy -> 1 -> 3 -> null. The count (size) is decremented by 1. This carefully designed implementation accounts for various edge cases and uses the dummy node pattern and node count to enhance the efficiency and readability of the linked list operations.
public class LinkedList {
private Node head;
private int size;
public LinkedList() {
this.head = null;
size = 0;
}
public int get(int index) {
if(index > size || index < 0) return -1;
Node node = head;
for(int i =0 ; i< index; i++) node = node.next;
return node == null ? -1 : node.val;
}
public void addAtHead(int val) {
Node node = new Node(val);
node.next = head;
head = node;
size++;
}
public void addAtTail(int val) {
if (isEmpty()) {
head = new Node(val);
return;
}
Node node = new Node(val);
Node dummy = head;
while (dummy.next != null) dummy = dummy.next;
dummy.next = node;
size++;
}
public void addAtIndex(int index, int val) {
if (index < 0 || index > size) return ;
Node node = new Node(val);
if (index < 0) index = 0;
if(isEmpty()){
head = node;
size++;
return;
}
Node dummy = head;
for(int i = 0; i< index; i++) dummy = dummy.next;
if(size == index){
dummy.next = node;
size++;
return;
}
node.next = dummy.next;
dummy.next = node;
size++;
}
public void deleteAtIndex(int index) {
if(index >= size || index < 0)return;
Node current = head;
Node previous = null;
for(int i = 0; i<index ;i++){
previous = current;
current = current.next;
}
if(previous == null){
head = head.next;
}else {
previous.next = current.next;
}
size--;
}
public boolean isEmpty() {
return head == null;
}
private static class Node {
private int val;
private Node next;
public Node(int val) {
this.val = val;
this.next = null;
}
}
}
Advantages of Linked Lists:
Dynamic Size:
Singly-linked lists can dynamically adjust their size during runtime, making them suitable for scenarios where the number of elements is unknown or may change.
Efficient Insertions and Deletions:
Adding or removing elements from the middle of a singly linked list is more efficient than arrays because there is no need to shift elements. The relevant references can be updated, maintaining constant time complexity.
Memory Utilization:
Singly-linked lists are memory-efficient compared to arrays, as they don’t require contiguous memory allocation. Nodes can be scattered throughout the memory, allowing for better memory utilization.
Easy Implementation:
Implementing singly linked lists is relatively straightforward, making them an excellent choice for learning and understanding fundamental data structures.
Conclusion:
Mastering the implementation of singly linked lists is a valuable skill for any programmer. Their simplicity and efficiency in specific scenarios make them a powerful tool for managing dynamic data. By understanding the structure and advantages of singly linked lists, you can enhance your ability to design and implement efficient algorithms in your code.
Happy Coding
Vishwaraj Sali
sali.vishwaraj@gmail.com
https://www.Vishsali.dev