SyntaxPilot
Courses/C++ Coding Questions/Lesson 22
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

C++ Coding Questions · Lesson 22 of 30

Linked list questions I

build and print a list with a Node structinsert at head and taildelete by value (head and missing cases)freeing memory

These are the notes for C++ Coding Questions, episode 22, placement practice for people who finished the SyntaxPilot C++ course. Today is the first of two episodes on linked lists, the place where interviews check whether you really understand pointers: building and printing a list (without losing it), inserting at the head and the tail (why Node* head changes nothing, and the empty-list crash), and deleting by value (the head case, the missing case) followed by freeing every node (memory leaks and use-after-free).

Each question follows the same steps: read the problem, think out loud, the obvious attempt, a real failure, why, the fix, every test case, and the complexity.

Every program was compiled with g++ -Wall -O2 -std=c++17 main.cpp -o main (g++ 13.3, Linux x86-64), the SyntaxPilot compiler's C++ command with warnings on, and every output below is real. When a program crashes, the compiler shows Segmentation fault, like a terminal does.

Real-life pictures

In real life In C++
A treasure hunt: every chit has a clue and the place of the next chit a node: data + next
The last chit says "the end" next == nullptr
Only the FIRST chit's place is written on your hand head, a pointer to the first node
A row of cinema seats, side by side: a friend at the front means everyone shifts a vector: insert at the front is O(n)
A new first chit: write the old first place on it, then on your hand insert at the head: O(1)
Rubbing the first place off your hand while you walk head = head->next while printing: the list is lost
A helper writes the new start on a PHOTOCOPY of your hand pushFront(Node* head, ...): changes a copy
Giving the helper your real hand Node*& head, a reference to the pointer
Taking a chit out: the chit before it must point past it prev->next = gone->next
Taking out the FIRST chit: change your hand head = head->next
Collecting every chit after the game: read the next place before you bin a chit freeList: save next, then delete

A linked list in one minute

A linked list stores values in separate nodes (boxes) that are linked by pointers. Unlike a vector, the boxes are not side by side in memory: each one knows only where the next one is.

struct Node {
    int data;      // the value in this box
    Node* next;    // where the next box is (nullptr = the end)
};
head
 |
 v
[10 | *] --> [20 | *] --> [30 | nullptr]
  • Node: one box, data + next.
  • head: a pointer to the first node. It is the only way into the list: lose it and the list is lost.
  • Empty list: head == nullptr. This case causes most linked-list crashes, so check it first in every function.
  • Tail: the last node, whose next is nullptr. Keeping a tail pointer makes adding at the end O(1).
  • new Node{x, nullptr} makes a box on the heap, memory that stays alive until you give it back with delete. Every new needs exactly one delete.
  • -> follows a pointer: cur->data is the data of the box cur points to (the same as (*cur).data).
  • Traversal (walking the list): for (Node* cur = head; cur != nullptr; cur = cur->next).

Q1: Build a list from input and print it

Problem. Read n, then n numbers. Build a linked list in the same order and print it as 10 -> 20 -> 30 -> NULL, twice (real programs use a list more than once).

Think out loud. Input: n and n numbers. Output: the list, two times. To keep the input order we add each box at the end; walking to the end every time would be slow, so keep a second pointer, tail, at the last box. Edge cases: n = 0 (just NULL), printing more than once.

The obvious attempt: print by moving head

#include <iostream>
using namespace std;

struct Node {
    int data;                            // the value in this box
    Node* next;                          // where the next box is
};

int main() {
    int n;
    cin >> n;
    Node* head = nullptr;                // the list starts empty
    Node* tail = nullptr;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        Node* node = new Node{x, nullptr};   // a new box on the heap
        if (head == nullptr) head = node;    // the very first box
        else tail->next = node;              // link it after the last
        tail = node;
    }
    for (int k = 0; k < 2; k++) {        // print it twice
        while (head != nullptr) {
            cout << head->data << " -> ";
            head = head->next;
        }
        cout << "NULL\n";
    }
    return 0;
}

Input:

3
10 20 30

Output:

10 -> 20 -> 30 -> NULL
NULL

