What does a linked list implementation tell you about a C programmer? Why is it a historically common interview question? Is it still worth asking someone in 2024? A couple years ago this post by Hillel Wayne discussed the possible history of the question and how it became an interview staple for C programmers. I agree with essentially all of the analysis there so you should read it first before getting into why I think this question still has relevance because, especially when interviewing candidates for senior positions, it identifies programmers who are familiar with C idioms and not just C syntax.

Imaginary Interview

Let's imagine I'm interviewing someone and ask them to implement a singly linked list that supports appending, inserting into the list in an arbitrary spot, and removing elements from the list. I ask them to go for something basic so that we can start talking about how they've implemented it and how it might be improved. They quickly produce code like this, after a little bit of the usual C testing and debugging:

struct slist {
    struct slist *next;
    void *data;
};

#define foreach_slist(_list, _data) \
    for (struct slist *_iter = _list; _iter && ((_data = _iter->data)); _iter = _iter->next)

struct slist *slist_alloc(void *data) {
    struct slist *node = calloc(1, sizeof(*node));
    node->data = data;
    return node;
}

void slist_insert_after(struct slist *head, void *data) {
    struct slist *node = slist_alloc(data);
    node->next = head->next;
    head->next = node;
}

void slist_append(struct slist *head, void *data) {
    while (head->next)
        head = head->next;
    slist_insert_after(head, data);
}

void slist_remove_after(struct slist *head) {
    if (head->next) {
        struct slist *node = head->next;
        head->next = node->next;
        free(node);
    }
}

struct slist *slist_remove(struct slist *head, void *data) {
    if (head->data == data) {
        struct slist *rtn = head->next;
        free(head);
        return rtn;
    }
    head->next = slist_remove(head->next, data);
    return head;
}

Here's the matching test/user, storing some ints in our list to simplify the test implementation, with the understanding that in a real program it'd be storing pointers instead:

#include <stdio.h>
#include <stdlib.h>

int main(void) {
    void *data;
    struct slist *head = slist_alloc((void*)5);
    slist_append(head, (void*)6);
    slist_append(head, (void*)7);

    printf("Old list: ");
    foreach_slist(head, data) {
        int val = (int)data;
        printf("%d ", val);
    }
    printf("\n");

    head = slist_remove(head, (void*)6);
    printf("New list: ");
    foreach_slist(head, data) {
        int val = (int)data;
        printf("%d ", val);
    }
    printf("\n");


    return 0;
}

We dive into it. There's a softball problem: slist_remove is rebuilding the entire list, so I ask them why they've done it that way and what could be done to fix it? My interviewee immediately answers, "I realized it as I was writing the function out, but to fix it properly I want a list container so that the list head being passed to slist_remove never needs to be deleted--it'd take the container instead and the head pointer in the container could be deleted without confusing the caller or complicating list management. The remove code would then be able to traverse the list and remove just one node without reassigning all of the next pointers. It'd also simplify working with an empty list, because in the current version the user has to handle an empty list as a null pointer, which creates a lot of special cases in the user code that should instead be inside the library code."

The first version would never have been submitted for review, but during an interview one might be nervous or feel pressured to produce something as fast as possible, so the first implementation is going to have problems like this. But they already understand them and have a good plan for fixing them, so there's no real reason to dwell on them, and I skip another small problem in the foreach macro (what happens if you store a 0 integer? can you work around this?).

No Allocations

We can, instead, dive into to the real question I wanted to ask all along: "This implementation performs too many allocations. I would like a linked list that does no allocations at all. How would you do that?"

The interviewee says "Well, that is pretty simple but the code is not very reusable and you'd have to re-implement all the linked list operations for each struct that was to be stored in a list. We just locally implement a linked list as part of some other struct foo, as it is quite easy:"

They type out some pseudo-C to illustrate their point:

struct foo {
    struct foo *next;
    int bar;
};

void foo_append(struct foo * restrict head, struct foo * restrict new) {
    ...
}

struct foo *foo_remove(struct foo *head, struct foo *rem) {
    ...
}

They explain further, "so these append and remove functions would be essentially the same as the generic ones from before but they'd be specific to struct foo, and we'd need to re-implement them for each struct. Maybe we could stick in some kind of macro to generate it, but really we should just use C++ and implement it as a template to make the implementation easier to understand, maybe something along these lines:"

template<typename T>
class ListNode {
    ListNode<T> *next;

    void append(ListNode<T> *data) { ... }
    ListNode<T> remove(ListNode<T> *rem) { ...}
};

class Foo : ListNode<Foo> {
    ...
};

"Otherwise, we need to stick to the generic version in C with the node allocations. It would be a poor design to have a dozen linked list implementations in our code base in order to avoid allocations."

Do you agree? Is it possible to satisfy both objectives at once and produce a no-allocation linked list implementation that is generic and reusable in C only, or is another language required?

The C Version

In the standard, it specifies that the first element of a struct has the same address as the struct. That is, in a struct defined like so,

struct slist_node {
    struct slist_node *next;
};

struct foo {
    struct slist_node node;
};

struct foo x;

The values of &x and &x.node are the same. So if a pointer to struct slist_node is known to be contained within a struct foo, we can convert between the two pointers with a typecast and have valid behavior. By embedding the list node struct inside our structure at the start, we can freely convert between the two, so we can write a generic linked list in terms of struct slist_node and embed it in an arbitrary structure to be able to use it with the linked list implementation. It is both a generic implementation and it requires no allocations to do list operations! At first, however, this seems dangerous: what if someone unfamiliar with it inserts another value in front of the list node in the struct definition? Can we prevent that? We actually can with static_assert:

