Insert, delete and memory care

Why it matters

Insertion and deletion are the reason linked lists exist. An array must shift its items to make room for a new one. A linked list only changes a few pointers. That sounds simple, and it is, but most bugs in list code happen in these few lines. A pointer is changed in the wrong order, a node is freed too early, or a node is lost because nothing points to it any more. Interviewers ask for these operations because they reveal whether you can keep track of pointers under pressure.

In this lesson you will learn the three pointer changes that every insert and delete uses. You will learn why you must find the node before the target, not the target itself. You will learn how a tail pointer makes appends cheap, and how a dummy head node removes special cases. Finally you will learn how to free memory so that every node is deleted exactly once. Every example runs and prints the output shown.

Changing a pointer is changing a link

Lesson 1 said that each next pointer is a link. Inserting or deleting is nothing more than changing links. A link is just a value stored inside a node, so you change it with an assignment like any other variable.

Think of a line of people holding hands. Person A holds the hand of person B. If a new person C wants to stand between them, A must let go of B and grab C, and C must grab B. The order matters. If A lets go of B before C has grabbed B, B is lost, and nobody can reach B again.

Linked list code follows the same rule. When you insert a node between prev and next, you first set the new node's next to point to next. Only then do you set prev->next to the new node. If you reverse those two steps, the new node points to itself, and the old next is lost. The pictures in this lesson show the right order.

Here is the general rule you will apply in every example in this lesson. Set the new link first. Then break the old link. Free memory last.

Insert at the front

Inserting at the front is the easiest case. You create a new node, point its next at the current head, and move the head to the new node. There is no walk, so the cost is O(1).

Here is the function. It takes the head by reference, because it must change the head itself.

void insertHead(Node*& head, int value) {
    Node* node = new Node(value);
    node->next = head;   // step 1: new node points at the old head
    head = node;         // step 2: head now points at the new node
}

Trace it on a list that holds 2 and 3, inserting 1. Before the call, head is node 2, and node 2's next is node 3. The new line creates node 1, with next set to nullptr by the constructor. Step 1 sets node 1's next to node 2. Step 2 sets head to node 1. Now the chain is head, node 1, node 2, node 3. Nothing was copied and nothing was shifted. The 2 and 3 nodes did not move in memory.

The picture below shows the state before and after the call. The first row is the old list starting at 20. The second row is the list after the new node 10 is placed in front.

Two rows: a list starting at 20 before the insert, and the list starting at the new node 10 after it

If you call insertHead on an empty list, head is nullptr. Step 1 sets the new node's next to nullptr, which is already true, and step 2 makes the new node the only node. The empty case needs no special code. This is one of the reasons insertion at the front is the first operation most people learn.

Insert at a position

To insert at index i, the new node must sit between the node at index i minus 1 and the node at index i. The node at index i minus 1 is called the predecessor. Its next is the link you must change. So the walk stops one node early, at the predecessor, not at the target.

This is the most useful pattern in the module. Whenever you insert or delete, ask: which node's next must change? That node is the one you need to hold.

// Insert so the new node has index i (0 means the front).
// Returns false if i is larger than the list allows.
bool insertAt(Node*& head, int i, int value) {
    if (i == 0) {
        insertHead(head, value);
        return true;
    }
    Node* prev = head;
    for (int k = 0; k < i - 1 && prev != nullptr; k++) {
        prev = prev->next;
    }
    if (prev == nullptr) return false;
    Node* node = new Node(value);
    node->next = prev->next;   // step 1: new node points at the old successor
    prev->next = node;         // step 2: predecessor points at the new node
    return true;
}

Walk through insertAt(head, 2, 99) on the list 1, 2, 3. The index is 2, so the loop runs i - 1 times, which is once. It moves prev from node 1 to node 2. Node 2 is the predecessor of index 2. Now node->next = prev->next makes the new node point at node 3, which was node 2's old next. Then prev->next = node makes node 2 point at 99. The list is 1, 2, 99, 3. Node 3 is still in memory and reachable through the new node.

Now try insertAt(head, 10, 7) on the same four-node list. The loop moves prev forward until it reaches the last node, then becomes nullptr. The check prev == nullptr catches it. The function returns false and changes nothing. Nothing was allocated, so nothing leaked. Check the failure path before the allocation, as this code does, and you never have to free a node you did not use.

