Lists — The Pipeline — thecodingidiot.com

Everything in libtci up to this point reimplements a libc function — you built each one to understand what the standard library does before using it. The list functions are different, and they live in a different library. There is no lstnew in libc, no lstclear.

What follows is a pattern: a generic singly-linked list, the kind that turns up in almost every non-trivial C project. These functions go into libtciutil — the utility library started in c03 — with the tciu_ prefix.

The list section introduces concepts — void * as a generic container, function pointers, the double pointer pattern — that will not fully click until the later c-tier chapters. Meet them here, in a contained context. You do not need to have all of it figured out today.

Every container you have used so far — arrays, char ** like argv — has a fixed shape at allocation time, or requires reallocation to grow.

A linked list is different. Each element is its own heap allocation — a node. Adding one means allocating a node and wiring it in. Removing one means adjusting one pointer and calling free. No existing element moves.

The cost is access speed. An array gives you any element in one step: arr[i]. A list requires walking from the front — n steps to reach the nth element.

Use arrays when you know the size up front or need random access. Use lists when you are building a collection of unknown length and only ever traverse it front to back.

The node structure

You have used structs since c02/08, where fmt_t carried parsed format flags, and again in c04/01 for the game-state type. A linked-list node needs exactly two fields: a pointer to its content, and a pointer to the next node.

content is void * — a pointer to anything. The same struct works for a list of strings, integers, or any type you define.

next == NULL serves the same role as \0 in a string — a sentinel that signals the end of the sequence:

string:  h → e → l → l → o → \0
  list:  A → B → C → D → E → NULL

Walking a string stops when the byte at the current address is zero. Walking a list stops when node->next is NULL. The pattern is identical.

Struct syntax

The t_list struct is self-referential — its next field points to another t_list. That form requires a tag, which you have not needed before. The standard syntax first, then the self-referential form:

struct point {
    int  x;
    int  y;
};

Access fields through a value with .; through a pointer with ->:

struct point   p;
struct point  *ptr;
 
p.x = 3;
p.y = 4;
 
ptr = &p;
ptr->x = 3;

ptr->x means: follow the pointer to the struct it points at, then read the field x. It is shorthand for (*ptr).x — the two forms are identical. Every -> in the list functions below is doing exactly this.

typedef gives the struct a shorter alias so you do not have to write struct everywhere:

typedef struct point {
    int  x;
    int  y;
} t_point;
 
t_point  p;   /* instead of: struct point p; */

Add the type definition to libtciutil.h, before the function declarations and after the #include "libtciutil.h" line:

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

struct s_list is a self-referential structure: the next field points to another struct s_list. You need the struct tag (s_list) to write the type of next inside the definition, because the t_list typedef is not yet complete at that point. This is the standard C pattern for linked-list nodes.

typedef gives the type the alias t_list, so the rest of the code can write t_list *node instead of struct s_list *node.

tciu_lstnew

tciu_lstnew allocates a new node holding content and returns a pointer to it:

Create tciu_lstnew.c:

#include "libtciutil.h"
#include <stdlib.h>
 
t_list  *tciu_lstnew(void *content)
{
    t_list  *node;
 
    node = malloc(sizeof(t_list));  /* space for the struct, not the content */
    if (!node)
        return (NULL);
    node->content = content;        /* store the pointer; the caller owns what it points at */
    node->next = NULL;              /* a freshly allocated node is never mid-list */
    return (node);
}

sizeof(t_list) is the size of the struct — on a 64-bit platform, two 8-byte pointers = 16 bytes. node->content = content uses the arrow operator (->) to assign through the pointer; node->next = NULL sets the "no next node" sentinel. A newly allocated node is never in the middle of a list, so next starts as NULL.

Add tciu_lstnew.c to libtciutil's SRCS and its declaration to libtciutil.h:

t_list  *tciu_lstnew(void *content);

tciu_lstadd_front

tciu_lstadd_front prepends new to the list pointed at by *lst. It takes t_list **lst — a pointer to the pointer that holds the front of the list — because it needs to modify that pointer:

Create tciu_lstadd_front.c:

#include "libtciutil.h"
 
void    tciu_lstadd_front(t_list **lst, t_list *new)
{
    new->next = *lst;   /* point new at the current front (NULL if list is empty) */
    *lst = new;         /* update the caller's front pointer */
}

