C — Linked Lists

A linked list is a chain of nodes where each node holds a value and a pointer to the next node. Unlike arrays, nodes are scattered in heap memory — the links are what connect them.

[value | next] → [value | next] → [value | next] → NULL
   head                                               tail

The Node Struct

typedef struct s_node
{
    int             value;
    struct s_node   *next;
}   t_node;

The next pointer uses struct s_node * (not t_node *) because the typedef is not yet complete at that point in the declaration.

For a generic list (storing any type), use void * for the content:

typedef struct s_list
{
    void            *content;
    struct s_list   *next;
}   t_list;

Creating a Node

Always allocate on the heap — stack-allocated nodes are destroyed when the function returns:

t_node  *new_node(int value)
{
    t_node *node;

    node = malloc(sizeof(t_node));
    if (!node)
        return (NULL);
    node->value = value;
    node->next  = NULL;
    return (node);
}

Always check the return value of malloc — if it returns NULL, allocation failed.

Building a List

Add to the Front

Prepending is O(1) — no traversal needed:

void    push_front(t_node **head, int value)
{
    t_node *node;

    node = new_node(value);
    if (!node)
        return ;
    node->next = *head;
    *head = node;
}

head is a double pointer so the function can update the caller’s pointer.

t_node *list = NULL;
push_front(&list, 3);   // [3]
push_front(&list, 2);   // [2] → [3]
push_front(&list, 1);   // [1] → [2] → [3]

Add to the Back

Appending requires traversing to the last node — O(n):

void    push_back(t_node **head, int value)
{
    t_node *node;
    t_node *current;

    node = new_node(value);
    if (!node)
        return ;
    if (!*head)
    {
        *head = node;
        return ;
    }
    current = *head;
    while (current->next)
        current = current->next;
    current->next = node;
}

Traversing a List

Walk from head to NULL, processing each node:

void    print_list(t_node *head)
{
    t_node *current;

    current = head;
    while (current)
    {
        printf("%d\n", current->value);
        current = current->next;
    }
}

Never modify head directly while traversing — use a separate current pointer.

Searching

Return the first node that matches a value, or NULL if not found:

t_node  *find(t_node *head, int target)
{
    while (head)
    {
        if (head->value == target)
            return (head);
        head = head->next;
    }
    return (NULL);
}

List Size

int ft_lstsize(t_node *head)
{
    int count;

    count = 0;
    while (head)
    {
        count++;
        head = head->next;
    }
    return (count);
}

Last Node

t_node  *ft_lstlast(t_node *head)
{
    if (!head)
        return (NULL);
    while (head->next)
        head = head->next;
    return (head);
}

Deleting a Node

To remove a node from the middle, re-link the previous node’s next to skip it:

void    delete_node(t_node **head, int target)
{
    t_node *current;
    t_node *prev;

    current = *head;
    prev = NULL;
    while (current)
    {
        if (current->value == target)
        {
            if (prev)
                prev->next = current->next;
            else
                *head = current->next;   // deleting the head
            free(current);
            return ;
        }
        prev = current;
        current = current->next;
    }
}

Freeing the Entire List

Walk the list and free each node. Advance the pointer before freeing the current node:

void    free_list(t_node **head)
{
    t_node *current;
    t_node *next;

    current = *head;
    while (current)
    {
        next = current->next;   // save next before freeing
        free(current);
        current = next;
    }
    *head = NULL;   // prevent dangling pointer
}

Never call current = current->next after free(current) — the memory is invalid.

Applying a Function to Every Node

Iterate over the list and call a function on each node’s content:

void    ft_lstiter(t_list *lst, void (*f)(void *))
{
    while (lst)
    {
        f(lst->content);
        lst = lst->next;
    }
}

This is the void * function pointer pattern — f can be any function that takes a void *.

Doubly Linked Lists

A doubly linked list adds a prev pointer so you can traverse in both directions:

typedef struct s_dnode
{
    int             value;
    struct s_dnode  *next;
    struct s_dnode  *prev;
}   t_dnode;

Insertion and deletion are more complex (two pointers to update instead of one), but moving backwards or deleting a node given only its pointer becomes O(1).

Linked List vs Array

Use a linked list when you insert or remove frequently at the front, or when the size changes unpredictably. Use an array when you need fast indexed access.

Quick Reference