Notice the loop condition k < i - 1. For index 1, the loop runs zero times, so prev is the head. That is correct: the head is the predecessor of index 1. Many off-by-one bugs come from getting this number wrong. When you write a loop like this, test index 1 by hand.

Summary of the pointer changes

Before you write any insert or delete, fill in this table on paper. It names the node you must hold, the links that change, and the memory that is freed. Each row matches one of the functions above.

If a row needs a node you do not hold, the operation costs a walk. That is the reason for the predecessor pattern, and for the tail pointer that removes the walk from appends.

Here is a runnable program that puts both insert functions to work. It builds a list at the front, inserts in the middle, and then tries an index that is too large.

1 2 3
1 2 99 3
0
1 2 99 3

The first three lines build the list with the front insert, so each new value becomes the head. insertAt(head, 2, 99) puts 99 at index 2, after the 2. The call with index 10 fails and returns false. Because cout prints a bool as 0 or 1 by default, the line shows 0, and the list does not change.

Delete a node by value

Deleting uses the same idea, with one more step. You find the node before the target, call it prev. Then you point prev->next at the target's successor, and free the target. The picture below shows the bypass.

A three node list with the middle node highlighted as the target, and a bypass arrow from its predecessor to the node after it

The one place where you cannot use a predecessor is the head. There is no node before the head, so the head needs its own branch. Here is the function.

void removeFirst(Node*& head, int value) {
    if (head == nullptr) return;
 
    if (head->data == value) {
        Node* old = head;      // save the node we will free
        head = head->next;     // move head past it
        delete old;            // free only the saved pointer
        return;
    }
 
    Node* prev = head;
    while (prev->next != nullptr && prev->next->data != value) {
        prev = prev->next;
    }
    if (prev->next == nullptr) return;   // value not found
 
    Node* target = prev->next;
    prev->next = target->next;           // bypass the target
    delete target;                       // free it
}

The head branch saves old before moving head, then deletes old. The order matters. If you wrote delete head; head = head->next;, you would read head->next from memory that was already freed. Lesson 1 called this out as a bug, and it appears again in every delete.

The general branch stops when prev->next holds the value. It then saves the target in target, bypasses it, and deletes it. The target pointer is still valid after the bypass, because the bypass changed prev->next, not the target node. The target's own next still points at the rest of the list, but we no longer reach the target from the list.

Trace removeFirst(head, 1) on 5, 1, 4, 1, 6. The head is 5, which is not 1, so we walk. prev starts at node 5. Its next holds 1, so the loop stops. target is the first 1. prev->next becomes node 4, and the first 1 is freed. The list is 5, 4, 1, 6. Only the first match was removed. The second 1 is still there, because this function removes one node.

Here is the runnable program. It builds a list from a vector, then removes three values and prints the list after each call.

5 1 4 1 6
5 4 1 6
4 1 6
4 1 6

Read the last two lines carefully. The call with value 42 does not exist in the list, so the function walks to the end, sees that prev->next is nullptr, and returns. Nothing changes. That case is easy to forget, and forgetting it leads to a null dereference when the code tries target->next.

Insert in sorted order, traced

Keeping a list sorted is a common job, such as a leaderboard that stays in score order. The rule is simple. Walk until the next node holds a larger value than the new one, then insert between the current node and that next node. The walk needs the predecessor for the same reason as before, so the walk stops one node early. A dummy head makes the rule work when the new value is smaller than every node.

Trace the insertion of 5 into the sorted list 1, 4, 6, 8. Start with prev on the dummy, so the dummy is the predecessor of node 1. The table shows each check.

The new node 5 takes the place after prev. Its next is set to the old prev->next, which is node 6, and then prev->next is set to node 5. The list is 1, 4, 5, 6, 8. Both link changes follow the set new link first rule from earlier in this lesson.

Now insert 0 into the same list. Step 1 checks node 1, which is 1, and 1 is not smaller than 0. The walk stops at once, with prev still on the dummy. The new node goes after the dummy, which makes it the new first node, and the function returns dummy.next. Without the dummy, this case would need its own branch that changes the head, which is the special case the dummy removes.