The first print is perfect. The second prints only NULL.

Why it fails

head = head->next moves head itself: 10, then 20, then 30, then nullptr. After the first print head is nullptr. The three boxes are still in memory, but no pointer leads to them any more: the list is lost, and its memory is leaked (it can never be deleted). It is like rubbing the first chit's place off your hand while you walk.

Fix: walk with a separate pointer

Walk with cur, which starts at head. Put it in a print function that takes head by value: the function gets its own copy of the address, so walking cannot hurt the original.

#include <iostream>
using namespace std;

struct Node {
    int data;                            // the value in this box
    Node* next;                          // where the next box is
};

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

int main() {
    int n;
    cin >> n;
    Node* head = nullptr;                // the list starts empty
    Node* tail = nullptr;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        Node* node = new Node{x, nullptr};   // a new box on the heap
        if (head == nullptr) head = node;    // the very first box
        else tail->next = node;              // link it after the last
        tail = node;
    }
    print(head);
    print(head);                         // head never moved
    return 0;
}

Input:

3
10 20 30

Output:

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

Input 0:

NULL
NULL

Complexity. Building: O(n), each box is linked after tail in O(1). Printing: O(n). Space: O(n), one node per value (each node also stores one pointer, 8 bytes on a 64-bit machine).

These notes free every list in the later programs. This first program ends without delete; when main returns, the operating system takes the memory back anyway, but in a long-running program that would be a leak (see Q3).

Q2: Insert at the head and at the tail

Problem. Build a list from n numbers, then read q commands: F x inserts x at the front, B x inserts x at the back. Print the list at the end.

Input Output
10 20 30, F 5, B 40 5 -> 10 -> 20 -> 30 -> 40 -> NULL
empty, B 7 7 -> NULL
empty, B 7, F 3 3 -> 7 -> NULL

Think out loud. Front: the new box points to the old head, then head becomes the new box. Back: walk to the last box and link the new one after it. Edge cases: the empty list (there is no last box), a list of one box.

The obvious attempt: Node* head parameters

#include <iostream>
using namespace std;

struct Node {
    int data;                            // the value in this box
    Node* next;                          // where the next box is
};

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

void pushFront(Node* head, int x) {
    Node* node = new Node{x, head};      // new box points at the old first
    head = node;                         // it is the new first box
}

void pushBack(Node* head, int x) {
    Node* node = new Node{x, nullptr};
    Node* cur = head;
    while (cur->next != nullptr)         // walk to the last box
        cur = cur->next;
    cur->next = node;
}

int main() {
    int n, q;
    cin >> n;
    Node* head = nullptr;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        if (head == nullptr) head = new Node{x, nullptr};
        else pushBack(head, x);
    }
    cin >> q;
    while (q--) {                        // F x = front, B x = back
        char op;
        int x;
        cin >> op >> x;
        if (op == 'F') pushFront(head, x);
        else pushBack(head, x);
    }
    print(head);
    return 0;
}

Input:

3
10 20 30
2
F 5
B 40

Output:

10 -> 20 -> 30 -> 40 -> NULL

40 arrived at the end, but 5 vanished. No error, no warning.

Why it fails: pushFront changed a copy of head

void pushFront(Node* head, int x) receives head by value: a copy of the address. head = node; changes the copy, and the copy disappears when the function returns. main's head still points to 10, and the new box (5) is leaked.

Why did pushBack work? It never changes head. It changes a box: cur->next = node. The copy points to the same boxes as the original, so that change is real. Rule: a function that may change which box is first must take Node*& head (a reference to the pointer, another name for the caller's own head). Another option is to return the new head: head = pushFront(head, x);.

Fix 1: Node*& head

#include <iostream>
using namespace std;

struct Node {
    int data;                            // the value in this box
    Node* next;                          // where the next box is
};

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

void pushFront(Node*& head, int x) {
    Node* node = new Node{x, head};      // new box points at the old first
    head = node;                         // it is the new first box
}

void pushBack(Node*& head, int x) {
    Node* node = new Node{x, nullptr};
    Node* cur = head;
    while (cur->next != nullptr)         // walk to the last box
        cur = cur->next;
    cur->next = node;
}

int main() {
    int n, q;
    cin >> n;
    Node* head = nullptr;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        if (head == nullptr) head = new Node{x, nullptr};
        else pushBack(head, x);
    }
    cin >> q;
    while (q--) {                        // F x = front, B x = back
        char op;
        int x;
        cin >> op >> x;
        if (op == 'F') pushFront(head, x);
        else pushBack(head, x);
    }
    print(head);
    return 0;
}

