#include <iostream>
using namespace std;

template <typename T>
class dll {
private:
    struct Node {
        Node* prev;
        Node* next;
        T data;
    };

    Node* head;
    Node* tail;

public:
    dll();
    ~dll();

    void insert(T value);

    bool empty() const { return head == tail; };
};

template <typename T> dll<T>::dll() {
    head = nullptr;
    tail = head;
}

template <typename T> dll<T>::~dll() {
    delete[] head;
}

template <typename T> void dll<T>::insert(T value) {
    Node *node = new Node;
    std::cout << node << '\n';
    node->data = value;
    // Case 1: There are no nodes yet
    if (head == nullptr) {
        node->prev = nullptr;
        node->next = nullptr;
        head = node;
        tail = head;
    }
    else {
        // Case 2: There is more than one node
        Node *curr = head;
        if (curr->next != nullptr)
        {
            while (curr->next) {
                // If the value is less than the current value
                if (value < curr->data) {
                    Node *temp = new Node;
                    temp->data = curr->data;
                    temp->next = curr->next;
                    temp->prev = curr->prev;
                    node->next = temp;
                    node->prev = temp->prev;
                    curr->prev = node;
                }
                curr = curr->next;
            }
        }
        // Case 3: There is only one node
        else {
            node->prev = head;
            node->next = nullptr;
            tail = node;
        }
    }
}

int main() {
    dll<int> list;
    list.insert(10);
    list.insert(20);
    list.insert(15);
}