Think of a linked list like a scavenger hunt. In a standard array, everyone is sitting in a row of numbered seats; if you want the fifth person, you just go to seat five. But in a scavenger hunt, you only know where the first clue is. That first clue gives you a piece of information (the data) and a slip of paper telling you exactly where to find the second clue. The second clue leads to the third, and so on. You can't just jump to the middle of the hunt—you have to follow the trail from the start.

In C++, we map this directly to memory. Each "clue" is a struct or class we call a Node. The "information" is your actual data, and the "slip of paper" is a pointer to the next Node in the sequence. When you hit a clue that says "The end," that's our nullptr.

Designing the Node

First, we need the building block. I usually prefer a simple struct for the Node because it's essentially just a data container. We need two things: the value we're storing and a pointer to another object of the same type.

struct Node {
    int data;
    Node* next;

    // A quick constructor makes life much easier when adding new nodes
    Node(int val) : data(val), next(nullptr) {}
};

Notice that next is a pointer to a Node. This is a recursive definition, which is the "magic" that allows the list to grow indefinitely. As long as you have a pointer to the next link, the chain continues.

Managing the Chain

Now, we need a way to keep track of where the hunt starts. If you lose the first clue, the rest of the list is lost in memory (a classic memory leak). I'll wrap this logic in a LinkedList class to keep the head pointer protected.

class LinkedList {
private:
    Node* head;

public:
    LinkedList() : head(nullptr) {}

    void append(int value) {
        Node* newNode = new Node(value);
        
        if (head == nullptr) {
            head = newNode;
            return;
        }

        Node* temp = head;
        while (temp->next != nullptr) {
            temp = temp->next;
        }
        temp->next = newNode;
    }

    void printList() {
        Node* temp = head;
        while (temp != nullptr) {
            std::cout << temp->data << " -> ";
            temp = temp->next;
        }
        std::cout << "nullptr" << std::endl;
    }
};

I used a while loop in the append method because, unlike an array, we can't just index to the end. We have to "walk" the list from the head until we find the node where next is nullptr. It's a bit slower than array access, but it makes inserting items into the middle of the list incredibly fast later on, because you just swap a few pointers instead of shifting thousands of elements.

The Responsibility of Cleanup

Since we're using new to create each Node, these are living on the heap. If your LinkedList object goes out of scope, the head pointer vanishes, but the Nodes stay in memory, orphaned. In a professional environment, this is a bug that gets you a stern talking-to during code review. You need a destructor to walk the list and delete every single node.

~LinkedList() {
    Node* current = head;
    while (current != nullptr) {
        Node* nextNode = current->next;
        delete current;
        current = nextNode;
    }
}

I always make sure to save the nextNode pointer before deleting the current one. If you delete the node first, you've just destroyed the only map you had to the rest of the list.

📋 Practical Task

Implement a Music Playlist Manager

Your task is to expand the Linked List concept into a simple Music Playlist Manager. Instead of storing integers, create a Song struct that contains a std::string title and std::string artist.

Build a Playlist class with the following specific requirements:

• addSong(string title, string artist): Appends a new song to the end of the playlist.
• removeFirst(): Removes the first song from the playlist (simulating "playing" the song and moving it off the list). Ensure you handle memory correctly so there are no leaks.
• showPlaylist(): Prints the title and artist of every song in the list in order.

Test your implementation by adding three songs, removing the first one, and printing the remaining list to verify the "head" of your list shifted correctly.