Input:

3
10 20 30
2
F 5
B 40

Output:

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

The next trap: pushBack on an empty list

Input (empty list, then B 7):

Segmentation fault

head is nullptr, so cur is nullptr, and cur->next reads a field at address 0. A segmentation fault means the program touched memory it does not own, and the operating system stopped it.

Fix 2: the empty list first

If head is nullptr, the new box is the whole list. Now main can use pushBack for the very first box too.

#include <iostream>
using namespace std;

struct Node {
    int data;                            // the value in this box
    Node* next;                          // where the next box is
};

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

void pushFront(Node*& head, int x) {
    Node* node = new Node{x, head};      // new box points at the old first
    head = node;                         // it is the new first box
}

void pushBack(Node*& head, int x) {
    Node* node = new Node{x, nullptr};
    if (head == nullptr) {               // empty list: it is the first box
        head = node;
        return;
    }
    Node* cur = head;
    while (cur->next != nullptr)         // walk to the last box
        cur = cur->next;
    cur->next = node;
}

int main() {
    int n, q;
    cin >> n;
    Node* head = nullptr;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        pushBack(head, x);
    }
    cin >> q;
    while (q--) {                        // F x = front, B x = back
        char op;
        int x;
        cin >> op >> x;
        if (op == 'F') pushFront(head, x);
        else pushBack(head, x);
    }
    print(head);
    return 0;
}

Input: empty, B 7:

7 -> NULL

Input: empty, B 7, F 3:

3 -> 7 -> NULL

Input: 10 20 30, F 5, B 40:

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

Input: empty, no commands:

NULL

Complexity. pushFront: O(1), two pointer changes however long the list is. pushBack as written: O(n), it walks the whole list. With a tail pointer (Q1, and the mini project) it is O(1) too. Extra space: O(1) per insert (one node).

Q3: Delete the first box with value x, then free the list

Problem. Build a list from n numbers, read x, delete the first box holding x, print removed or not found, the list, and how many boxes are still alive (made with new and not yet deleted, counted with a global alive).

List, x Output
10 20 30 40, 30 removed, 10 -> 20 -> 40 -> NULL
10 20 30 40, 10 (the head) removed, 20 -> 30 -> 40 -> NULL
10 20 30 40, 99 not found, the list unchanged
empty, 5 not found, NULL

Think out loud. To unlink a box we need the box before it: prev->next = gone->next, then delete gone. Edge cases: x is the head (no box before it), x is missing, the empty list, x is the last box.

The obvious attempt: look for the box before x

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* next;
};
int alive = 0;                           // boxes made and not yet freed

void pushBack(Node*& head, int x) {
    Node* node = new Node{x, nullptr};
    alive++;
    if (head == nullptr) { head = node; return; }
    Node* cur = head;
    while (cur->next != nullptr) cur = cur->next;
    cur->next = node;
}

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

bool removeValue(Node*& head, int x) {
    Node* cur = head;
    while (cur->next->data != x)         // find the box BEFORE x
        cur = cur->next;
    Node* gone = cur->next;
    cur->next = gone->next;              // link around it
    delete gone;                         // give its memory back
    alive--;
    return true;
}

int main() {
    int n, x;
    cin >> n;
    Node* head = nullptr;
    for (int i = 0; i < n; i++) {
        int v;
        cin >> v;
        pushBack(head, v);
    }
    cin >> x;
    cout << (removeValue(head, x) ? "removed\n" : "not found\n");
    print(head);
    cout << "boxes still alive: " << alive << "\n";
    return 0;
}

Input: 10 20 30 40, x = 30:

removed
10 -> 20 -> 40 -> NULL
boxes still alive: 3

Input: x = 10 (the head):

