4.2 ~75 min medium

Singly Linked List

Nodes on the heap, each pointing to the next. Insert at front, end or a position, delete by value, search and traverse, plus the dummy-node trick and the classic pitfalls.

Rule of this site: Don't just watch: implement it yourself, then solve 2–3 problems.

02Mental model

A treasure hunt: each clue tells you where the next clue is hidden. You can’t jump to clue #7. You must follow clues 1 → 2 → … → 7. But adding a new clue in the middle is easy: change one clue to point to the new one, and the new one to point onward.

That is a singly linked list: nodes scattered around the heap, each holding data and a pointer to the next node. The program only keeps head, the address of the first node. The last node’s next is nullptr.

struct Node {
    int data;
    Node* next;
};

The golden rule of rewiring

When inserting, connect the new node first, then redirect the old pointer. If you move head (or temp->next) first, you lose the rest of the list.

Deleting needs the node before

To remove node X you change the arrow that points to X, and that arrow belongs to the previous node. So deletion walks with a prev pointer. Deleting the head is a special case: there is no previous node.

The dummy (sentinel) node

Put a fake node before the head: Node dummy{0, head};. Now every real node, including the first, has a previous node, so one loop handles all cases. At the end, head = dummy.next.

Pitfalls checklist

Check nullptr before every ->.
Handle the empty list, one node, head and tail cases.
delete every node you unlink.
Never move head to traverse. Use a temp copy.

03Visualize

space play · ←→ step · r reset. The highlighted code line follows each step.

Loading visualizer…

Try: insert front 9, insert at pos 2, delete the head, then "Delete (dummy)" on the new head. Notice the dummy needs no special case.

04C++ code

Compiled and run with g++ -std=c++17; the output below is real. Type it out yourself before you copy it.

singly-linked-list.cpp103 lines · C++17

Compiler ExplorerRun OnlineGDB

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* next;
};

void insertFront(Node*& head, int x) {
    Node* n = new Node{x, nullptr};
    n->next = head;          // 1. new node points at the old head
    head = n;                // 2. head points at the new node
}

void insertEnd(Node*& head, int x) {
    Node* n = new Node{x, nullptr};
    if (head == nullptr) { head = n; return; }
    Node* temp = head;
    while (temp->next != nullptr)
        temp = temp->next;
    temp->next = n;
}

void insertAt(Node*& head, int pos, int x) {      // pos is 0-based
    if (pos == 0) { insertFront(head, x); return; }
    Node* temp = head;
    for (int i = 0; i < pos - 1 && temp != nullptr; i++)
        temp = temp->next;
    if (temp == nullptr) return;                  // position too big
    Node* n = new Node{x, temp->next};
    temp->next = n;
}

void deleteValue(Node*& head, int x) {
    if (head == nullptr) return;
    if (head->data == x) {                        // deleting the head
        Node* temp = head;
        head = head->next;
        delete temp;
        return;
    }
    Node* prev = head;
    while (prev->next != nullptr && prev->next->data != x)
        prev = prev->next;
    if (prev->next == nullptr) return;            // not found
    Node* temp = prev->next;
    prev->next = temp->next;
    delete temp;
}

void deleteDummy(Node*& head, int x) {            // same job, no special case
    Node dummy{0, head};
    Node* prev = &dummy;
    while (prev->next != nullptr && prev->next->data != x)
        prev = prev->next;
    if (prev->next != nullptr) {
        Node* temp = prev->next;
        prev->next = temp->next;
        delete temp;
    }
    head = dummy.next;
}

bool search(Node* head, int x) {
    Node* temp = head;
    while (temp != nullptr) {
        if (temp->data == x) return true;
        temp = temp->next;
    }
    return false;
}

void print(Node* head) {
    for (Node* t = head; t != nullptr; t = t->next) cout << t->data << " -> ";
    cout << "null\n";
}

void freeList(Node*& head) {
    while (head != nullptr) {
        Node* temp = head;
        head = head->next;
        delete temp;
    }
}

int main() {
    Node* head = nullptr;
    insertEnd(head, 12);
    insertEnd(head, 7);
    insertEnd(head, 31);
    insertFront(head, 9);
    print(head);
    insertAt(head, 2, 15);
    print(head);
    deleteValue(head, 9);      // head
    deleteValue(head, 31);     // tail
    print(head);
    deleteDummy(head, 12);     // new head, handled by the dummy
    print(head);
    cout << "search 15: " << search(head, 15) << ", search 99: " << search(head, 99) << "\n";
    freeList(head);
    print(head);
}

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* next;
};

void insertFront(Node*& head, int x) {
    Node* n = new Node{x, nullptr};
    n->next = head;          // 1. new node points at the old head
    head = n;                // 2. head points at the new node
}

void insertEnd(Node*& head, int x) {
    Node* n = new Node{x, nullptr};
    if (head == nullptr) { head = n; return; }
    Node* temp = head;
    while (temp->next != nullptr)
        temp = temp->next;
    temp->next = n;
}

void insertAt(Node*& head, int pos, int x) {      // pos is 0-based
    if (pos == 0) { insertFront(head, x); return; }
    Node* temp = head;
    for (int i = 0; i < pos - 1 && temp != nullptr; i++)
        temp = temp->next;
    if (temp == nullptr) return;                  // position too big
    Node* n = new Node{x, temp->next};
    temp->next = n;
}

void deleteValue(Node*& head, int x) {
    if (head == nullptr) return;
    if (head->data == x) {                        // deleting the head
        Node* temp = head;
        head = head->next;
        delete temp;
        return;
    }
    Node* prev = head;
    while (prev->next != nullptr && prev->next->data != x)
        prev = prev->next;
    if (prev->next == nullptr) return;            // not found
    Node* temp = prev->next;
    prev->next = temp->next;
    delete temp;
}

