Double Linked List Using Pointers in C++

A double linked list is a linear data structure similar to a single linked list, but each node has two pointers: one that points to the previous node and another that points to the next node. This allows traversal in both forward and backward directions.

Key Characteristics of Double Linked Lists:

Node Structure:
- Each node in a double linked list contains three fields: data, a pointer to the previous node (prev), and a pointer to the next node (next).
- The prev pointer of the first node and the next pointer of the last node point to nullptr, indicating the beginning and end of the list, respectively.
Traversal:
- Traversing a double linked list can be done both forward and backward, starting from the head or the tail of the list.
- This enables efficient operations such as inserting and deleting nodes at both ends and searching for elements in either direction.
Insertion:
- Adding a node at the head involves creating a new node, updating pointers to link it with the current head and setting it as the new head.
- Adding a node at the tail is similar, but pointers are updated to link the new node with the current tail, and the new node becomes the new tail.
Deletion:
- Deleting a node involves adjusting pointers to bypass the node to be deleted and deallocating its memory to prevent memory leaks.
- Deleting a node can occur at the head, tail, or any position within the list.

Example C++ Program:

Here’s a C++ program implementing a double linked list with functions to add a node at the head, add a node at the tail, insert a node at a specified position, and delete a node at a specified position:

#include <iostream>

// Define a Node structure
struct Node {
    int data;
    Node* prev;
    Node* next;
};

// Function to add a node at the head of the list
void addAtHead(Node*& head, int value) {
    Node* newNode = new Node;
    newNode->data = value;
    newNode->prev = nullptr;
    newNode->next = head;
    if (head != nullptr)
        head->prev = newNode;
    head = newNode;
}

// Function to add a node at the tail of the list
void addAtTail(Node*& head, int value) {
    Node* newNode = new Node;
    newNode->data = value;
    newNode->next = nullptr;
    if (head == nullptr) {
        newNode->prev = nullptr;
        head = newNode;
        return;
    }
    Node* temp = head;
    while (temp->next != nullptr) {
        temp = temp->next;
    }
    temp->next = newNode;
    newNode->prev = temp;
}

// Function to insert a node at a specified position in the list
void insert(Node*& head, int value, int position) {
    if (position < 0)
        return;
    if (position == 0) {
        addAtHead(head, value);
        return;
    }
    Node* newNode = new Node;
    newNode->data = value;
    Node* temp = head;
    for (int i = 0; i < position - 1 && temp != nullptr; ++i) {
        temp = temp->next;
    }
    if (temp == nullptr)
        return;
    newNode->next = temp->next;
    if (temp->next != nullptr)
        temp->next->prev = newNode;
    temp->next = newNode;
    newNode->prev = temp;
}

// Function to delete a node at a specified position in the list
void deleteNode(Node*& head, int position) {
    if (head == nullptr || position < 0)
        return;
    if (position == 0) {
        Node* temp = head;
        head = head->next;
        if (head != nullptr)
            head->prev = nullptr;
        delete temp;
        return;
    }
    Node* temp = head;
    for (int i = 0; i < position && temp != nullptr; ++i) {
        temp = temp->next;
    }
    if (temp == nullptr)
        return;
    if (temp->next != nullptr)
        temp->next->prev = temp->prev;
    temp->prev->next = temp->next;
    delete temp;
}

// Function to print the elements of the list
void printList(Node* head) {
    while (head != nullptr) {
        std::cout << head->data << " ";
        head = head->next;
    }
    std::cout << std::endl;
}

int main() {
    Node* head = nullptr;

    // Add nodes at the head of the list
    addAtHead(head, 3);
    addAtHead(head, 2);
    addAtHead(head, 1);

    std::cout << "List after adding nodes at the head: ";
    printList(head);

    // Add nodes at the tail of the list
    addAtTail(head, 4);
    addAtTail(head, 5);

    std::cout << "List after adding nodes at the tail: ";
    printList(head);

    // Insert a node at position 2
    insert(head, 10, 2);
    std::cout << "List after inserting a node at position 2: ";
    printList(head);

    // Delete a node at position 3
    deleteNode(head, 3);
    std::cout << "List after deleting a node at position 3: ";
    printList(head);

    return 0;
}

Line-by-Line Explanation:

#include <iostream>: This line includes the necessary header file for input/output operations.
struct Node { ... };: This defines a structure named Node representing a node in the double linked list. It contains three fields: data to store the value of the node, prev to point to the previous node, and next to point to the next node.
void addAtHead(Node*& head, int value) { ... }: This function adds a node at the head of the list. It creates a new node with the specified value, updates pointers to link it with the current head, and sets it as the new head.
void addAtTail(Node*& head, int value) { ... }: This function adds a node at the tail of the list. It creates a new node with the specified value, traverses the list to find the current tail, updates pointers to link the new node with the tail, and sets it as the new tail.
void insert(Node*& head, int value, int position) { ... }: This function inserts a node with the specified value at the given position in the list. It handles insertion at the head separately and then traverses the list to find the node at the specified position, updating pointers to insert the new node.
void deleteNode(Node*& head, int position) { ... }: This function deletes the node at the given position in the list. It handles deletion at the head separately and then traverses the list to find the node at the specified position, updating pointers to bypass the node to be deleted and deallocating its memory.
void printList(Node* head) { ... }: This function prints the elements of the list by traversing it from the head to the end, printing the data of each node.
int main() { ... }: This is the main function where the program execution begins. It initializes the head pointer to nullptr and demonstrates the usage of the functions to manipulate the double linked list.

This program provides a comprehensive example of implementing a double linked list in C++, including functions to add nodes at the head and tail, insert nodes at a specified position, delete nodes at a specified position, and print the elements of the list. Each function is accompanied by comments explaining its purpose and implementation.