The insertion takes O(n) time, because the walk may pass every node, and O(1) extra space. A sorted array would find the spot with a binary search, in O(log n), but then the insertion itself would shift items, which is O(n). The list does the insertion in O(1) once the spot is found, and the walk is what costs time.

A worked failure: the wrong order of pointer changes

It helps to see the wrong order fail, step by step, before you rely on the right one. The list is 1, 2, 3. The head pointer holds node 1, and prev holds node 2. The new node holds 9. Here is the insertion written with the two link changes in the wrong order.

Node* node = new Node(9);
prev->next = node;         // step A: node 2 now points at 9
node->next = prev->next;   // step B: reads node 9 itself and stores it in node 9's own next

Trace step A. Before it, the links run 1 to 2 to 3 to nullptr. After it, node 2's next is node 9. The link from node 2 to node 3 is gone. Node 3 still sits in memory, with its own next still set, but no pointer in the list reaches it. It is lost, and nothing will free it, so it is also a leak.

Trace step B. The right-hand side reads prev->next, which is now node 9, not node 3. So node 9's next is set to node 9. The node points at itself. A walk from the head now gives 1, 2, 9, 9, 9 and so on forever.

The fix is to swap the two lines. Set node->next = prev->next first, which makes node 9 point at node 3, and only then set prev->next = node. The walk becomes 1, 2, 9, 3 and then nullptr, which is the correct answer.

The wrong version does not crash inside the insert. The damage shows later, when a walk runs forever or a free reaches memory it should not touch. That delay is why this bug is hard to find. Print the list right after each insert while you learn, and the wrong count or the endless output shows up at once.

Insert and delete at the tail

A tail pointer is a second pointer that always points at the last node. With it, adding to the end costs O(1), because you can reach the last node without a walk. The price is that you must update the tail whenever the last node changes. Those updates are where most bugs live.

The rule has three cases. An empty list needs both head and tail to point at the new node. A non-empty list needs tail->next to point at the new node, and then tail moves to it. Removing the last node needs the tail to move back to the node before, which is the predecessor again. Removing from the front needs the tail to become nullptr if the list becomes empty.

Hold a queue in your mind as you read this. A queue is a line of people. New people join at the back and leave from the front. A singly linked list with a head and tail pointer is the simplest queue you can build. The visualizer below shows the same join-at-back, leave-at-front pattern.

Watch the arrival at the back. The new item joins after the last one, and the item that leaves always comes from the front. This is exactly what the pushBack and popFront functions in the next program do with a head and a tail pointer.

size 3
popped 10
got 20
got 30
got 40
head null: 1, tail null: 1

Trace the middle part of this program. After three pushBack calls the list is 10, 20, 30, the head is node 10, the tail is node 30, and size is 3. popFront removes 10: it saves the old head, reads its value, moves head to node 20, and deletes node 10. The tail is still node 30, which is correct because the list is not empty. pushBack(40) links node 30 to node 40 and moves the tail there.

The final loop removes 20, 30 and 40 in order. When 40 is removed, head becomes nullptr, so the if (head == nullptr) tail = nullptr; line runs. Without that line, tail would still point at the deleted node 40. The next pushBack would write tail->next into freed memory, which is a serious bug. This is the most common tail bug, and the test head null, tail null at the end of the output checks it.

The List struct's size field is updated by the same functions that change the links. That keeps the count correct without a walk. The downside is that any code that changes the links without updating size makes the count wrong. Keep all changes inside the methods.

Removing the last node

Removing the last node is harder than it looks, because you need the node before the last one. A tail pointer tells you where the last node is, but a singly linked list has no prev pointer, so it cannot tell you the node before the tail. You must walk from the head and stop one node early. That walk is why removing the last node costs O(n), even when you keep a tail.

void removeLast(Node*& head) {
    if (head == nullptr) return;
    if (head->next == nullptr) {         // one node: the list becomes empty
        delete head;
        head = nullptr;
        return;
    }
    Node* prev = head;
    while (prev->next->next != nullptr) {   // stop when prev is the node before the last
        prev = prev->next;
    }
    delete prev->next;                   // the last node
    prev->next = nullptr;                // prev is now the last node
}

