I've always found that the best way to actually "get" linked lists isn't by looking at a diagram of arrows and boxes, but by watching a program crash because you forgot to update a pointer. So, let's build a custom container from scratch. We're going to build a simple history buffer—something that could track a sequence of strings representing "Undo" actions in a text editor.

Starting with the bare bones

My first instinct is usually to just throw a struct together. We need a node that holds the data and a pointer to the next thing in line. Let's see what happens if we just try to link these manually in main.

struct Node {
    std::string data;
    Node* next;
};

// In main...
Node* head = new Node{"Type 'Hello'", nullptr};
Node* second = new Node{"Bold text", nullptr};
head->next = second;

This works, but it's miserable. If I want to add a tenth item, I'm writing ten lines of boilerplate. I'm essentially doing the container's job manually. I need a class to wrap this logic so I can just call push_back() and let the class handle the pointer gymnastics.

The "Empty List" Headache

I'll start by wrapping this in a LinkedList class. I want a push_back method. Here is my first attempt at the logic:

class LinkedList {
    Node* head = nullptr;
public:
    void push_back(std::string value) {
        Node* newNode = new Node{value, nullptr};
        Node* temp = head;
        while (temp->next != nullptr) {
            temp = temp->next;
        }
        temp->next = newNode;
    }
};

I ran this, and it immediately segfaulted. Why? I looked at the while loop. If the list is empty, head is nullptr. I'm trying to access temp->next (which is nullptr->next), and the OS shuts me down instantly. I forgot the most important edge case: the very first element.

I have to handle the empty state separately. If head is null, the new node is the head. Only then can I start traversing.

void push_back(std::string value) {
    Node* newNode = new Node{value, nullptr};
    if (head == nullptr) {
        head = newNode;
        return;
    }
    Node* temp = head;
    while (temp->next != nullptr) {
        temp = temp->next;
    }
    temp->next = newNode;
}

Hunting for the Memory Leak

Now it works for adding, but what about removing? Let's try a pop_front to remove the oldest history item. I'll just shift the head pointer forward.

void pop_front() {
    if (head == nullptr) return;
    head = head->next;
}

At first glance, this looks clean. The first element is "gone" from the list. But here's the problem: that first node is still sitting in heap memory, and I no longer have a pointer to it. I've just created a memory leak. In a long-running text editor, this would slowly eat all the available RAM.

I need to capture that node in a temporary pointer, move the head, and then explicitly call delete. I also realized that if I destroy the whole LinkedList object, all the remaining nodes stay in memory. I need a destructor to clean up the entire chain.

~LinkedList() {
    while (head != nullptr) {
        pop_front();
    }
}

void pop_front() {
    if (head == nullptr) return;
    Node* temp = head;
    head = head->next;
    delete temp; // Finally, the memory is freed
}

Generalizing with Templates

Right now, this only works for std::string. If I suddenly want to store int IDs or a custom Command object, I'd have to rewrite the whole class. This is where templates come in. I'll replace std::string with a placeholder T.

One thing to watch out for: the Node struct also needs to be templated, otherwise the LinkedList<T> can't use it. It's cleaner to just nest the Node inside the class as a private struct.

template <typename T>
class LinkedList {
    struct Node {
        T data;
        Node* next;
    };
    Node* head = nullptr;

public:
    void push_back(T value) {
        Node* newNode = new Node{value, nullptr};
        if (!head) {
            head = newNode;
            return;
        }
        Node* temp = head;
        while (temp->next) temp = temp->next;
        temp->next = newNode;
    }
    // ... pop_front and destructor stay logically the same ...
};

By moving to templates, I've turned a specific "undo string list" into a generic container. It's not as fast as a std::vector for random access, but for adding and removing from the ends, it's exactly what we need.

📋 Practical Task

Exercise: Implementing a Doubly-Linked Undo/Redo Buffer

Your task is to extend the LinkedList concept to support bidirectional navigation. In a real undo/redo system, you don't just want to remove the front; you want to move a "current" pointer back and forth through the history.

Modify the provided LinkedList template to create a DoublyLinkedList with the following requirements:

• Add a Node* prev pointer to the internal Node struct.
• Update push_back so that the new node's prev pointer correctly points to the previous tail.
• Implement a pop_back() method that removes the last element of the list. (Hint: You'll need to keep track of a tail pointer in the class to avoid traversing the whole list every time).
• Ensure the destructor correctly cleans up all nodes to prevent memory leaks.

Test your implementation by creating a DoublyLinkedList<int>, adding five integers, popping two from the back, and verifying the remaining elements are still correctly linked in both directions.