Singly Linked List in Java
Deep Dive into Singly linked list with Java
Singly linked list in java is a linear data structure in which each element, called a node, contains data and a reference to the next node in the sequence. Unlike arrays, linked lists do not require a fixed size and allow efficient insertion and deletion, especially at the beginning of the list.
In Java, singly linked lists are commonly used when dynamic memory allocation and frequent modifications are needed.
This article explores the structure and operations of singly linked lists in Java, including algorithms, executable code, and time space complexity for each operation.
What is a Singly Linked List in Java?
A singly linked list is a fundamental linear data structure in Java, consisting of nodes where each node contains data and a reference to the next node in the sequence.
This structure allows for efficient insertion and deletion operations, especially when compared to arrays, as it doesn’t require shifting elements.
Structure of a Singly Linked List
Each node in a singly linked list comprises two components:
- Data: The value stored in the node.
- Next: A reference to the subsequent node in the list.
The list begins with a head pointer that references the first node. The last node’s next pointer is set to null, indicating the end of the list.
Structure of singly linked list in Java
class LinkedList {
Node head; // head
// Linked list Node
class Node {
int data;
Node next;
// constructor to initialize
Node(int d) {
data = d;
next = null;
}
}
} 
Insertion Operations in Singly Linked List
1. Insert at the Beginning
Algorithm:
- Create a new node.
- Set its next pointer to the current head.
- Update the head to the new node.
Space Complexity: O(1)
public void insertAtBeginning(int data) {
Node newNode = new Node(data);
newNode.next = head;
head = newNode;
}
2. Insert at the End
Algorithm:
- Create a new node.
- If the list is empty, set head to the new node.
- Otherwise, traverse to the last node.
- Set the last node’s next pointer to the new node.
Space Complexity: O(1)
public void insertAtEnd(int data) {
Node newNode = new Node(data);
if (head == null) {
head = newNode;
return;
}
Node current = head;
while (current.next != null) {
current = current.next;
}
current.next = newNode;
}
3. Insert at a Specific Position
Algorithm:
- Create a new node.
- Traverse to the node before the desired position.
- Set the new node’s next pointer to the current node’s next.
- Set the current node’s next to the new node.
Code:
Space Complexity: O(1)
public void insertAtPosition(int data, int position) {
Node newNode = new Node(data);
if (position == 0) {
newNode.next = head;
head = newNode;
return;
}
Node current = head;
for (int i = 0; i < position - 1 && current != null; i++) {
current = current.next;
}
if (current == null) {
throw new IndexOutOfBoundsException("Position out of bounds");
}
newNode.next = current.next;
current.next = newNode;
}
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Deletion Operations in Singly Linked List
1. Delete from the Beginning
Algorithm:
- Check if the list is empty.
- Set head to head.next.
Space Complexity: O(1)
public void deleteFromBeginning() {
if (head == null) {
return;
}
head = head.next;
}
2. Delete from the End
Algorithm:
- Check if the list is empty or has only one node.
- Traverse to the second-last node.
- Set its next pointer to null.
Time Complexity: O(n)
Space Complexity: O(1)
Space Complexity: O(1)
public void deleteFromEnd() {
if (head == null || head.next == null) {
head = null;
return;
}
Node current = head;
while (current.next.next != null) {
current = current.next;
}
current.next = null;
}
3. Delete from a Specific Position
Algorithm:
Check if the list is empty.
If position is 0, set head to head.next.
Traverse to the node before the desired position.
Set its next pointer to the next of next node
Space Complexity: O(1)
public void deleteAtPosition(int position) {
if (head == null) {
return;
}
if (position == 0) {
head = head.next;
return;
}
Node current = head;
for (int i = 0; i < position - 1 && current != null; i++) {
current = current.next;
}
if (current == null || current.next == null) {
throw new IndexOutOfBoundsException("Position out of bounds");
}
current.next = current.next.next;
}
Traversal Operation in Singly Linked List
Traversal in Singly Linked List
- Traversal refers to the process of visiting each node in a singly linked list exactly once, usually from the head node to the last node.
- It is a fundamental operation used to access, display, or process the elements stored in the list.
When is Traversal Used?
- Printing all elements of the list
- Searching for a specific value
- Performing operations like counting nodes, summing values, etc.
- Validating the structure or integrity of the list
1. Iterative Traversal
Algorithm:
- Start with the head node.
- While the current node is not null:
- Process (e.g., print or count) the current node’s data.
- Move to the next node.
Space Complexity: O(1)
public void traverseIterative() {
Node current = head;
while (current != null) {
System.out.print(current.data + " ");
current = current.next;
}
System.out.println();
}
2. Recursive Traversal
Algorithm:
- If the current node is null, return.
- Process the current node’s data.
- Recursively call the method with the next node.
Space Complexity: O(n) due to recursive call stack
public void traverseRecursive(Node current) {
if (current == null) return;
System.out.print(current.data + " ");
traverseRecursive(current.next);
}
3. Reverse Recursive Traversal
Algorithm:
If the current node is null, return.
Recursively call the function with the next node.
After recursion returns, process the current node’s data.
Space Complexity: O(n)
public void traverseReverseRecursive(Node current) {
if (current == null) return;
traverseReverseRecursive(current.next);
System.out.print(current.data + " ");
}
WHY? SINGLY LINKED LIST !!!
Conclusion
Singly linked lists are a fundamental data structure offering efficient insertion and deletion operations, especially at the beginning of the list.
While they lack direct access to elements by index, their dynamic nature makes them suitable for scenarios where frequent insertions and deletions are required.
Understanding their operations and complexities is crucial for effective algorithm design and problem-solving in Java.
FAQ's related to Singly Linked List in Java
Answer:
A singly linked list is a dynamic data structure made up of nodes, where each node contains data and a pointer to the next node in the list. Unlike arrays, linked lists do not require predefined size and allow efficient insertions and deletions without shifting elements.
However, accessing elements by index is slower in a linked list compared to an array.
Answer:
- Dynamic size (no need to declare size in advance)
- Efficient insertions and deletions at the beginning or middle
- No memory wastage due to over-allocation
- Simple implementation of stacks and queues
Answer:
Singly linked lists are not ideal when:
- You need frequent random access by index (as it takes O(n) time)
- Memory usage is critical (since each node stores a pointer)
- Backward traversal is required (singly linked lists only support forward traversal)
Answer:
Yes, a singly linked list can be reversed either iteratively or recursively by manipulating the next pointers of each node. The most common method is an iterative approach using three pointers: previous, current, and next. Reversing a list is a common interview question and helps demonstrate pointer manipulation and understanding of the list structure.
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Login/Signup to comment