Building a Universal Doubly Linked List in C++: A Step-by-Step Template Implementation

Introduction: Why a Universal List?

In modern programming, containers that can hold any data type and resize dynamically are essential. Think of a playlist on a music streaming app that can hold songs, podcasts, or audiobooks — all mixed together. In C++, the Standard Template Library (STL) provides std::list, but building your own doubly linked list from scratch is a rite of passage that deepens your understanding of pointers, memory management, and templates. This tutorial will guide you through creating a universal doubly linked list that can store any type, complete with an external bidirectional iterator.

Understanding the Doubly Linked List

A doubly linked list consists of nodes, each containing a data element and two pointers: one pointing to the next node and one to the previous node. The first node's previous pointer is nullptr, and the last node's next pointer is nullptr. This structure allows efficient insertion and removal at both ends and traversal in both directions.

Why not just use a vector? Unlike arrays, linked lists don't require contiguous memory, so inserting in the middle is O(1) once you have the position. However, random access is O(n). For applications like a color swatch manager that frequently adds and removes items from the front, back, or center, a doubly linked list shines.

Step 1: The Dnode Class

Start by creating a template node class. Each node stores data and two pointers. The constructor sets both pointers to nullptr by default.

template <typename T>
class Dnode {
public:
    T data;
    Dnode* next;
    Dnode* prev;
    Dnode(const T& d = T(), Dnode* n = nullptr, Dnode* p = nullptr)
        : data(d), next(n), prev(p) {}
    // Accessors
    T get_data() const { return data; }
    Dnode* get_next() const { return next; }
    Dnode* get_prev() const { return prev; }
    // Mutators
    void set_data(const T& d) { data = d; }
    void set_next(Dnode* n) { next = n; }
    void set_prev(Dnode* p) { prev = p; }
};

This node class is the building block. Notice that we use default arguments in the constructor — a common C++ pattern that reduces overloads.

Step 2: The Dlist Class (Shell)

Now create the list class with head and tail pointers. Initially, both are nullptr. The default constructor is trivial.

template <typename T>
class Dlist {
public:
    Dlist() : head(nullptr), tail(nullptr) {}
    // Big Three will go here
    // front_insert, rear_insert, etc.
private:
    Dnode<T>* head;
    Dnode<T>* tail;
};

Step 3: Basic Operations — front_insert, rear_insert, front_remove, rear_remove

These are the core mutators. For front_insert, create a new node and link it before the current head. If the list is empty, set both head and tail to the new node.

void front_insert(const T& item) {
    Dnode<T>* new_node = new Dnode<T>(item, head, nullptr);
    if (head != nullptr)
        head->prev = new_node;
    else
        tail = new_node;
    head = new_node;
}

Similarly, rear_insert appends at the end. front_remove deletes the head node and updates pointers. Remember to handle the single-node case carefully — a common source of segmentation faults.

Step 4: The Big Three

Because your list manages dynamic memory, you must implement the destructor, copy constructor, and copy assignment operator. The destructor should delete all nodes. The copy constructor and assignment operator must deep-copy the entire list, preserving both next and prev pointers.

// Destructor
~Dlist() {
    while (head != nullptr) {
        Dnode<T>* temp = head;
        head = head->next;
        delete temp;
    }
    tail = nullptr;
}

// Copy constructor
Dlist(const Dlist& other) : head(nullptr), tail(nullptr) {
    Dnode<T>* cursor = other.head;
    while (cursor != nullptr) {
        rear_insert(cursor->data);
        cursor = cursor->next;
    }
}

For assignment, use the copy-and-swap idiom or clear the current list first, then copy. Always test with a show_all helper function to verify correctness.

Step 5: External Bidirectional Iterator

An iterator is an object that allows traversing the container without exposing internal pointers. For a doubly linked list, we need a bidirectional iterator that can move forward (++) and backward (--). Create an iterator class that wraps a node pointer.

template <typename T>
class DlistIterator {
public:
    DlistIterator(Dnode<T>* n = nullptr) : current(n) {}
    T& operator*() const { return current->data; }
    DlistIterator& operator++() { current = current->next; return *this; }
    DlistIterator& operator--() { current = current->prev; return *this; }
    bool operator!=(const DlistIterator& other) const {
        return current != other.current;
    }
private:
    Dnode<T>* current;
};

Then add begin(), end(), r_begin(), and r_end() methods to the list class. end() returns an iterator with nullptr, while r_begin() starts at tail and r_end() is nullptr.

Step 6: Insert and Remove with Iterators

Now implement insert_before, insert_after, and remove that take an iterator. For example, insert_before creates a new node and links it before the node pointed to by the iterator.

void insert_before(DlistIterator<T> pos, const T& item) {
    Dnode<T>* pos_node = pos.current;
    if (pos_node == head) {
        front_insert(item);
        return;
    }
    Dnode<T>* new_node = new Dnode<T>(item, pos_node, pos_node->prev);
    pos_node->prev->next = new_node;
    pos_node->prev = new_node;
}

Similarly, remove deletes the node at the iterator and returns an iterator to the next node (or end()).

Practical Example: Color Swatch Organizer

Imagine you're building a tool for a graphic design app that organizes color swatches. Each swatch is a hex color (e.g., #cc0099) and dimensions. The application reads a file of swatches and sorts them: predominantly red swatches go to the front, green to the back, and blue to the center. Then it makes a copy, removes the first, last, and center swatch from the copy, and outputs both lists forward and backward — all using your universal list.

This mirrors real-world tasks like sorting a playlist by genre or managing a leaderboard in a gaming tournament where you need to quickly add and remove players from different positions.

Testing and Debugging Tips

Compile incrementally with g++ -g main1.cc. Use a show_all function to print the list after each operation. Draw diagrams of pointer connections — especially during insertions and removals — to avoid segfaults. Remember that the Big Three must be correct or your program will crash when copying or destroying lists.

Conclusion

Building a universal doubly linked list in C++ is a challenging but rewarding exercise. You've learned to create a template class, manage dynamic memory, and implement an external iterator. These skills are directly applicable to advanced projects like building custom containers, game engines, or real-time data processing systems. Now go ahead and implement your own Dlist — and don't forget to test every step!