Doubly Linked List
#include <bits/stdc++.h> // Includes all standard C++ librariesusing namespace std;
// Definition of a Node in Doubly Linked Listclass Node {public: int data; // Data part of node Node* next; // Pointer to next node Node* prev; // Pointer to previous node
// Constructor to initialize node with data Node(int data) { this->data = data; this->next = NULL; // Next initially points to NULL this->prev = NULL; // Prev initially points to NULL }};
// Function to print list from head to tailvoid printHead(Node* head) { if(head == NULL) { // Check for empty list cout << "List is Empty!" << endl; return; }
cout << "Doubly List by Head : "; while(head != NULL) { // Traverse until end cout << head->data << " "; // Print data head = head->next; // Move to next node } cout << endl;}
// Function to print list from tail to headvoid printTail(Node* tail) { if(tail == NULL) { // Check for empty list cout << "List is Empty!" << endl; return; }
cout << "Doubly List by Tail : "; while(tail != NULL) { // Traverse in reverse cout << tail->data << " "; // Print data tail = tail->prev; // Move to previous node } cout << endl;}
// Insert a new node at the beginningvoid insertAtHead(Node* &head, int data) { Node *temp = new Node(data); // Create new node temp->next = head; // New node points to old head if(head != NULL) head->prev = temp; // Old head points back to new node head = temp; // Update head pointer}
// Insert a new node at the endvoid insertAtTail(Node* &tail, int data) { Node *temp = new Node(data); // Create new node tail->next = temp; // Old tail points to new node temp->prev = tail; // New node points back to old tail tail = temp; // Update tail pointer}
// Insert node at given position (1-based index)void insertAtMiddle(Node* &head, Node* &tail, int data, int pos) { if(pos == 1) { // If position is 1, insert at head insertAtHead(head, data); return; }
Node *temp = head;
// Move to (pos - 1)th node while(temp != NULL && pos > 2) { temp = temp->next; pos--; }
if(temp == NULL || pos <= 0) { // Invalid position cout << "Invalid Position!" << endl; return; }
Node *insertNode = new Node(data); // Create node to insert insertNode->next = temp->next; // New node points to next of current insertNode->prev = temp; // New node's prev is current temp->next = insertNode; // Current node's next is new node
if(insertNode->next == NULL) { // If inserted at end, update tail tail = insertNode; } else { temp->next->prev = insertNode; // Update next node's prev pointer }}
// Delete node at given position (1-based index)void deletePosition(Node* &head, Node* &tail, int pos) { Node *temp = head;
if(pos == 1) { // Delete head node head = head->next; // Move head forward delete temp; // Delete old head
if(head != NULL) { head->prev = NULL; // New head's prev becomes NULL } else { tail = NULL; // List becomes empty } return; }
// Traverse to (pos - 1)th node while(temp != NULL && pos > 2) { temp = temp->next; pos--; }
// Invalid position if(temp == NULL || temp->next == NULL || pos <= 0) { cout << "Invalid Position!" << endl; return; }
Node* target = temp->next; // Node to delete temp->next = target->next; // Skip over the target
if(target == tail) { // If deleting last node tail = tail->prev; // Move tail back } else { target->next->prev = temp; // Update next node's prev pointer }
delete target; // Free memory}
// Delete node with a given value (first occurrence)void deleteValue(Node* &head, Node* &tail, int val) { Node* temp = head;
// Check if head needs to be deleted if(head->data == val) { head = head->next; // Move head forward delete temp; // Delete old head
if(head != NULL) { head->prev = NULL; // Update new head } else { tail = NULL; // List becomes empty } return; }
// Traverse to find the value while(temp != NULL) { if(temp->data == val) { val = INT_MIN; // Mark as found break; } temp = temp->next; }
if(temp == NULL || val != INT_MIN) { // Value not found cout << "Value Not Found!" << endl; return; }
// Re-link neighbors to skip over target temp->prev->next = temp->next;
if(temp == tail) { tail = tail->prev; // Update tail if needed } else { temp->next->prev = temp->prev; // Update next node's prev }
delete temp; // Free memory}
// Driver codeint main() { Node *head = new Node(1); // Create first node with data 1 Node *tail = head; // Head and tail both point to it
// Insert nodes with values 2, 4, 8, 16, 32 at the tail for(int i = 1; i <= 5; i++) { insertAtTail(tail, pow(2, i)); // pow(2, i) = 2, 4, 8, 16, 32 }
printHead(head); // Print list from head printTail(tail); // Print list from tail
// Example operations: // insertAtMiddle(head, tail, 99, 6); // Insert 99 at 6th position // deletePosition(head, tail, 8); // Try deleting 8th node (invalid here)
deleteValue(head, tail, 64); // Try deleting value 64 (not in list)
printHead(head); // Final print from head printTail(tail); // Final print from tail
return 0;}- Implements a Doubly Linked List
- Supports:
- Insertion at head, tail, or middle
- Deletion by position or value
- Printing list forward (from head) and backward (from tail)
Doubly List by Head : 1 2 4 8 16 32Doubly List by Tail : 32 16 8 4 2 1Value Not Found!Doubly List by Head : 1 2 4 8 16 32Doubly List by Tail : 32 16 8 4 2 1| Function | Description |
|---|---|
insertAtHead() | Insert node at the beginning |
insertAtTail() | Insert node at the end |
insertAtMiddle() | Insert node at specific position |
deletePosition() | Delete node at given position |
deleteValue() | Delete node with given value |
printHead() | Print list forward (from head) |
printTail() | Print list backward (from tail) |
Node *tail = NULL;Step 1: insertion(tail, pow(2,4), 2) → insert 16
Since the list is empty, 16 becomes the only node and points to itself.
+-----+------+| 16 | o---++-----+ | ^ | +-------+ (tail)Step 2: insertion(tail, pow(2,3), 16) → insert 8 after 16
+-----+ +-----+| 16 | --> | 8 |+-----+ +-----+ ^ | | v +-----------+ (tail)Step 3: insertion(tail, pow(2,5), 8) → insert 32 after 8
+-----+ +-----+ +------+| 16 | --> | 8 | --> | 32 |+-----+ +-----+ +------+ ^ | | v +-----------------------+ (tail)Step 4: insertion(tail, pow(2,2), 16) → insert 4 after 16
+-----+ +-----+ +-----+ +------+| 16 | --> | 4 | --> | 8 | --> | 32 |+-----+ +-----+ +-----+ +------+ ^ | | v +-----------------------------------+ (tail)Step 5: deletion(tail, 64)
Value 64 is not in the list, so:
Element Not Found!Final List:
+-----+ +-----+ +-----+ +------+| 16 | --> | 4 | --> | 8 | --> | 32 |+-----+ +-----+ +-----+ +------+ ^ | | v +-----------------------------------+ (tail)- The tail always points to the last inserted node.
- You can traverse the entire list starting from tail->next (the head).
- The do-while in printList ensures even single-node circular lists are printed.