In this blog post, we will understand the various differences between Singly and doubly linked lists in Java. Before directly going Singly vs Doubly Linked List in Java, let’s understand them individually.
Singly Linked List in Java
A singly linked list in Java is a data structure consisting of a sequence of nodes. Where each node holds a reference (pointer) to an object and a reference to the next node in the list. We traverse the list from one node to another using the reference to the next node. The last node has a reference to null, marking the end of the list. We use singly linked lists to implement dynamic data structures. When we add or remove the elements the size can change dynamically.
Doubly Linked List
A doubly linked list in Java is a data structure consisting of a sequence of nodes. Where each node holds a reference (pointer) to an object and references to both the next and previous node in the list. We traverse the list from one node to another using the reference to the next node, similar to singly linked lists. The first node has a reference to null for the previous node and the last node has a reference to null for the next node. We use doubly linked lists for dynamic data structures that require bidirectional traversal.
Singly vs Doubly Linked List in Java
When comparing the two, the main difference is the number of references each node holds, with the singly linked list holding a reference to only the next node. While the doubly linked list holds references to both the next and previous node. Let’s see the following table to understand the differences between the singly and doubly linked lists in Java:
| SN | Feature | Singly Linked List | Doubly Linked List |
|---|---|---|---|
| 1 | Basic Concept | Each node has a reference to the next node. | Each node has a reference to both the next and previous node. |
| 2 | Memory Usage | Lower memory usage as each node only holds a reference to the next node. | Higher memory usage as each node holds references to both the next and previous node. |
| 3 | Traversal | Can only traverse forward, not backward. | Can traverse forward and backward. |
| 4 | Insertion/Deletion | Efficient for inserting and deleting at the end. | Efficient for inserting and deleting at both ends and anywhere in between. |
| 5 | Memory Allocation | Allocated memory in a single contiguous block. | Allocated memory may not be in a single contiguous block. |
| 6 | Cost of Insertion/Deletion at Beginning | More expensive as all other nodes must be updated. | Less expensive as only the previous and next pointers need to be updated. |
| 7 | Access Time | Slower for accessing elements in the middle. | Faster for access elements in the middle. |
| 8 | Ease of Implementation | Simpler as only a single reference is needed for each node. | Slightly more complex as two references are needed for each node. |
| 9 | Use Cases | Used in cases where only forward traversal is needed or memory usage is a concern. | Used in cases where bidirectional traversal is required or inserting/deleting elements is more frequent than searching. |
If you don’t know, how to create a singly linked list and a doubly linked list in Java then you can visit another post called Create LinkedList in Java where you can find the example code.