void deleteDummy(Node*& head, int x) {            // same job, no special case
    Node dummy{0, head};
    Node* prev = &dummy;
    while (prev->next != nullptr && prev->next->data != x)
        prev = prev->next;
    if (prev->next != nullptr) {
        Node* temp = prev->next;
        prev->next = temp->next;
        delete temp;
    }
    head = dummy.next;
}

bool search(Node* head, int x) {
    Node* temp = head;
    while (temp != nullptr) {
        if (temp->data == x) return true;
        temp = temp->next;
    }
    return false;
}

void print(Node* head) {
    for (Node* t = head; t != nullptr; t = t->next) cout << t->data << " -> ";
    cout << "null\n";
}

void freeList(Node*& head) {
    while (head != nullptr) {
        Node* temp = head;
        head = head->next;
        delete temp;
    }
}

int main() {
    Node* head = nullptr;
    insertEnd(head, 12);
    insertEnd(head, 7);
    insertEnd(head, 31);
    insertFront(head, 9);
    print(head);
    insertAt(head, 2, 15);
    print(head);
    deleteValue(head, 9);      // head
    deleteValue(head, 31);     // tail
    print(head);
    deleteDummy(head, 12);     // new head, handled by the dummy
    print(head);
    cout << "search 15: " << search(head, 15) << ", search 99: " << search(head, 99) << "\n";
    freeList(head);
    print(head);
}

Expected output

9 -> 12 -> 7 -> 31 -> null
9 -> 12 -> 15 -> 7 -> 31 -> null
12 -> 15 -> 7 -> null
15 -> 7 -> null
search 15: 1, search 99: 0
null

05Complexity

Insert at front	O(1)
Insert at end	O(n), or O(1) with a tail pointer
Insert at position k	O(k)
Delete by value / search	O(n)
Access the i-th item	O(n): no random access
Extra space	O(n) plus one pointer per node

Compared with an array, a linked list wins at inserting and deleting (no shifting) and loses at indexing (must walk) and cache-friendliness.

06Watch

Introduction to linked list

mycodeschool · 17:13

Why this one: Why linked lists exist and how they compare with arrays.

Watched

Linked List: Implementation in C/C++

mycodeschool · 13:58

Why this one: Writes the C/C++ node struct and insertion functions line by line.

Watched

Data Structures: Full Course Using C and C++

freeCodeCamp.org · 9h 46m

Why this one: The full freeCodeCamp version of mycodeschool's course; includes insert at nth position and delete.

Watched

Original class slides (Python, by the course's lecture authors):Linked List

07Exam lens

Likely questions

Write a function to insert a node at the beginning, at the end and at a given position of a singly linked list.
Write a function that deletes the first node with a given value.
Compare arrays and linked lists (memory, access, insertion, deletion).
What is a dummy (sentinel) node and why does it simplify deletion?
What happens if you write head = n; n->next = head; (wrong order)?

Common mistakes

Losing the list by updating head before linking the new node (head = n; first).
Dereferencing temp->next without checking temp != nullptr.
Forgetting the empty-list and delete-the-head special cases.
Not calling delete on removed nodes (memory leak).
Passing Node* head by value to a function that changes head. Use Node*& head.

08Quick check

1.Correct order to insert node n at the front?
2.To delete a node in a singly linked list you need a pointer to…

3.What does this print? List: 3 → 8 → 5

int c = 0;
for (Node* t = head; t; t = t->next) c += t->data;
cout << c;

4.Why use a dummy node?
5.Why must insertFront take Node*& head?

09Practice

🟢 Trace by hand

Start empty. Do insertEnd 4, insertFront 7, insertAt(1, 2), insertEnd 9, delete 7, delete 9. Write the list after each step.

Show answer

insertEnd 4 → 4
insertFront 7 → 7 → 4
insertAt(1, 2) → 7 → 2 → 4
insertEnd 9 → 7 → 2 → 4 → 9
delete 7 (head case) → 2 → 4 → 9
delete 9 → 2 → 4

🟡 Implement it

Write reverse(Node*& head) (iterative, O(1) extra space), length(Node* head) and deleteAt(Node*& head, int pos).

Hint

Reverse: keep prev = nullptr, cur = head. Each step: save next = cur->next, set cur->next = prev, move prev = cur, cur = next. Finally head = prev.

Solution

void reverse(Node*& head) {
    Node* prev = nullptr;
    Node* cur = head;
    while (cur) {
        Node* next = cur->next;
        cur->next = prev;
        prev = cur;
        cur = next;
    }
    head = prev;
}

🔴 Solve problems

Reverse Linked List easyleetcode.com
Hint
Three pointers, prev / cur / next. Draw it.
Remove Duplicates from Sorted List easyleetcode.com
Hint
While cur->next has the same value as cur, unlink it.
Merge Two Sorted Lists easyleetcode.com
Hint
A dummy node plus a tail pointer. Always attach the smaller head.

Solution idea
ListNode d; ListNode* t = &d; while (a && b) { if (a->val <= b->val) { t->next = a; a = a->next; } else { t->next = b; b = b->next; } t = t->next; } t->next = a ? a : b; return d.next;
Reverse Linked List II mediumleetcode.com
Hint
Walk to the node before position left, then reverse the sublist with the same three-pointer trick. A dummy node saves you when left = 1.

10Mastery checklist

Tick these honestly. When every box is ticked, the topic is marked complete.

I can insert at the front, the end and a position without losing the list.
I can delete by value, including the head and not-found cases.
I can use a dummy node to remove special cases.
I can reverse a linked list iteratively.
I free every removed node with delete.

0/5 ticked

My notes

View as Markdown · Chapter cheat sheet