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
nextisnullptr. Keeping atailpointer 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 withdelete. Everynewneeds exactly onedelete.->follows a pointer:cur->datais thedataof the boxcurpoints 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; whenmainreturns, 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: moveheadto the next box and delete the old one. - Walk only while
cur->next != nullptr && cur->next->data != x. The order matters:&&stops at the firstfalse(short-circuit evaluation), sonullptr->datais never read. If we reach the end, returnfalse.
#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
- 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, andheadpoints to the first. - 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. - Why does
void pushFront(Node* head, int x)not change the list? The pointer is passed by value; the function changes its copy. UseNode*& head(orNode** headin C), or return the new head. - How do you insert at the tail in O(1)? Keep a
tailpointer and update it on every insert (and when the last node is deleted). - 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.
- Why must the null check come first in
while (cur->next != nullptr && cur->next->data != x)?&&evaluates left to right and stops at the firstfalse; reversed, it readsnullptr->data. - How do you delete a node by value? Handle the head separately; otherwise find the node before it, set
prev->next = gone->next, thendelete gone. - What is a memory leak? Memory allocated with
newthat is never freed withdelete; in a long-running program it keeps growing. - What is use-after-free? Reading or writing memory after
delete; undefined behaviour. When freeing a list, savenextbeforedelete. - How would you avoid manual
deletein modern C++? Usestd::list/std::forward_list, or own nodes withstd::unique_ptr<Node> next(beware: a very long chain ofunique_ptrs is destroyed recursively, which can overflow the stack). - 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.
- What does a segmentation fault mean? The program accessed memory it does not own (often a
nullptror 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 ishead == nullptr. - Walk with
cur, never withhead, or the list is lost. - A function that may change the first node takes
Node*& head(or returns the new head).Node* headis only a copy. - Check the empty list first:
pushBackonnullptris 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
nextbeforedelete. Everynewneeds exactly onedelete; deleting first and readingnextafter 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.