Trace it on the list 4, 7, 9. The head is node 4, and its next is not null, so the function goes on. The pointer prev starts on node 4. The loop test looks at prev->next->next, which is node 9. That is not null, so the loop moves prev to node 7. Now the test looks at node 7's next, which is node 9, and then at node 9's next, which is nullptr. The test fails, so the loop stops with prev on node 7. Node 7 is the node before the last one. delete prev->next frees node 9, and prev->next = nullptr makes node 7 the new end. The list is 4, 7.

The case with one node has to be handled first. The loop would read prev->next->next with prev->next equal to nullptr, which is a null dereference. The early branch handles it, and the head becomes nullptr, which is the empty list.

If the list is long, the walk is the expensive part. A doubly linked list fixes this with the prev pointer on the last node. That is one more reason the last module lesson exists.

Memory care: freeing every node once

Every new must be matched by exactly one delete. Forgetting the delete leaks memory. Calling delete twice on the same node is a double free, which corrupts the heap and can crash later, far from the bug. Reading a node after deleting it is a use after free. All three are your responsibility in C++. The language does not collect garbage for you.

The safe way to free a list is to walk it and delete each node, saving the next pointer first. Here is the loop you have seen in lesson 1, now written as a function.

void freeList(Node* head) {
    Node* cur = head;
    while (cur != nullptr) {
        Node* nxt = cur->next;   // save the next pointer first
        delete cur;              // then free the current node
        cur = nxt;               // then move on
    }
}

The order inside the loop is the whole lesson. Save, delete, move. If you wrote delete cur; cur = cur->next;, the second line reads a freed node. The compiler does not warn you, and the program may appear to work until a later change moves memory around.

The cleanest way to make sure a list is freed is to put the freeing code in a destructor. A destructor is a special function that C++ calls automatically when an object goes out of scope. It is named ~List. If List owns the nodes, its destructor frees them, so you cannot forget. The next program shows this. It also counts the nodes freed, so you can see the destructor run.

built 4 nodes
freed 4 nodes
after the block

The braces around List a create a scope. When the closing brace is reached, C++ calls a's destructor before the next line runs. That is why freed 4 nodes appears before after the block. You never call the destructor yourself.

There is one danger here, and it is important. If you copy a List, C++ makes a shallow copy by default: the new object's head holds the same address as the old one. When both objects are destroyed, both destructors try to free the same nodes. That is a double free. For example, List b = a; inside main would print freed 4 nodes twice and crash or corrupt memory at the second destruction. The fix is to delete the copy operations or to write a deep copy. For this module it is enough to know the danger and to avoid copying list objects.

What the destructor order looks like

When a function ends, C++ destroys the local objects in the reverse order of their creation. This matters when a list is one object inside another. If an outer object holds a List member, the list's destructor runs as part of the outer one. Keep the rule simple: whoever creates the nodes must free them, and an object that owns nodes must free them in its destructor.

Local pointers such as cur and nxt have no destructor. Their memory goes away when the function returns, but the node they pointed to stays allocated until someone calls delete on it. The stack holds the pointer, the heap holds the node, and only delete ends the node's life.

Who owns each node

An owner is the part of the code that is responsible for freeing a node. Good list code gives each node exactly one owner, and that owner frees it once. In the examples in this lesson, the list object owns its nodes, and its destructor frees them. When a function receives a node pointer, it borrows the node. It may read the node or change its fields, but it must not delete the node unless the function is the owner.

Three rules follow from this. First, a function that removes a node is the one that deletes it, and no other code may use that node afterwards. Second, a function that returns a node pointer, such as a search, lends the node to the caller. The list still owns it, so the caller must not delete it. Third, a dummy node that you create on the stack owns nothing, because new never made it. Never call delete on it.

The third rule is the one people break. Writing delete &dummy; crashes, because the memory was never created by new. The address sanitizer reports attempting free on address which was not malloc()-ed. Only delete what new created, and only once.

The rules also tell you what to check when a crash appears after a call. Ask which function owns the node that was read, and whether that owner already freed it. Most use after free bugs come from two owners who each believed they were in charge.

Common mistakes and the messages you will see

Here are the mistakes you will meet most often, with the messages they produce so you can recognise them.