static_assert(offsetof(struct foo, node) == 0, "node must come first in foo");

Now if another programmer changes our layout they'll see a compiler error and we have achieved some level of safety, as our assumptions about the struct layout are encoded and verified by the compiler. There's an entirely separate question of ensuring that we only encounter struct slist_nodes that are contained within the right type of struct, but that issue is addressed in a different part of the design dealing with how code is broken into translation units.

This raises even more questions: what if I want to put struct foo into two linked lists at the same time, as this requires two list nodes? What if I adopt this more broadly and I want struct foo to be a linked list node and also be something else, like an event, which might have a similar requirement to place struct event at offset zero in order to do conversion?

Hopefully it is clear that the answer is pointer arithmetic. The first pass took advantage of the location of the first element of a struct being known--there is never padding at the start of a struct--so a list node pointer could be converted to a foo pointer by doing nothing. We can generalize this to a conversion between a member and its container by subtracting the offset of that member within the container from a given pointer:

struct foo *to_foo(struct slist_node *node) {
    return (struct foo *)((char *)node - offsetof(struct foo, node));
}

In this way, regardless of how the layout of struct foo changes, the correct pointer conversion will be performed to obtain the containing structure address based on the address of the node member. This is so common in the Linux kernel that there's an associated macro to further improve the robustness by adding some type checking to ensure the casts aren't covering up a mistake:

#define __same_type(a, b) __builtin_types_compatible_p(typeof(a), typeof(b))
#define container_of(ptr, type, member) ({                \
    void *__mptr = (void *)(ptr);                   \
    static_assert(__same_type(*(ptr), ((type *)0)->member) ||   \
              __same_type(*(ptr), void),            \
              "pointer type mismatch in container_of()");   \
    ((type *)(__mptr - offsetof(type, member))); })

Armed with the implementation of container_of from the kernel we can provide our most general linked list implementation, which supports putting a single struct into multiple lists, does not allocate memory, and can be combined with any struct using a small amount of glue code to do the necessary type conversions:

struct slist_node {
    struct slist_node *next;
};

struct slist {
    struct slist_node head;
};

#define foreach_slist(_list, _iter) \
    for (_iter = (_list)->head.next; _iter; _iter = _iter->next)

void slist_append(struct slist *list, struct slist_node *node) {
    struct slist_node *head = &list->head;

    while (head->next)
        head = head->next;

    head->next = node;
}

void slist_insert_after(struct slist_node * restrict head,
    struct slist_node * restrict node)
{
    node->next = head->next;
    head->next = node;
}

void slist_remove_after(struct slist_node *node) {
    if (node->next)
        node->next = node->next->next;
}

void slist_remove(struct slist *list, struct slist_node *node) {
    struct slist_node *prev = &list->head;
    struct slist_node *next = list->head.next;

    while (next) {
        if (next == node) {
            slist_remove_after(prev);
            return;
        }

        prev = next;
        next = next->next;
    }
}

The matching user code looks like this:

#include <assert.h>
#include <stddef.h>
#include <stdio.h>
#include <stdlib.h>

#define __same_type(a, b) __builtin_types_compatible_p(typeof(a), typeof(b))
#define container_of(ptr, type, member) ({                \
    void *__mptr = (void *)(ptr);                   \
    static_assert(__same_type(*(ptr), ((type *)0)->member) ||   \
              __same_type(*(ptr), void),            \
              "pointer type mismatch in container_of()");   \
    ((type *)(__mptr - offsetof(type, member))); })

struct foo {
    struct slist_node node;
    int value;
};

struct foo *to_foo(struct slist_node *node) {
    return container_of(node, struct foo, node);
}

int main(void) {
    struct foo a = { .value = 1 };
    struct foo b = { .value = 2 };
    struct foo c = { .value = 3 };
    struct slist list = {0};
    struct slist_node *node;

    slist_append(&list, &a.node);
    slist_append(&list, &b.node);
    slist_append(&list, &c.node);

    printf("Old: ");
    foreach_slist(&list, node) {
        struct foo *f = to_foo(node);
        printf("%d ", f->value);
    }
    printf("\n");

    slist_remove(&list, &b.node);
    printf("New: ");
    foreach_slist(&list, node) {
        struct foo *f = to_foo(node);
        printf("%d ", f->value);
    }
    printf("\n");

    return 0;
}

Is This a Useful Insight?

I started off by asserting that the point of asking this question is to help identify people who are familiar with C-specific idioms, not just with the language syntax or the notion of storing a few pointers or swapping them, as ultimately the default linked list implementation in C, Java, and other imperative languages looks structurally similar. Although the goal can be accomplished in C++ and possibly in other languages, doing it in C requires not just pointer management but pointer arithmetic and a level of comfort with the memory layout of a structure that is rarely relevant in another language.

In an embedded system, the resource constraints generally require this kind of thinking. Dynamic memory allocation may be disallowed entirely, as it introduces additional bug potential and complicates system analysis, because malloc has unbounded runtime and memory fragmentation increases the worst case bound on overhead, which could drive up cost if larger amounts of external memory are required as a result. But in contrast, this approach has less per element memory usage (one pointer rather than two) and very consistent and predictable performance for list operations. Outside of embedded, any system that implements some kind of object-like or polymorphic functionality is going to require one of two main implementation strategies; this is one of them and the other involves unions, type identifiers, and large switch statements.

It's not a perfect question, but it's a reasonable way to start a discussion of all of these topics, grounded in simple code free of algorithmic challenges.