Segmentation fault

Input: x = 99 (missing):

Segmentation fault

Why it fails

The loop checks cur->next->data, so it never checks the head itself. For 10 it walks to 40, whose next is nullptr, and reads nullptr->data: crash. A missing value walks off the end the same way. (An empty list would crash even sooner: cur itself is nullptr.)

Fix: the head case first, then a loop that stops at the end

  • If head->data == x, there is no box before it: move head to the next box and delete the old one.
  • Walk only while cur->next != nullptr && cur->next->data != x. The order matters: && stops at the first false (short-circuit evaluation), so nullptr->data is never read. If we reach the end, return false.
#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* next;
};
int alive = 0;                           // boxes made and not yet freed

void pushBack(Node*& head, int x) {
    Node* node = new Node{x, nullptr};
    alive++;
    if (head == nullptr) { head = node; return; }
    Node* cur = head;
    while (cur->next != nullptr) cur = cur->next;
    cur->next = node;
}

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

bool removeValue(Node*& head, int x) {
    if (head == nullptr) return false;   // empty list
    if (head->data == x) {               // x is the first box
        Node* gone = head;
        head = head->next;
        delete gone;
        alive--;
        return true;
    }
    Node* cur = head;
    while (cur->next != nullptr && cur->next->data != x)
        cur = cur->next;
    if (cur->next == nullptr) return false;   // not in the list
    Node* gone = cur->next;
    cur->next = gone->next;              // link around it
    delete gone;
    alive--;
    return true;
}

int main() {
    int n, x;
    cin >> n;
    Node* head = nullptr;
    for (int i = 0; i < n; i++) {
        int v;
        cin >> v;
        pushBack(head, v);
    }
    cin >> x;
    cout << (removeValue(head, x) ? "removed\n" : "not found\n");
    print(head);
    cout << "boxes still alive: " << alive << "\n";
    return 0;
}

Input: x = 10 (the head):

removed
20 -> 30 -> 40 -> NULL
boxes still alive: 3

Input: x = 99:

not found
10 -> 20 -> 30 -> 40 -> NULL
boxes still alive: 4

Input: empty list, x = 5:

not found
NULL
boxes still alive: 0

Input: x = 40 (the last box):

removed
10 -> 20 -> 30 -> NULL
boxes still alive: 3

Every case is right, but the last line says boxes still alive: 3: the program ended without deleting them.

Memory leaks, and freeing a list the right way

A memory leak is memory made with new that is never given back with delete. When main ends, the operating system takes the memory back, so a short program gets away with it. A server that runs for weeks does not: leak a few nodes on every request and it keeps growing until it runs out of memory.

The obvious way to free a list is wrong:

// ✗ use-after-free: reads cur->next from a box that was just deleted
for (Node* cur = head; cur != nullptr; cur = cur->next)
    delete cur;

After delete cur, the box no longer belongs to us, and cur = cur->next reads it. That is use-after-free, undefined behaviour: it may even seem to work today, which is what makes it dangerous. The right way is the treasure hunt: read the next place first.

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* next;
};
int alive = 0;                           // boxes made and not yet freed

void pushBack(Node*& head, int x) {
    Node* node = new Node{x, nullptr};
    alive++;
    if (head == nullptr) { head = node; return; }
    Node* cur = head;
    while (cur->next != nullptr) cur = cur->next;
    cur->next = node;
}

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

bool removeValue(Node*& head, int x) {
    if (head == nullptr) return false;   // empty list
    if (head->data == x) {               // x is the first box
        Node* gone = head;
        head = head->next;
        delete gone;
        alive--;
        return true;
    }
    Node* cur = head;
    while (cur->next != nullptr && cur->next->data != x)
        cur = cur->next;
    if (cur->next == nullptr) return false;   // not in the list
    Node* gone = cur->next;
    cur->next = gone->next;              // link around it
    delete gone;
    alive--;
    return true;
}

void freeList(Node*& head) {
    while (head != nullptr) {
        Node* nxt = head->next;          // save the next address FIRST
        delete head;
        alive--;
        head = nxt;
    }
}

