Linked list: delete nodes

You need a reference to the preceding node, because its next-pointer is pointing to the node to be deleted. That cannot obviously not stay like that: that next-pointer needs to be updated to skip that to-be-deleted node and point to the next one.

If you only have a reference to the node to be deleted, there is no way to make that update on the previous node -- other than starting a new traversal in the list starting from the head node, in order to find back the preceding node and make that update.

Here is a visualisation of a linked list with five nodes and values 1, 2, 3, 4 and 5:

 head
  ↓ 
┌───────────┐   ┌───────────┐   ┌───────────┐   ┌───────────┐   ┌───────────┐
│ value: 1  │   │ value: 2  │   │ value: 3  │   │ value: 4  │   │ value: 5  │
│ next: ——————→ │ next: ——————→ │ next: ——————→ │ next: ——————→ │ next:null │
└───────────┘   └───────────┘   └───────────┘   └───────────┘   └───────────┘

Now let's say you want to delete the node with value 4 (I'll call this Node 4) ... then the result should be:

 head
  ↓ 
┌───────────┐   ┌───────────┐   ┌───────────┐   ┌───────────┐   ┌───────────┐
│ value: 1  │   │ value: 2  │   │ value: 3  │   │ value: 4  │   │ value: 5  │
│ next: ——————→ │ next: ——————→ │ next: ──────┐ │ next:null │   │ next:null │
└───────────┘   └───────────┘   └───────────┘ │ └───────────┘   └───────────┘
                                              │                    ↑
                                              └────────────────────┘

... after which the memory used by that node can be freed.

Two things changed here:

• Node 3 had its next pointer redirected to Node 5
• Node 4 had its next pointer set to NULL -- which is optional, but really stresses the fact that this node is no longer in a relationship with the list.

As we need to change something in Node 3, we need a reference to it. And that is a problem when we only have a reference to Node 4. The only way to get a reference to Node 3 is to start from head and follow from there the next pointers... until we arrive at Node 3. But that is a waste of time.

If however we would have a reference to Node 3 we also have a reference to Node 4: it is the next pointer sitting in Node 3! And so we have everything we need to perform the removal of Node 4 when we have only a reference to Node 3.

So an implementation could look like this -- I use c:

void delete_after(Node * prev) {
    Node * node = prev->next; // get a reference to the node that needs removal
    if (node == NULL) return; // Nothing to do
    // And here is the reason why we need prev:
    prev->next = node->next; // Rewire, skipping the node to delete
    node->next = NULL; // optional
    free(node);
}

There are two cases here:

1. The 4th node is the last node in the linked list:
   In this case, we will need a pointer to the third node, so we can update the next pointer for it (also explained in @trincot's answer)
2. There are more than 4 nodes:
   Here, you don't actually need a pointer to the third node. You can copy the 5th node onto the 4th node, and delete the 5th node. Example: let the linked list be 1 -> 3 -> 6 -> 2 -> 5 -> None. First we copy the 5th node onto the 4 node. The list now becomes 1 -> 3 -> 6 -> 5 -> 5 -> None. Since you already have a pointer to the 4th node, you can delete the 5th node easily (by setting node.next = node.next.next for the 4th node). The list now looks like 1 -> 3 -> 6 -> 5 -> None, where we have deleted the 4th node from the original linked list without using a pointer to the third node.