DLL
#include <iostream>
using namespace std;
struct Node {
int data;
Node* prev;
Node* next;
};
class DoublyLL {
public:
Node* head;
Node* rear;
int count;
DoublyLL() {
head = rear = NULL;
count = 0;
}
int insert(int value) {
// Step 1: allocate new node
Node* newNode = new Node();
// Locate insertion point
Node* pred = NULL;
Node* succ = head;
while (succ != NULL && succ->data < value) {
pred = succ;
succ = succ->next;
}
// Fill node
newNode->data = value;
newNode->prev = pred;
newNode->next = succ;
// Check for duplicate
if (succ != NULL && succ->data == value) {
delete newNode;
return 0; // duplicate key
}
// Insert before first node or into empty list
if (pred == NULL) {
newNode->prev = NULL;
newNode->next = head;
head = newNode;
} else {
pred->next = newNode;
}
// Insert in middle or end
if (succ != NULL) {
succ->prev = newNode;
} else {
// Insert at end of list, set rear
rear = newNode;
}
// Update rear when first node
if (rear == NULL) rear = newNode;
count++;
return 1; // success
}
void deleteNode(int value) {
if (head == NULL) {
cout << "List is empty.\n";
return;
}
// locate the node to be deleted
Node* temp = head;
while (temp && temp->data != value) {
temp = temp->next;
}
// if target node not found
if (!temp) {
cout << "Value not found.\n";
return;
}
// Fix previous link or update head
if (temp->prev) // if it is middle node or end node
temp->prev->next = temp->next;
else
head = temp->next;
// Fix next link or update rear
if (temp->next) temp->next->prev = temp->prev;
else rear = temp->prev;
delete temp;
count--;
cout << value << " deleted.\n";
}
void displayForward() {
if (!head) { cout << "List is empty.\n"; return; }
Node* temp = head;
cout << "List (Ascending): ";
while (temp) {
cout << temp->data << " <-> ";
temp = temp->next;
}
cout << "NULL\n";
}
void displayBackward() {
if (!rear) { cout << "List is empty.\n"; return; }
Node* temp = rear;
cout << "List (Reverse): ";
while (temp) {
cout << temp->data << " <-> ";
temp = temp->prev;
}
cout << "NULL\n";
}
void showCount() {
cout << "Total nodes: " << count << endl;
}
};
int main() {
DoublyLL dll;
int choice, value, result;
do {
cout << "\n--- Doubly Linked List Menu ---\n";
cout << "1. Insert (maintains ascending order)\n";
cout << "2. Delete a Node\n";
cout << "3. Display Forward\n";
cout << "4. Display Backward\n";
cout << "5. Show Count\n";
cout << "6. Exit\n";
cout << "Enter your choice: ";
cin >> choice;
switch (choice) {
case 1:
cout << "Enter value to insert: ";
cin >> value;
result = dll.insert(value);
if (result == 0) cout << "Duplicate key. Insert failed.\n";
else cout << value << " inserted in DLL.\n";
break;
case 2:
cout << "Enter value to delete: ";
cin >> value;
dll.deleteNode(value);
break;
case 3:
dll.displayForward();
break;
case 4:
dll.displayBackward();
break;
case 5:
dll.showCount();
break;
case 6:
cout << "Exiting...\n";
break;
default:
cout << "Invalid choice.\n";
}
} while (choice != 6);
return 0;
}