new->next = *lst makes new point at the current front. *lst = new makes new the new front. Two assignments; the node is in the list.

Why t_list **lst and not t_list *lst? The same reason add_one in the pointer page needed int *n: without a pointer to the front pointer, changes inside the function would not be visible to the caller. When the list is empty, *lst is NULL; after this call, *lst is new. Without the double pointer, the caller's variable would still be NULL.

Add tciu_lstadd_front.c to libtciutil's SRCS and its declaration to libtciutil.h:

void    tciu_lstadd_front(t_list **lst, t_list *new);

tciu_lstlast

tciu_lstlast returns the last node in the list. It is needed by tciu_lstadd_back:

Create tciu_lstlast.c:

#include "libtciutil.h"
 
t_list  *tciu_lstlast(t_list *lst)
{
    if (!lst)
        return (NULL);          /* empty list has no last node */
    while (lst->next)
        lst = lst->next;        /* advance until next is NULL: that node is last */
    return (lst);
}

The loop stops when lst->next is NULL. At that point lst is pointing at the node whose next is NULL — the last node. That is what gets returned.

lst = lst->next reassigns the local variable lst. It moves your position in the list — it does not write into any node. Compare the two forms:

lst = lst->next — the local variable now holds a different address; the list is unchanged
lst->next = something — writes into the node lst points at; the list changes

The first is navigation. The second is modification. Every traversal in libtci uses the first form.

Add tciu_lstlast.c to libtciutil's SRCS and its declaration to libtciutil.h:

t_list  *tciu_lstlast(t_list *lst);

tciu_lstadd_back

tciu_lstadd_back appends new to the end of the list. If the list is empty, new becomes the first node (same logic as tciu_lstadd_front):

Create tciu_lstadd_back.c:

#include "libtciutil.h"
 
void    tciu_lstadd_back(t_list **lst, t_list *new)
{
    t_list  *last;
 
    if (!*lst) {
        *lst = new;             /* empty list: new node becomes the first */
        return;
    }
    last = tciu_lstlast(*lst);    /* walk to the end */
    last->next = new;           /* new->next is already NULL from tciu_lstnew */
}

When the list is non-empty, tciu_lstlast finds the current last node and last->next = new wires new in after it. new->next is still NULL from when tciu_lstnew set it, so new correctly becomes the last node.

Add tciu_lstadd_back.c to libtciutil's SRCS and its declaration to libtciutil.h:

void    tciu_lstadd_back(t_list **lst, t_list *new);

tciu_lstsize

tciu_lstsize counts the number of nodes in the list:

Create tciu_lstsize.c:

#include "libtciutil.h"
 
int     tciu_lstsize(t_list *lst)
{
    int  size;
 
    size = 0;
    while (lst) {
        lst = lst->next;    /* advance before incrementing: both happen once per node */
        size++;
    }
    return (size);
}

Walk until lst is NULL, counting each step. The return type is int rather than size_t — lists are rarely large enough for the distinction to matter.

Add tciu_lstsize.c to libtciutil's SRCS and its declaration to libtciutil.h:

int     tciu_lstsize(t_list *lst);

A manual list test

Before continuing, assemble a short test to confirm the list functions work together:

#include "libtciutil.h"
 
int main(void)
{
    t_list  *list;
    t_list  *node;
 
    list = NULL;
    tciu_lstadd_back(&list, tciu_lstnew("first"));
    tciu_lstadd_back(&list, tciu_lstnew("second"));
    tciu_lstadd_back(&list, tciu_lstnew("third"));
    tciu_lstadd_front(&list, tciu_lstnew("zeroth"));
 
    tci_printf("size: %d\n", tciu_lstsize(list));
 
    node = list;
    while (node) {
        tci_printf("%s\n", (char *)node->content);
        node = node->next;
    }
 
    return (0);
}

The (char *)node->content cast is necessary: content is void * and printf's %s expects char *. The list stores void *; you know the content is a string; you cast when you use it.

Compile and run:

make re
gcc -Wall -Wextra -g -std=c99 test_list.c -L. -ltciutil -ltci -I. -o test_list
./test_list

Expected output:

size: 4
zeroth
first
second
third

Confirm the output is in order. Then delete the test file and binary.

Note that this test leaks memory — the nodes allocated by tciu_lstnew are never freed. The next page adds the cleanup functions that handle that properly.