What is a Doubly Linked List?
A doubly linked list is a data structure that consists of a sequence of elements, where each element contains both data and two pointers. Unlike singly linked list, where each node points only to the next node, a doubly linked list node has pointers to both the next and the previous nodes in the sequence. This bidirectional connectivity allows for more efficient traversal in both directions.
Structure of Doubly Linked List
A Doubly linked lists consists of connected nodes. Each node contains three things:
- Data: Information that linked list contains.
- Previous Node Pointer: The pointer to the previous node.
- Next Node Pointer: The pointer to the next node.
Implementation:
1. Using Structure
#include <iostream>
struct Node {
int data;
Node* next;
Node* prev;
Node(int val) : data(val), next(nullptr), prev(nullptr) {}
};
class DoublyLinkedList {
private:
Node* head;
Node* tail;
public:
DoublyLinkedList() : head(nullptr), tail(nullptr) {}
void insertEnd(int val) {
Node* newNode = new Node(val);
if (!head) {
head = tail = newNode;
} else {
tail->next = newNode;
newNode->prev = tail;
tail = newNode;
}
}
void printForward() {
Node* current = head;
while (current) {
std::cout << current->data << " ";
current = current->next;
}
std::cout << std::endl;
}
void printBackward() {
Node* current = tail;
while (current) {
std::cout << current->data << " ";
current = current->prev;
}
std::cout << std::endl;
}
};
int main() {
DoublyLinkedList myList;
myList.insertEnd(1);
myList.insertEnd(2);
myList.insertEnd(3);
std::cout << "Forward: ";
myList.printForward();
std::cout << "Backward: ";
myList.printBackward();
return 0;
}
2. Using Classes
#include <iostream>
class Node {
public:
int data;
Node* next;
Node* prev;
Node(int val) : data(val), next(nullptr), prev(nullptr) {}
};
class DoublyLinkedList {
private:
Node* head;
Node* tail;
public:
DoublyLinkedList() : head(nullptr), tail(nullptr) {}
void insertEnd(int val) {
Node* newNode = new Node(val);
if (!head) {
head = tail = newNode;
} else {
tail->next = newNode;
newNode->prev = tail;
tail = newNode;
}
}
void printForward() {
Node* current = head;
while (current) {
std::cout << current->data << " ";
current = current->next;
}
std::cout << std::endl;
}
void printBackward() {
Node* current = tail;
while (current) {
std::cout << current->data << " ";
current = current->prev;
}
std::cout << std::endl;
}
};
int main() {
DoublyLinkedList myList;
myList.insertEnd(1);
myList.insertEnd(2);
myList.insertEnd(3);
std::cout << "Forward: ";
myList.printForward();
std::cout << "Backward: ";
myList.printBackward();
return 0;
}
3. Using Generic Templates
#include <iostream>
template <typename T>
struct Node {
T data;
Node* next;
Node* prev;
Node(const T& val) : data(val), next(nullptr), prev(nullptr) {}
};
template <typename T>
class DoublyLinkedList {
private:
Node<T>* head;
Node<T>* tail;
public:
DoublyLinkedList() : head(nullptr), tail(nullptr) {}
void insertEnd(const T& val) {
Node<T>* newNode = new Node<T>(val);
if (!head) {
head = tail = newNode;
} else {
tail->next = newNode;
newNode->prev = tail;
tail = newNode;
}
}
void printForward() {
Node<T>* current = head;
while (current) {
std::cout << current->data << " ";
current = current->next;
}
std::cout << std::endl;
}
void printBackward() {
Node<T>* current = tail;
while (current) {
std::cout << current->data << " ";
current = current->prev;
}
std::cout << std::endl;
}
};
int main() {
DoublyLinkedList<int> intList;
intList.insertEnd(1);
intList.insertEnd(2);
intList.insertEnd(3);
std::cout << "Forward: ";
intList.printForward();
std::cout << "Backward: ";
intList.printBackward();
DoublyLinkedList<std::string> strList;
strList.insertEnd("A");
strList.insertEnd("B");
strList.insertEnd("C");
std::cout << "Forward: ";
strList.printForward();
std::cout << "Backward: ";
strList.printBackward();
return 0;
}
4. Using std::list (C++ Standard Template Library)
#include <iostream>
#include <list>
int main() {
std::list<int> myList;
myList.push_back(1);
myList.push_back(2);
myList.push_back(3);
std::cout << "Forward: ";
for (const auto& element : myList) {
std::cout << element << " ";
}
std::cout << std::endl;
std::cout << "Backward: ";
for (auto iter = myList.rbegin(); iter != myList.rend(); ++iter) {
std::cout << *iter << " ";
}
std::cout << std::endl;
return 0;
}
Operations on Doubly Linked List:
Insertion:
- Insert at the Beginning:
O(1)- Insert a new node at the beginning of the doubly linked list. - Insert at the End:
O(1)- Insert a new node at the end of the doubly linked list. - Insert at a Specific Position:
O(n)- Insert a new node at a specified position in the list.
Deletion:
- Delete at the Beginning:
O(1)- Delete the first node of the doubly linked list. - Delete at the End:
O(1)- Delete the last node of the doubly linked list. - Delete at a Specific Position:
O(n)- Delete a node at a specified position in the list.
Traversal:
- Forward Traversal:
O(n)- Traverse the doubly linked list from the beginning to the end. - Reverse Traversal:
O(n)- Traverse the doubly linked list from the end to the beginning.
Advantages of Doubly Linked Lists over Singly Linked Lists
Bidirectional Traversal:
- Doubly Linked List: Nodes in a doubly linked list have both next and previous pointers. This allows for efficient bidirectional traversal, enabling easy navigation in both forward and backward directions.
- Singly Linked List: Singly linked lists only have next pointers, limiting traversal to one direction. To traverse a single linked list backward, one would need to start from the head and iterate until the desired node, which can be less efficient.
Insertions and Deletions:
- Doubly Linked List: Insertions and deletions in the middle of a doubly linked list are more efficient. Given a node, it's easier to update the adjacent nodes' pointers during insertion or deletion
- Singly Linked List: While insertions and deletions at the beginning are efficient, operations in the middle involve traversing from the head, which can be less efficient.
Memory Utilization:
- Doubly Linked List: Each node in a doubly linked list requires extra space for the previous pointer. This additional memroy usage provides increases flexibility in terms of traversal and operations.
- Singly Linked List: Nodes in a singly linked list only store the next pointer, leading to lower memory overhead. This might be advantageous in memory-constrained environments.
Reversing the List:
- Doubly Linked List: Reversing a doubly linked list is a straightforward and can be done efficiently, as each node has a pointer to its predecessor.
- Singly Linked List: Reversing a singly linked list involves additional complexity, often requiring extra space or modifying the list in place.
Disadvantages of Doubly Linked Lists:
Increased Memory Usage:
- Doubly Linked List: It requires more memory per node due to the additional space needed for the previous pointer. In situations where memory is a critical resource, this could be disadvantage.
Complexity:
- The Implementation and maintenance of doubly linked lists can be more complex compared to singly linked lists. This increased complexity might lead to more challenging debugging and maintenance.