The first mistake is an insert that breaks the list because the links were changed in the wrong order. Suppose you write prev->next = node; node->next = prev->next;. The first line sets prev->next to the new node. The second line then sets the new node's next to itself. Everything after prev is lost, and the list stops at the new node. The program does not crash. It just prints fewer items than it should. Symptoms like this are quiet, so print the list after every insert while you are learning.

The second mistake is deleting the head without moving it first. Writing delete head; head = nullptr; loses the rest of the list. Writing delete head; head = head->next; reads freed memory.

The third mistake is a double free. The sanitizer message is:

==23817==ERROR: AddressSanitizer: attempting double-free on 0x602000000010
    #0 0x7f8d in operator delete(void*)
    #1 0x55c2 in main prog.cpp:41

Read the first line. It says you freed the same address twice. The #1 line points at the second delete call in your code, so look at the calls that come before it. A common cause is a destructor running on a copied list, as described above.

The fourth mistake is a use after free, which the sanitizer reports as heap-use-after-free. It names the line where the freed node was read. The cause is almost always a delete followed by a read of the same pointer. Save the value you need before you delete.

The fifth mistake is a leak. Build a list, drop the head, and the nodes can no longer be reached. A normal run may look fine. The sanitizer reports leaks at exit when you compile with -fsanitizer=address, with a line that starts with Direct leak of followed by the number of bytes. Each leak line points at the new call that made the node.

The sixth mistake is a tail that points at a deleted node. The symptom is a crash in pushBack, usually a null or freed address. The fix is the rule from the tail section: when the list becomes empty, set the tail to nullptr too.

A debugging walkthrough

Suppose a teammate says removeFirst does nothing. They call removeFirst(head, 3) on the list 1, 2, 3, and after the call the list still prints 1 2 3. Here is how to find out whether the function or the call is wrong.

First, write the input and expected output on paper. Input list 1, 2, 3. Value 3. Expected output 1, 2.

Second, trace the walk. head is node 1, which is not 3, so we go to the walk. prev is node 1. The check prev->next->data != value compares node 2's data, which is 2, with 3. The check is true, so prev moves to node 2. Now prev->next is node 3, whose data is 3. The check is false, so the loop stops with prev on node 2.

Third, look at the line after the loop: if (prev->next == nullptr) return;. prev->next is node 3, not nullptr, so the function continues. target is node 3. prev->next = target->next makes node 2's next equal to node 3's next, which is nullptr. delete target frees node 3. The list should now be 1, 2. The trace says the function works.

Fourth, suspect the caller. If the output really is unchanged, the most likely cause is that the caller did not pass head by reference. If removeFirst(Node* head, int value) takes the pointer by value, the call still changes prev->next, which is part of the shared list, so the removal still works for non-head targets. But the call removeFirst(head, 1) on a list whose head holds 1 would change only the local copy of head. The caller's head would still point at a freed node. That is the reason the parameter is Node*&.

Fifth, add a print after each call. Printing the list after every operation shows you the state at each point, and it is the fastest way to find which call goes wrong.

Interview patterns for this lesson

Four patterns cover almost every insert and delete question.

The first is find the predecessor. For any change in the middle of a list, stop the walk one node early. The predecessor's next is the only link that changes.

The second is dummy head. Create a fake node in front of the real head, and make the real head its next. Now the head is no different from any other node, so the same code deletes or inserts it. At the end, return dummy.next. This removes the head branch from removeFirst. It is the standard way to write a removal that handles every value, including several copies at the front.

Here is removeAll, which removes every node with a given value, using a dummy head. It stays in one loop, and the head case needs no code.

void removeAll(Node*& head, int value) {
    Node dummy(0);
    dummy.next = head;
    Node* prev = &dummy;
    while (prev->next != nullptr) {
        if (prev->next->data == value) {
            Node* target = prev->next;
            prev->next = target->next;
            delete target;
        } else {
            prev = prev->next;
        }
    }
    head = dummy.next;
}

Notice that prev only moves forward when the next node is kept. After a delete, prev stays where it is, because the new prev->next may also need to be removed. The dummy lives on the stack, so you never delete it. Only the real nodes are on the heap.

The third pattern is tail pointer for O(1) append. Keep a tail, update it in every operation that changes the last node, and you can add to the end without a walk. Interviewers often ask for it right after you write an O(n) append.