int main() {
    int n, x;
    cin >> n;
    Node* head = nullptr;
    for (int i = 0; i < n; i++) {
        int v;
        cin >> v;
        pushBack(head, v);
    }
    cin >> x;
    cout << (removeValue(head, x) ? "removed\n" : "not found\n");
    print(head);
    freeList(head);                      // the game is over: collect every box
    cout << "boxes still alive: " << alive << "\n";
    return 0;
}

Input: x = 30:

removed
10 -> 20 -> 40 -> NULL
boxes still alive: 0

boxes still alive: 0. Every new has its delete, and head ends as nullptr, so nobody can use the old boxes by mistake.

Complexity. Delete by value: O(n) to find the box, O(1) to unlink it. freeList: O(n) time, O(1) extra space.

Complexity summary: linked list vs vector

Operation Linked list vector
insert at the front O(1) O(n): everyone shifts
insert at the back O(n), O(1) with a tail pointer O(1) amortised
insert after a box you already hold O(1) O(n) shift
delete a value O(n) to find + O(1) to unlink O(n) to find + O(n) to shift
the k-th element O(n): walk O(1): v[k]
memory per value the value + one pointer the value only (plus spare capacity)
speed in practice boxes scattered in memory: slower to walk side by side: very cache-friendly

A list wins when you insert and delete at places you already hold (the front, a node you found). A vector wins for v[k] and for raw speed. In C++ code you would normally use std::list or std::forward_list instead of writing your own; interviews ask you to write it to see that you understand pointers.

Common mistakes (and the real results)

Mistake What you see Why Fix
head = head->next to print no error: the 2nd print is only NULL the only address is lost walk with cur
pushFront(Node* head, int x) no error: 5 vanishes changes a copy of head Node*& head, or return the new head
pushBack on an empty list Segmentation fault nullptr->next if (head == nullptr) { head = node; return; }
while (cur->next->data != x) Segmentation fault for the head and for a missing value head never checked; walks off the end head case + cur->next != nullptr &&
cur->next->data != x && cur->next != nullptr Segmentation fault && checks left to right: the null check comes too late null check first
unlinking without delete boxes still alive grows memory leak delete gone;
delete cur; cur = cur->next; undefined behaviour (may even look fine) use-after-free save next first
delete the same node twice free(): double free detected (abort) two pointers to one box delete each box once; set pointers to nullptr
Node n{x, nullptr}; tail->next = &n; in a loop garbage or a loop n is a local: it dies at the end of each iteration new Node{...}

Mini project: a music playlist

A Playlist class with head, tail and count: add a song at the front or the back in O(1), delete a song by title (head, middle, last, missing), show the list, and a destructor that frees every song when the playlist dies. Commands: F title, B title, D title.

#include <iostream>
#include <string>
using namespace std;

struct Song {
    string title;
    Song* next;
};

class Playlist {
    Song* head = nullptr;
    Song* tail = nullptr;                // O(1) add at the end
    int count = 0;
public:
    void addFront(const string& t) {
        head = new Song{t, head};
        if (tail == nullptr) tail = head;
        count++;
    }
    void addBack(const string& t) {
        Song* s = new Song{t, nullptr};
        if (head == nullptr) head = tail = s;
        else { tail->next = s; tail = s; }
        count++;
    }
    bool remove(const string& t) {
        Song* prev = nullptr;
        Song* cur = head;
        while (cur != nullptr && cur->title != t) { prev = cur; cur = cur->next; }
        if (cur == nullptr) return false;           // not found
        if (prev == nullptr) head = cur->next;      // it was the first
        else prev->next = cur->next;
        if (cur == tail) tail = prev;               // it was the last
        delete cur;
        count--;
        return true;
    }
    void show() const {
        cout << "[" << count << "] ";
        for (Song* s = head; s != nullptr; s = s->next)
            cout << s->title << (s->next ? " > " : "");
        cout << "\n";
    }
    ~Playlist() {                        // free every song when the playlist dies
        while (head != nullptr) {
            Song* nxt = head->next;
            delete head;
            head = nxt;
        }
    }
};

