Removing from a linked list

To take a node out of a chain, one arrow has to skip it. Which box holds that arrow? Watch the tag called link.

⋯36bool remove_key(struct node **link, int key)37{38    while (*link != NULL && (*link)->key != key)39        link = &(*link)->next;40    if (*link == NULL)41        return false;42    struct node *dead = *link;43    *link = dead->next;44    free(dead);45    return true;46}⋯48int main(void)49{50    struct node *head = NULL;51    head = push_front(head, 40);52    head = push_front(head, 30);53    head = push_front(head, 20);54    head = push_front(head, 10);55    remove_key(&head, 30);56    remove_key(&head, 10);57    if (!remove_key(&head, 50))58        printf("no 50\n");59    print_list(head);60    free_list(head);61    return 0;62}

What link points to

The list is the one from Singly linked lists: push_front four times makes 10, 20, 30, 40, with head at 0x7fe8 holding 0x1060, the 10 node. The nodes sit on the heap in the order they were made, 40 first.

To remove 30, the program has to change the box that holds 30’s address. That box is 20’s next field, at 0x1048: the next field of a node starts 8 bytes into it. Change it to 30’s own next, 0x1000, and the chain skips 30. To remove 10, the box to change is head itself, because head holds 10’s address.

So every node has one box that points to it: head for the first node, a next field for every other. Call that box the node’s link. remove_key finds the link and changes it, and its parameter is the address of a link:

bool remove_key(struct node **link, int key)

struct node **link is a pointer to a pointer. It holds the address of a box, and that box holds a node’s address. Read it in steps:

• link is an address, such as 0x1048: the address of 20’s next field.
• *link is what that box holds, 0x1020: the address of the node after it.
• (*link)->key is that node’s key, 30.
• &(*link)->next is the address of that node’s next field: where link moves to next.

Watch link’s box in the clip. The first call gets &head, 0x7fe8: head’s own address. 10 is not 30, so link moves to 0x1068, 10’s next field; then to 0x1048, 20’s next field. There *link is the 30 node, and the loop stops. link points at the box that has to change, never at the node itself. In the picture, link’s tag sits on the node whose next field it points into, 10 and then 20; while link holds head’s address, its box shows 0x7fe8 and there is no tag.

Then two lines do the removal:

• Line 43, *link = dead->next;, writes 0x1000 into 20’s next field. 20’s arrow swings past 30 onto 40.
• Line 44, free(dead);, gives the 30 node back. It hatches.

The second call removes 10, the first node. The loop does not run at all, since head already holds 10’s address: link stays at 0x7fe8, and line 43 writes 0x1040 into head. The same three lines did it, with no extra case for the head.

The third call looks for 50. link walks to 0x1048 and then 0x1008, 40’s next field, which holds NULL. The loop stops on NULL, line 40 sees it, and remove_key returns false without writing anything.

The code and its cost

Finding the link

bool remove_key(struct node **link, int key)
{
    while (*link != NULL && (*link)->key != key)
        link = &(*link)->next;
    if (*link == NULL)
        return false;
    struct node *dead = *link;
    *link = dead->next;
    free(dead);
    return true;
}

The loop stops in one of two places: on the link that holds the key’s node, or on the last next field, which holds NULL. main calls it as remove_key(&head, 30), so the walk starts at head. On an empty list, head holds NULL, so the loop never runs and remove_key returns false at once.

Unlink, then free

The order of lines 43 and 44 matters. After free(dead), the node’s 16 bytes belong to the C library again, and the program must not read them. *link = dead->next reads dead’s next field, so it must run while the node is still the program’s. The worked example below swaps them and shows what the address sanitiser says.

The version with prev and cur

The other common way walks two pointers: cur on the node being looked at, and prev on the one before it.

struct node *remove_first(struct node *head, int key)
{
    struct node *prev = NULL;
    struct node *cur = head;
    while (cur != NULL && cur->key != key) {
        prev = cur;
        cur = cur->next;
    }
    if (cur == NULL)
        return head;
    if (prev == NULL)
        head = cur->next;
    else
        prev->next = cur->next;
    free(cur);
    return head;
}

It works, but the box to change is either head or prev’s next field, so it needs the if (prev == NULL) to tell them apart, and it has to return the new head for main to store: head = remove_first(head, 30);. The pointer to a link has no such case, because head and a next field are both just boxes holding a node’s address.

Freeing a whole list

void free_list(struct node *head)
{
    while (head != NULL) {
        struct node *next = head->next;
        free(head);
        head = next;
    }
}

The same rule: read the next address first, while the node is still the program’s, then free it, then move on. Without next, the line after free(head) would have to read head->next from a freed node.

What it costs

Here n is the number of nodes in the list. Finding the link walks up to n steps, one per node, as any walk does. Unlinking and freeing is a fixed few steps, however long the list is.

Running it yourself

The code pane shows remove_key and main. The full program, remove.c, starts with struct node, push_front, print_list and free_list; the later programs of this chapter copy those lines unchanged. Build and run it with:

gcc -std=c11 -Wall -Wextra -pedantic remove.c -o remove
./remove

It prints no 50, then 20 40 .

Worked example

Remove 20 from 20 → 40 by hand. head is at 0x7fe8 and holds 0x1040, the 20 node; 20’s next field holds 0x1000, the 40 node. Call remove_key(&head, 20):

head now holds 40’s address, and the list is 40. It is the first node again, and no line was different.

Free first, then unlink. Swap lines 43 and 44, so that free(dead); runs before *link = dead->next;, and build the program with the address sanitiser. gcc already warns that the pointer dead is used after free. The run stops in the first call with:

ERROR: AddressSanitizer: heap-use-after-free
READ of size 8
SUMMARY: AddressSanitizer: heap-use-after-free free-first.c:44 in remove_key

The read is 8 bytes, the size of a next field: the program read dead’s next after giving the node back. Without the sanitiser, the C library may already have written its own bookkeeping into those bytes, and the list would then point into it.

Emptying a list of 1,000. Remove every key from a 1,000-node list, one call each. Front first, each key is in the first node, so link never moves: 0 moves of link in all. Back first, the last node of a list of k nodes is k − 1 moves away, so the calls take 999 + 998 + … + 0 = 499,500 moves of link. The same keys, the same lines, and the order alone makes the difference.

Where it’s used

Operating systems. A kernel keeps tasks on linked lists, and a task that finishes is unlinked from its list in a few pointer writes.

Memory allocators. An allocator keeps freed blocks on lists by size; handing a block out removes it from its list.

Hash tables. A table with chaining keeps a short list in each slot, and removing a key is this walk on that list; Hash tables with chaining (18.2) uses it. Deleting from a binary search tree (13.2) uses the same pointer to a link, with a left or right field in place of next. And Memory errors (2.5) has more of the reports the sanitiser gives.

Reference card

Platform: C11, gcc on x86-64 Linux: int 4 bytes, pointers 8, little-endian. Addresses in the pictures are short stand-ins, by one rule for the whole course; sizes are the real ones.