Linked Lists - DSA Tutorial

Last modified - 11-08-2026

Author - Krishna Shinde

If you've been working through arrays and just started reading about linked lists, you've probably asked the same question every beginner in dsa asks: "why not just use an array?" It's a fair question, and answering it properly is the fastest way to actually understand what a linked list is for.

This C++ tutorial walks through what a linked list is, how it's structured in memory, the difference between singly and doubly linked lists, and how to implement one from scratch in C++. It's one of the core topics in data structures and algorithms, and once it clicks, patterns like reversal and cycle detection stop feeling like separate problems and start feeling like the same idea reused.

What Is a Linked List?

A linked list is a linear data structure made up of nodes, where each node holds a value and a pointer to the next node in the sequence. Unlike an array, the elements aren't stored in contiguous memory — each node can live anywhere in memory, and it's the pointer that stitches them together into a chain.

That single design choice is the reason linked lists exist at all. Arrays need a fixed, contiguous block of memory, so inserting or removing an element in the middle means shifting everything after it. A linked list just rewires a couple of pointers.

Why Not Just Use an Array?

Arrays and linked lists solve the same basic problem — storing an ordered collection of items — but they trade off different things:

*Amortized, assuming a dynamic array like std::vector.

The short version: pick an array when you need fast random access, and pick a linked list when you're doing a lot of insertions and deletions, especially near the front of the collection.

The Structure of a Node

Every linked list is built from a simple building block, the node. In C++, this is typically a small struct with a value and a pointer to the next node:

struct Node {

    int data;

    Node* next;

    Node(int val) {

        data = val;

        next = nullptr;

    }

};

The list itself is just a pointer to the first node, usually called the head. If the head is nullptr, the list is empty.

Singly Linked List: Building One From Scratch

Let's build a minimal singly linked list with insertion at the head, insertion at the tail, and a traversal function to print it.

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* next;

    Node(int val) : data(val), next(nullptr) {}
};

class LinkedList {
private:
    Node* head;

public:
    LinkedList() {
        head = nullptr;
    }

    void insertAtHead(int val) {
        Node* newNode = new Node(val);
        newNode->next = head;
        head = newNode;
    }

    void insertAtTail(int val) {
        Node* newNode = new Node(val);

        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) {
            cout << temp->data << " -> ";
            temp = temp->next;
        }

        cout << "NULL" << endl;
    }
};

int main() {
    LinkedList list;

    list.insertAtTail(10);
    list.insertAtTail(20);
    list.insertAtTail(30);
    list.insertAtHead(5);

    list.printList();

    return 0;
}

Output:

5 -> 10 -> 20 -> 30 -> NULL

Notice that insertAtHead is a constant-time operation — it doesn't matter how long the list is, we're just rewiring one pointer. insertAtTail, on the other hand, has to walk the entire list to find the last node, which is O(n) unless you keep a separate tail pointer.

Deleting a Node

Deletion follows the same pattern as insertion: find the node just before the one you want to remove, then skip over it.

void deleteValue(int val) {

    if (head == nullptr) return;

    if (head->data == val) {

        Node* temp = head;

        head = head->next;

        delete temp;

        return;

    }

    Node* current = head;

    while (current->next != nullptr && current->next->data != val) {

        current = current->next;

    }

    if (current->next != nullptr) {

        Node* temp = current->next;

        current->next = current->next->next;

        delete temp;

    }

}

This is also where linked lists earn their keep in real interview problems — once you understand this "skip over the node" pattern, reversing a list and detecting cycles both come from the same core idea, just applied differently.

Singly vs. Doubly Linked Lists

A singly linked list only has a next pointer, so you can only traverse it in one direction. A doubly linked list adds a prev pointer to each node, letting you move backward as well:

struct DoublyNode {

    int data;

    DoublyNode* next;

    DoublyNode* prev;

    DoublyNode(int val) : data(val), next(nullptr), prev(nullptr) {}

};

The extra pointer costs more memory per node, but it makes operations like deleting a node you already have a reference to, or traversing backward, run in constant time instead of requiring a full pass from the head.

Time and Space Complexity

When Should You Actually Use a Linked List?

Linked lists aren't the default choice for most day-to-day programming — std::vector and arrays win more often than not, especially when cache locality matters. But they're the right tool when:

1. You're inserting and deleting frequently, especially near the front of the collection.
2. You don't know the size of your collection in advance and don't want to deal with resizing.
3. You're implementing another structure on top, like a stack, a queue, or a graph's adjacency list.
4. You need constant-time removal of a node you already have a reference to (common in LRU cache implementations).

Conclusion

A linked list trades the fast random access of an array for cheap insertions and deletions, by giving up contiguous memory and relying on pointers instead. Once that trade-off clicks, the rest of the topic — singly vs. doubly linked, reversal, cycle detection — is just variations on the same "follow the pointer" idea. Practice building one from scratch in C++ until insertAtHead, insertAtTail, and deleteValue feel automatic, because that muscle memory is exactly what shows up in dsa interview questions next.

Linked lists show up again and again once you start solving harder problems in data structures and algorithms, so the time spent building one from scratch now pays off well beyond this one topic. Keep this pattern in your back pocket as you move deeper into programming — it's the same "follow the pointer" thinking that powers stacks, queues, and even graph adjacency lists later on.