int main() {
    Playlist p;
    string cmd, t;
    while (cin >> cmd >> t) {            // F title, B title, D title
        if (cmd == "F") p.addFront(t);
        else if (cmd == "B") p.addBack(t);
        else if (cmd == "D" && !p.remove(t)) cout << t << ": not found\n";
        p.show();
    }
    return 0;
}

Input:

B Kesariya
B Tum_Hi_Ho
F Chaiyya_Chaiyya
D Kesariya
B Ilahi
D Lag_Ja_Gale

Output:

[1] Kesariya
[2] Kesariya > Tum_Hi_Ho
[3] Chaiyya_Chaiyya > Kesariya > Tum_Hi_Ho
[2] Chaiyya_Chaiyya > Tum_Hi_Ho
[3] Chaiyya_Chaiyya > Tum_Hi_Ho > Ilahi
Lag_Ja_Gale: not found
[3] Chaiyya_Chaiyya > Tum_Hi_Ho > Ilahi

Deleting the last song must also move tail back (if (cur == tail) tail = prev;), or the next addBack would link a song after a deleted box.

Practice questions (with solutions)

1. Your turn: insert at position k. insertAt(head, k, x) puts x so that it becomes box number k (0 = the front). If k is past the end, put it at the back.

Solution

k = 0 (or an empty list) changes head, so take it by reference. Otherwise walk k − 1 steps to the box before position k, stopping early at the last box, and link the new box after it.

#include <iostream>
using namespace std;

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

void pushBack(Node*& head, int x) {
    Node* node = new Node{x, nullptr};
    if (head == nullptr) { head = node; return; }
    Node* cur = head;
    while (cur->next != nullptr) cur = cur->next;
    cur->next = node;
}

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

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

void insertAt(Node*& head, int k, int x) {
    if (k <= 0 || head == nullptr) {     // the new first box
        head = new Node{x, head};
        return;
    }
    Node* cur = head;
    for (int i = 0; i < k - 1 && cur->next != nullptr; i++)
        cur = cur->next;                 // the box BEFORE position k
    cur->next = new Node{x, cur->next};  // link it in after cur
}

int main() {
    int n, q;
    cin >> n;
    Node* head = nullptr;
    for (int i = 0; i < n; i++) {
        int v;
        cin >> v;
        pushBack(head, v);
    }
    cin >> q;
    while (q--) {
        int k, x;
        cin >> k >> x;
        insertAt(head, k, x);
        print(head);
    }
    freeList(head);
    return 0;
}

Input: 10 20 30, then (k, x) = (1, 15), (0, 5), (99, 40):

10 -> 15 -> 20 -> 30 -> NULL
5 -> 10 -> 15 -> 20 -> 30 -> NULL
5 -> 10 -> 15 -> 20 -> 30 -> 40 -> NULL

Time O(k), space O(1).

2. Count the nodes and the sum of all values.

Solution
#include <iostream>
using namespace std;

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

void pushBack(Node*& head, int x) {
    Node* node = new Node{x, nullptr};
    if (head == nullptr) { head = node; return; }
    Node* cur = head;
    while (cur->next != nullptr) cur = cur->next;
    cur->next = node;
}

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

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

int main() {
    int n;
    cin >> n;
    Node* head = nullptr;
    for (int i = 0; i < n; i++) {
        int v;
        cin >> v;
        pushBack(head, v);
    }
    int count = 0;
    long long sum = 0;                   // long long: many big values
    for (Node* cur = head; cur != nullptr; cur = cur->next) {
        count++;
        sum += cur->data;
    }
    cout << "count = " << count << ", sum = " << sum << "\n";
    freeList(head);
    return 0;
}

Input:

5
10 20 30 40 50

Output:

count = 5, sum = 150

Input 0:

count = 0, sum = 0

3. Delete EVERY box holding x.

Solution

First remove x from the front as many times as needed (the head may change several times). Then, when cur->next holds x, unlink it and do not move cur: the new cur->next may be x again.

#include <iostream>
using namespace std;

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

void pushBack(Node*& head, int x) {
    Node* node = new Node{x, nullptr};
    if (head == nullptr) { head = node; return; }
    Node* cur = head;
    while (cur->next != nullptr) cur = cur->next;
    cur->next = node;
}

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

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

