Doubly Linked List
A doubly linked list is a linear data structure that consists of a sequence of nodes. Each node contains data and two pointers, one pointing to the previous node and another pointing to the next node in the list. This allows for traversal in both directions, forward and backward.A step-by-step explanation and implementation of a doubly linked list in C++ with various operations:
#include <iostream>
struct Node {
int data;
Node* prev;
Node* next;
};
class DoublyLinkedList {
private:
Node* head;
Node* tail;
public:
DoublyLinkedList() {
head = nullptr;
tail = nullptr;
}
// Operations...
};
struct Node {
int data;
Node* prev;
Node* next;
};
class DoublyLinkedList {
private:
Node* head;
Node* tail;
public:
DoublyLinkedList() {
head = nullptr;
tail = nullptr;
}
// Operations...
};
//insert at the beginning position of DoublyLinkedList
void DoublyLinkedList::insertAtBeginning(int value) {
Node* newNode = new Node;
newNode->data = value;
newNode->prev = nullptr;
newNode->next = head;
if (head != nullptr)
head->prev = newNode;
else
tail = newNode;
head = newNode;
}
//insert at the end position of DoublyLinkedList
void DoublyLinkedList::insertAtEnd(int value) {
Node* newNode = new Node;
newNode->data = value;
newNode->next = nullptr;
newNode->prev = tail;
if (tail != nullptr)
tail->next = newNode;
else
head = newNode;
tail = newNode;
}
//insert at the speicifiec position of DoublyLinkedList
void DoublyLinkedList::insertAtPosition(int value, int position) {
if (position < 1) {
std::cout << "Invalid position." << std::endl;
return;
}
if (position == 1) {
insertAtBeginning(value);
return;
}
Node* newNode = new Node;
newNode->data = value;
Node* current = head;
int currentPosition = 1;
while (current != nullptr && currentPosition < position - 1) {
current = current->next;
currentPosition++;
}
if (current == nullptr) {
std::cout << "Invalid position." << std::endl;
return;
}
newNode->prev = current;
newNode->next = current->next;
if (current->next != nullptr)
current->next->prev = newNode;
else
tail = newNode;
current->next = newNode;
}
//delete a node from beginning of the DoublyLinkedList
void DoublyLinkedList::deleteAtBeginning() {
if (head == nullptr) {
std::cout << "The list is empty." << std::endl;
return;
}
Node* temp = head;
head = head->next;
if (head != nullptr)
head->prev = nullptr;
else
tail = nullptr;
delete temp;
}
//delete a node from end of the DoublyLinkedList
void DoublyLinkedList::deleteAtEnd() {
if (tail == nullptr) {
std::cout << "The list is empty." << std::endl;
return;
}
Node* temp = tail;
tail = tail->prev;
if (tail != nullptr)
tail->next = nullptr;
else
head = nullptr;
delete temp;
}
//delete a node from a specifiec position of the DoublyLinkedList
void DoublyLinkedList::deleteAtPosition(int position) {
if (position < 1 || head ==
nullptr) {
std::cout << "Invalid position or the list is empty." << std::endl;
return;
}
if (position == 1) {
deleteAtBeginning();
return;
}
Node* current = head;
int currentPosition = 1;
while (current != nullptr && currentPosition < position) {
current = current->next;
currentPosition++;
}
if (current == nullptr) {
std::cout << "Invalid position." << std::endl;
return;
}
current->prev->next = current->next;
if (current->next != nullptr)
current->next->prev = current->prev;
else
tail = current->prev;
delete current;
}
//display the DoublyLinkedList element forward
void DoublyLinkedList::displayForward() {
if (head == nullptr) {
std::cout << "The list is empty." << std::endl;
return;
}
Node* current = head;
while (current != nullptr) {
std::cout << current->data << " ";
current = current->next;
}
std::cout << std::endl;
}
//display the DoublyLinkedList element backward
void DoublyLinkedList::displayBackward() {
void DoublyLinkedList::displayBackward() {
if (tail == nullptr) {
std::cout << "The list is empty." << std::endl;
return;
}
Node* current = tail;
while (current != nullptr) {
std::cout << current->data << " ";
current = current->prev;
}
std::cout << std::endl;
}
int main() {
DoublyLinkedList list;
list.insertAtBeginning(10);
list.insertAtEnd(20);
list.insertAtEnd(30);
list.insertAtPosition(15, 2);
list.displayForward(); // Output: 10 15 20 30
list.displayBackward(); // Output: 30 20 15 10
list.deleteAtPosition(3);
list.displayForward(); // Output: 10 15 30
list.displayBackward(); // Output: 30 15 10
return 0;
}
We have implemented insertion operations such as insertAtBeginning, insertAtEnd, and insertAtPosition. Deletion operations include deleteAtBeginning, deleteAtEnd, and deleteAtPosition. Display operations displayForward and displayBackward are also implemented to print the list in both directions.
In the main function, we create a DoublyLinkedList object, perform operations on it, and display the list at various stages.
When you run the code, the output will be:
forward: 10 15 20 30
backward: 30 20 15 10
forward: 10 15 30
backward: 30 15 10