Linked lists data structures consist of a sequence of nodes that store data and point to the next node. Linked lists have multiple variations and two of the important variations are singly linked lists and doubly linked lists. The first node is called the head and the last node of the linked list is called the tail.
Singly Linked List
Singly linked list is a linear data structure that stores the data in the form of nodes. Nodes consist of data and the next pointer which points (stores address) to the next node.
The first node of the singly linked list is called head and the last node is called tail which points to null. Singly-linked lists are usually used to implement other data structures like stack, queue, dynamic arrays, etc.
These are efficient for operations like insertion and deletion at the beginning and end of the list.
Example
Singly Linked List in C++:
#include <iostream>
class Node {
public:
int data;
Node* next;
Node(int data) : data(data), next(nullptr) {}
};
class LinkedList {
public:
Node* head;
LinkedList() : head(nullptr) {}
// Insert a new node at the end of the list
void append(int data) {
Node* newNode = new Node(data);
if (head == nullptr) {
head = newNode;
} else {
Node* current = head;
while (current->next != nullptr) {
current = current->next;
}
current->next = newNode;
}
}
// Display the elements of the list
void display() {
Node* current = head;
while (current != nullptr) {
std::cout << current->data << " ";
current = current->next;
}
std::cout << std::endl;
}
};
int main() {
LinkedList myList;
myList.append(1);
myList.append(2);
myList.append(3);
myList.display();
return 0;
}
Singly Linked List in Java:
class Node {
int data;
Node next;
Node(int data) {
this.data = data;
this.next = null;
}
}
class LinkedList {
Node head;
LinkedList() {
this.head = null;
}
// Insert a new node at the end of the list
void append(int data) {
Node newNode = new Node(data);
if (head == null) {
head = newNode;
} else {
Node current = head;
while (current.next != null) {
current = current.next;
}
current.next = newNode;
}
}
// Display the elements of the list
void display() {
Node current = head;
while (current != null) {
System.out.print(current.data + " ");
current = current.next;
}
System.out.println();
}
public static void main(String[] args) {
LinkedList myList = new LinkedList();
myList.append(1);
myList.append(2);
myList.append(3);
myList.display();
}
}
Doubly Linked List
Doubly Linked List is an advancement in the singly linked list. It not only stores the data and the next pointer but also the previous pointer. It allows traversal of the list in both directions. It has a wide range of applications such as text editors, undo/redo, browsers, etc.
This allows for more efficient traversal in both directions and is useful for certain algorithms and applications.
Example
Doubly Linked List in C++:
#include <iostream>
class Node {
public:
int data;
Node* next;
Node* prev;
Node(int data) : data(data), next(nullptr), prev(nullptr) {}
};
class DoublyLinkedList {
public:
Node* head;
DoublyLinkedList() : head(nullptr) {}
// Insert a new node at the end of the list
void append(int data) {
Node* newNode = new Node(data);
if (head == nullptr) {
head = newNode;
} else {
Node* current = head;
while (current->next != nullptr) {
current = current->next;
}
current->next = newNode;
newNode->prev = current;
}
}
// Display the elements of the list in both directions
void display() {
Node* current = head;
while (current != nullptr) {
std::cout << current->data << " ";
current = current->next;
}
std::cout << std::endl;
}
};
int main() {
DoublyLinkedList myList;
myList.append(1);
myList.append(2);
myList.append(3);
myList.display();
return 0;
}
Doubly Linked List in Java:
class Node {
int data;
Node next;
Node prev;
Node(int data) {
this.data = data;
this.next = null;
this.prev = null;
}
}
class DoublyLinkedList {
Node head;
DoublyLinkedList() {
this.head = null;
}
// Insert a new node at the end of the list
void append(int data) {
Node newNode = new Node(data);
if (head == null) {
head = newNode;
} else {
Node current = head;
while (current.next != null) {
current = current.next;
}
current.next = newNode;
newNode.prev = current;
}
}
// Display the elements of the list in both directions
void display() {
Node current = head;
while (current != null) {
System.out.print(current.data + " ");
current = current.next;
}
System.out.println();
}
public static void main(String[] args) {
DoublyLinkedList myList = new DoublyLinkedList();
myList.append(1);
myList.append(2);
myList.append(3);
myList.display();
}
}
Difference between Singly and Doubly Linked List
Let us explore the differences between the Singly Linked List and the Doubly Linked List.
| Feature | Singly Linked List | Doubly Linked List |
|---|---|---|
| Type of Data Structure | It is a Linear Data Structure. | It is also a Linear Data Structure. |
| Node Structure | Singly Linked Lists contains data and a “Next” pointer | Double Linked List contains data, a “Next” pointer, and a “Previous” pointer. |
| Traversal | It can traverse in only a forward direction. | It is Bidirectional as we can traverse in both forward and backward directions. |
| Insertion and Deletion at Beginning | As we have the Head pointer insertion or deletion is efficient and can be performed in $O(1)$ time complexity. | Efficient, can be performed in $O(1)$ time complexity. |
| Insertion and Deletion at End | Insertion/Deletion at the end requires traversing the entire list and thus, is less efficient. The time complexity for operations at the end of the list is $O(N)$. | Due to the presence of Tail Pointer we can insert or delete in $O(1)$ at the end of the list. |
| Insertion at Arbitrary Position | Requires more operations and list traversal as singly linked lists are unidirectional. The worst-case time complexity is $O(N)$. | Doubly linked Lists are more efficient as compared to singly linked lists as we can traverse in both directions. |
| Memory Usage | Memory usage is less as compared to a doubly linked list. | Requires slightly more memory as it stores both “Next” and “Previous” pointers. |
| Implementation Complexity | It is simple to implement. | It is slightly more complex to implement due to bidirectional links. |
| Advantages | Simpler and uses less memory than a doubly linked list, Faster insertion and deletion of nodes at the beginning or end of the list | Can be traversed in both directions, Insertion and deletion of nodes anywhere in the list is simple, Can be reversed |
| Disadvantages | Can only be traversed in one direction, Insertion and deletion of nodes in the middle of the list is more complex, Cannot be reversed | More complex and uses more memory than a singly linked list, Slower insertion and deletion of nodes at the beginning or end of the list |
| Applications | To implement stacks, queues, and dynamic arrays. | Used to implement heaps, binary trees, undo/redo, browser navigation, etc. |
FAQs
Q. What is the difference between a singly linked list and a doubly linked list?
A. A singly linked list is a linear data structure in which each node contains data and a pointer to the next node in the list. A doubly linked list is a linear data structure in which each node contains data and pointers to the previous and next nodes in the list.
Q. Which one is better, a singly linked list or a doubly linked list?
A. There is no one-size-fits-all answer to this question. The best data structure to use depends on the specific application. Singly-linked lists are simpler and use less memory, but they can only be traversed in one direction. Doubly linked lists are more complex and use more memory, but they can be traversed in both directions.
Conclusion
- Both singly and doubly linked lists are linear data structures that can be used to implement more complex data structures.
- Singly linked lists can be used to implement stacks, queues, etc. whereas doubly linked lists are used to implement heaps, trees, etc.
- Singly-linked lists consist of data and a next pointer. These are unidirectionals.
- Doubly Linked lists consists of data, next, and previous pointers. These are bidirectionals.
- Both the data structures hold their uses and differences, it depends on the condition and requirements.