int removeAll(Node*& head, int x) {
    int removed = 0;
    while (head != nullptr && head->data == x) {   // x at the front, maybe many
        Node* gone = head;
        head = head->next;
        delete gone;
        removed++;
    }
    Node* cur = head;
    while (cur != nullptr && cur->next != nullptr) {
        if (cur->next->data == x) {      // remove it, and DON'T move cur
            Node* gone = cur->next;
            cur->next = gone->next;
            delete gone;
            removed++;
        } else {
            cur = cur->next;
        }
    }
    return removed;
}

int main() {
    int n, x;
    cin >> n;
    Node* head = nullptr;
    for (int i = 0; i < n; i++) {
        int v;
        cin >> v;
        pushBack(head, v);
    }
    cin >> x;
    cout << "removed " << removeAll(head, x) << "\n";
    print(head);
    freeList(head);
    return 0;
}

Input: 5 5 10 5 5 20 5, x = 5:

removed 5
10 -> 20 -> NULL

Input: 5 5 5, x = 5:

removed 3
NULL

Time O(n), space O(1).

4. Build a list in reverse order using only pushFront.

Solution

Each new value goes in front of the previous ones, so the list comes out reversed, and every insert is O(1).

#include <iostream>
using namespace std;

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

void pushFront(Node*& head, int x) {
    head = new Node{x, head};            // O(1): no walking at all
}

int main() {
    int n;
    cin >> n;
    Node* head = nullptr;
    for (int i = 0; i < n; i++) {
        int v;
        cin >> v;
        pushFront(head, v);
    }
    for (Node* cur = head; cur != nullptr; cur = cur->next)
        cout << cur->data << " -> ";
    cout << "NULL\n";
    while (head != nullptr) {
        Node* nxt = head->next;
        delete head;
        head = nxt;
    }
    return 0;
}

Input:

4
10 20 30 40

Output:

40 -> 30 -> 20 -> 10 -> NULL

Quick quiz

1. What does it print? (the episode quiz)

#include <iostream>
using namespace std;

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

int main() {
    Node* c = new Node{3, nullptr};
    Node* b = new Node{2, c};
    Node* a = new Node{1, b};
    a->next = c;
    for (Node* p = a; p != nullptr; p = p->next)
        cout << p->data;
    cout << "\n";
    delete a; delete b; delete c;        // b is freed here only because we still have its name
    return 0;
}

(A) 123 (B) 13 (C) 1 (D) 321

Answer

(B) 13. a->next = c links 1 straight to 3, around 2: exactly how delete-by-value works. In the video's version nobody deletes b; once no pointer leads to it, that is a memory leak. (This version deletes it only because the name b still exists.)

Output:

13

2. What does it print?

#include <iostream>
using namespace std;

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

void addFront(Node* head, int x) {
    head = new Node{x, head};
}

int main() {
    Node* head = new Node{1, new Node{2, nullptr}};
    addFront(head, 0);
    for (Node* p = head; p != nullptr; p = p->next)
        cout << p->data << " ";
    cout << "\n";
    return 0;
}

(A) 0 1 2 (B) 1 2 (C) 0 (D) compile error

Answer

(B) 1 2. addFront takes the pointer by value and changes only its copy; the new box (0) is leaked.

Output:

1 2 

3. The Q3 obvious attempt (while (cur->next->data != x)) with an empty list: what happens?

Answer

It crashes even sooner: cur is nullptr, and cur->next is read on the very first check.

Input: empty list, x = 5:

Segmentation fault

4. Which operations are O(1) on a singly linked list with a head and a tail pointer: insert at the front, insert at the back, delete the last box?

Answer

Insert at the front and insert at the back are O(1). Deleting the last box is O(n): to update tail you need the box before it, and a singly linked list can only walk forwards. (A doubly linked list, with a prev pointer in every node, makes it O(1).)