The fourth pattern is free exactly once. Whenever you write a delete, ask whether another pointer still uses the node, and whether anything will free it again. A destructor that frees the nodes, plus the rule against copying, answers both questions for a single owner.

When an interviewer asks "How do you delete a node if you only have a pointer to it?", the answer is special. You cannot find its predecessor without a walk. A trick is to copy the next node's data into this node and delete the next node. This works except for the last node, and it breaks if other pointers still point at the next node. Mention those limits when you give the trick.

Practice

Try each exercise yourself before you open the solution. Use the dummy head pattern where it helps.

1. Write int countValue(Node* head, int x) that returns how many nodes hold x. Return 0 for an empty list.

int countValue(Node* head, int x) {
    int n = 0;
    for (Node* cur = head; cur != nullptr; cur = cur->next) {
        if (cur->data == x) n++;
    }
    return n;
}

2. Write void insertSorted(Node*& head, int value) that inserts value into a list already sorted in increasing order, so the list stays sorted. Handle the case where value is smaller than every node.

void insertSorted(Node*& head, int value) {
    Node dummy(0);
    dummy.next = head;
    Node* prev = &dummy;
    while (prev->next != nullptr && prev->next->data < value) {
        prev = prev->next;
    }
    Node* node = new Node(value);
    node->next = prev->next;
    prev->next = node;
    head = dummy.next;
}

3. Write void removeLast(Node*& head) that removes the last node. Do nothing on an empty list. Handle the one-node case.

void removeLast(Node*& head) {
    if (head == nullptr) return;
    if (head->next == nullptr) {
        delete head;
        head = nullptr;
        return;
    }
    Node* prev = head;
    while (prev->next->next != nullptr) {
        prev = prev->next;
    }
    delete prev->next;
    prev->next = nullptr;
}

4. Write Node* insertFront(Node* head, int value) that takes the head by value and returns the new head. Then write the line the caller uses. Explain why this version needs the caller to assign the result.

Node* insertFront(Node* head, int value) {
    Node* node = new Node(value);
    node->next = head;
    return node;
}

5. Write Node* removeNth(Node* head, int n) that removes the node at index n (0 is the head) and returns the new head. Assume n is in range.

Node* removeNth(Node* head, int n) {
    Node dummy(0);
    dummy.next = head;
    Node* prev = &dummy;
    for (int k = 0; k < n; k++) {
        prev = prev->next;
    }
    Node* target = prev->next;
    prev->next = target->next;
    delete target;
    return dummy.next;
}

6. Explain why this code is wrong: void drop(Node* head) { Node* cur = head; while (cur) { delete cur; cur = cur->next; } }.

7. A list has a tail pointer. Describe, step by step, what must change when you delete the last node of a three node list. Then say what must change when you delete the only node.

8. Count how many new and delete calls are needed to build the list 1, 2, 3 and then free it, if you use the pushBack function from this lesson. Give the numbers.

9. Find the bug in this function, and fix it: void insertAfter(Node* node, int value) { Node* n = new Node(value); node->next = n; n->next = node->next; }.

void insertAfter(Node* node, int value) {
    Node* n = new Node(value);
    n->next = node->next;
    node->next = n;
}

10. Write Node* copyList(Node* head) that makes a new list with the same values in the same order and returns its head. Do not share nodes between the two lists.

Node* copyList(Node* head) {
    Node dummy(0);
    Node* tail = &dummy;
    for (Node* cur = head; cur != nullptr; cur = cur->next) {
        tail->next = new Node(cur->data);
        tail = tail->next;
    }
    return dummy.next;
}

What you now know

• Inserting and deleting change links. Set the new link first, then break the old one, then free memory.
• To insert or delete at index i, walk to the predecessor, the node at index i minus 1, because its next is the link that changes.
• Removing the head needs its own branch, unless you use a dummy head node in front of it.
• A tail pointer makes append O(1). Update the tail whenever the last node changes, including when the list becomes empty.
• Free each node exactly once. Save next before delete, and let a destructor free an owned list.
• The common bugs are a wrong order of link changes, a double free, a use after free, a leak and a stale tail. The sanitizer names each one.

The next lesson uses these pointer changes to reverse a list, find its middle, detect a cycle and merge two sorted lists.