Demo - Doubly-linked list

Here is an example implementation of a doubly-linked list in C++:

//  DoublyLinkedListNode.h
//  Created by Kevin Roark

#ifndef DoublyLinkedListNode_h
#define DoublyLinkedListNode_h

// Define a generic node for the doubly linked list
template <typename T>
class DoublyLinkedListNode {
public:
    T value; // Store the value of the node
    DoublyLinkedListNode* prev; // Pointer to the previous node
    DoublyLinkedListNode* next; // Pointer to the next node

    // Constructor to initialize the node with a value
    DoublyLinkedListNode(T value) : value(value), prev(nullptr), next(nullptr) {}
};

#endif /* DoublyLinkedListNode_h */

// DoublyLinkedList.h
// Created by Kevin Roark
#ifndef DoublyLinkedList_h
#define DoublyLinkedList_h

#include "DoublyLinkedListNode.h" // Include the node definition for the doubly linked list
#include <iostream> // Include the standard I/O library for printing
using namespace std;

// Template class for a generic doubly linked list
template <typename T>
class DoublyLinkedList {
private:
    DoublyLinkedListNode<T>* head; // Pointer to the head of the list
    DoublyLinkedListNode<T>* tail; // Pointer to the tail of the list

public:
    // Constructor to initialize an empty list
    DoublyLinkedList() : head(nullptr), tail(nullptr) {}

    // Destructor to clean up the list
    ~DoublyLinkedList() {
        clear(); // Use the clear method to delete all nodes
    }

    // Clear the list by deleting all nodes
    void clear() {
        while (head) {
            DoublyLinkedListNode<T>* nodeToDelete = head;
            head = head->next;
            delete nodeToDelete;
        }
        tail = nullptr;
    }

    // Insert a new node with the specified value at the head of the list
    void insertAtHead(T value) {
        DoublyLinkedListNode<T>* newNode = new DoublyLinkedListNode<T>(value);
        if (!head) { // If the list is empty
            head = tail = newNode;
        } else {
            newNode->next = head;
            head->prev = newNode;
            head = newNode;
        }
    }

    // Insert a new node with the specified value at the tail of the list
    void insertAtTail(T value) {
        DoublyLinkedListNode<T>* newNode = new DoublyLinkedListNode<T>(value);
        if (!tail) { // If the list is empty
            head = tail = newNode;
        } else {
            tail->next = newNode;
            newNode->prev = tail;
            tail = newNode;
        }
    }

    // Insert a new node at a specified position in the list
    void insertAtPosition(int position, T value) {
        if (position == 0) { // If the position is at the head
            insertAtHead(value);
            return;
        }

        DoublyLinkedListNode<T>* current = head;
        int index = 0;
        while (current != nullptr && index < position) {
            current = current->next;
            index++;
        }

        // Insert at the tail if position is out of bounds
        if (current == nullptr && index == position) {
            insertAtTail(value);
        } else if (current != nullptr) { // Insert in the middle
            DoublyLinkedListNode<T>* newNode = new DoublyLinkedListNode<T>(value);
            newNode->next = current;
            newNode->prev = current->prev;
            if (current->prev) {
                current->prev->next = newNode;
            }
            current->prev = newNode;
        }
    }

    // Remove a node at a specified position
    void removeAtPosition(int position) {
        if (position < 0 || head == nullptr) { // Handle invalid position or empty list
            cout << "Invalid position or list is empty." << endl;
            return;
        }

        if (position == 0) { // Removing the head node
            DoublyLinkedListNode<T>* nodeToDelete = head;
            head = head->next;
            if (head) {
                head->prev = nullptr;
            } else {
                tail = nullptr; // If the list is now empty
            }
            delete nodeToDelete;
            return;
        }

        DoublyLinkedListNode<T>* current = head;
        int index = 0;
        while (current != nullptr && index < position) {
            current = current->next;
            index++;
        }

        if (current != nullptr) { // Node found at the position
            if (current->next) {
                current->next->prev = current->prev;
            } else {
                tail = current->prev; // Update tail if last node is removed
            }
            if (current->prev) {
                current->prev->next = current->next;
            }
            delete current;
        } else {
            cout << "Position out of bounds." << endl;
        }
    }

    // Print the list in forward direction
       void printListForward() const {
           DoublyLinkedListNode<T>* current = head;
           while (current) {
               cout << current->value << " ";
               current = current->next;
           }
           cout << endl;
       }

       // Print the list in reverse direction
       void printListReverse() const {
           DoublyLinkedListNode<T>* current = tail;
           while (current) {
               cout << current->value << " ";
               current = current->prev;
           }
           cout << endl;
       }
   };

   #endif /* DoublyLinkedList_h */

//  Doubly Linked List Demonstration
//  Created by Kevin Roark

#include <iostream>
#include "DoublyLinkedList.h"
using namespace std;

// Main function to demonstrate the use of the doubly linked list
int main() {
    // Demonstrating DoublyLinkedList with integers
    DoublyLinkedList<int> myList; // Create a new list of integers

    // Insert elements at the head and tail
    myList.insertAtHead(1);
    myList.insertAtTail(2);
    myList.insertAtTail(5);
    myList.insertAtHead(10);

    // Print the integer list in both directions
    cout << "Printing Integer List Forward: " << endl;
    myList.printListForward();
    cout << "Printing Integer List Backward: " << endl;
    myList.printListReverse();

    // Insert an element at a specific position
    cout << "Inserting 20 at position 2 in Integer List: " << endl;
    myList.insertAtPosition(2, 20);
    myList.printListForward();

    // Remove an element at a specific position
    cout << "Removing element at position 1 in Integer List: " << endl;
    myList.removeAtPosition(1);
    myList.printListForward();

    // Demonstrating DoublyLinkedList with strings (Task List)
    DoublyLinkedList<string> taskList; // Create a new list of tasks (strings)

    // Insert tasks at the head and tail
    taskList.insertAtHead("Write report\n");
    taskList.insertAtTail("Attend meeting\n");
    taskList.insertAtTail("Review code\n");
    taskList.insertAtHead("Plan project\n");

    // Print the task list in both directions
    cout << "\nPrinting Task List Forward: " << endl;
    taskList.printListForward();
    cout << "Printing Task List Backward: " << endl;
    taskList.printListReverse();

    // Insert a task at a specific position
    cout << "Inserting 'Submit budget' at position 2 in Task List: " << endl;
    taskList.insertAtPosition(2, "Submit budget\n");
    taskList.printListForward();

    // Remove a task at a specific position
    cout << "Removing task at position 1 in Task List: " << endl;
    taskList.removeAtPosition(1);
    taskList.printListForward();

    return 0;
}

In this example, we define a DoublyLinkedListNode class to represent a node in the list, which has a value, a reference to the previous node, and a reference to the next node.

We then define a DoublyLinkedList class to represent the list itself, which has references to the head and tail of the list. We provide member functions to insert, remove and to print the list.

In the main function, we create a DoublyLinkedList object, insert and remove some nodes.

Doubly-linked lists have the advantage of allowing for efficient traversal of the list in both directions. However, they have some disadvantages, such as a higher overhead due to the need to maintain the prev pointers and more complex insertion and deletion operations.