Interview questions

  1. What is a linked list? A sequence of nodes, each holding a value and a pointer to the next node; the last node points to nullptr, and head points to the first.
  2. Linked list vs array/vector? List: O(1) insert/delete at a known place, no shifting, but O(n) access to the k-th element and an extra pointer per node. Vector: O(1) v[k], cache-friendly, but O(n) to insert at the front.
  3. Why does void pushFront(Node* head, int x) not change the list? The pointer is passed by value; the function changes its copy. Use Node*& head (or Node** head in C), or return the new head.
  4. How do you insert at the tail in O(1)? Keep a tail pointer and update it on every insert (and when the last node is deleted).
  5. What edge cases do you check in every linked-list function? The empty list, a list of one node, the head, the last node, a value that is missing.
  6. Why must the null check come first in while (cur->next != nullptr && cur->next->data != x)? && evaluates left to right and stops at the first false; reversed, it reads nullptr->data.
  7. How do you delete a node by value? Handle the head separately; otherwise find the node before it, set prev->next = gone->next, then delete gone.
  8. What is a memory leak? Memory allocated with new that is never freed with delete; in a long-running program it keeps growing.
  9. What is use-after-free? Reading or writing memory after delete; undefined behaviour. When freeing a list, save next before delete.
  10. How would you avoid manual delete in modern C++? Use std::list / std::forward_list, or own nodes with std::unique_ptr<Node> next (beware: a very long chain of unique_ptrs is destroyed recursively, which can overflow the stack).
  11. Can you delete a node when you are given only a pointer to it (not the head)? If it is not the last node: copy the next node's data into it and delete the next node instead. It fails for the last node.
  12. What does a segmentation fault mean? The program accessed memory it does not own (often a nullptr or a deleted pointer), and the operating system stopped it.

Glossary

Term Meaning Example
Linked list Values in separate nodes, each pointing to the next 10 -> 20 -> 30 -> NULL
Node One box of the list: a value and a pointer struct Node { int data; Node* next; };
data The value stored in a node 10
next A pointer to the next node, nullptr at the end node->next
head A pointer to the first node: the only way into the list Node* head
tail The last node, or a pointer kept to it tail->next = node
nullptr The null pointer: points to nothing an empty list: head == nullptr
Pointer A variable that holds a memory address Node* cur
-> Follow a pointer and use a member cur->data = (*cur).data
Heap Memory you ask for with new; it lives until you delete it new Node{x, nullptr}
new / delete Make an object on the heap / give its memory back delete gone;
Traversal Walking a list from head to the end for (Node* cur = head; cur; cur = cur->next)
Pass by value The function gets a copy of the argument void f(Node* head)
Reference Another name for an existing variable Node*& head
Reference to a pointer Lets a function change the caller's pointer void pushFront(Node*& head, int x)
Segmentation fault The program touched memory it does not own; the OS stops it nullptr->next
Short-circuit evaluation && stops at the first false, \|\| at the first true cur->next != nullptr && cur->next->data != x
Unlink Make the previous node point past a node prev->next = gone->next
Memory leak Memory made with new and never deleted boxes still alive: 3
Use-after-free Using memory after it was deleted: undefined behaviour delete cur; cur = cur->next;
Double free Deleting the same memory twice free(): double free detected
Undefined behaviour (UB) Code the C++ standard gives no meaning to; anything can happen reading a deleted node
Destructor A member function that runs by itself when an object dies ~Playlist()
O(1) / O(n) Constant time / time that grows with the list length insert at front / insert at back without a tail
Amortised O(1) O(1) on average over many operations, even if one is slow vector::push_back
std::list / std::forward_list The standard library's doubly / singly linked lists std::list<int> l;

Summary

  • A node is data + next; head points to the first node, and an empty list is head == nullptr.
  • Walk with cur, never with head, or the list is lost.
  • A function that may change the first node takes Node*& head (or returns the new head). Node* head is only a copy.
  • Check the empty list first: pushBack on nullptr is a segmentation fault.
  • Delete by value: the head case first, then find the node before x with cur->next != nullptr && cur->next->data != x, unlink, delete.
  • Free a list by saving next before delete. Every new needs exactly one delete; deleting first and reading next after is use-after-free.

Next episode: Linked list questions II: reverse a list, find the middle with slow and fast pointers, and detect a cycle with Floyd's algorithm.