Linked List — Holberton Cheat Sheet

C'EST QUOI UNE LINKED LIST ?

🔗 DÉFINITION — PARTIR DE ZÉRO

Une linked list (liste chaînée) est une structure de données où chaque élément — appelé nœud (node) — contient deux choses : une donnée et un pointeur vers le nœud suivant. Les nœuds sont éparpillés dans le heap, liés entre eux par ces pointeurs.

🕹️ ANALOGIE GAMING

Imagine une quête en chaîne dans un RPG : le PNJ A te dit "va voir le PNJ B", le PNJ B te dit "va voir le PNJ C", et ainsi de suite jusqu'au dernier qui te dit "c'est terminé" (NULL). Chaque PNJ contient son info + l'adresse du suivant. Si tu veux insérer un nouveau PNJ entre A et B, tu changes juste les pointeurs — pas besoin de tout réorganiser.

Visualisation d'une linked list [42 → 7 → 13 → NULL] :

HEAD ▼

next*

node 1

→

next*

node 2

→

next*

node 3

→

NULL

HEAD est le seul pointeur que tu gardes. C'est le point d'entrée de ta liste. Si tu perds head, tu perds toute la liste (les nœuds existent encore en mémoire mais sont inaccessibles → memory leak).

TABLEAU vs LINKED LIST — QUAND CHOISIR ?

⚖️ COMPARAISON COMPLÈTE

Critère	Tableau (array)	Linked List
Taille	Fixe à la déclaration	✅ Dynamique, grandit/rétrécit
Accès à l'élément N	✅ Instantané : `arr[3]`	❌ Doit parcourir depuis HEAD
Insertion en début	❌ Décaler tout → O(n)	✅ Changer HEAD → O(1)
Insertion en milieu	❌ Décaler → O(n)	✅ Changer 2 pointeurs → O(1)
Suppression	❌ Décaler → O(n)	✅ Changer 1 pointeur → O(1)
Mémoire	✅ Contiguë, compacte	❌ Overhead du pointeur (8 bytes/nœud)
Cache CPU	✅ Très rapide (localité)	❌ Nœuds éparpillés → cache miss
Taille connue à l'avance ?	✅ Oui → utilise un tableau	✅ Non → utilise une linked list

DÉCLARER LA STRUCTURE D'UN NŒUD

🧱 LA STRUCT NODE — LA BASE DE TOUT

/* Convention Holberton : tag _s, typedef _t */

typedef struct node_s
{
    int            n;      /* la donnée (peut être n'importe quel type) */
    struct node_s *next;  /* pointeur vers le nœud suivant */
} node_t;

/* ⚠️ On DOIT écrire struct node_s *next (pas node_t *next)
   car le typedef n'est pas encore connu à ce stade */

/* Le dernier nœud a next = NULL — c'est la sentinelle de fin */

Pourquoi struct node_s *next et pas node_t *next ? Parce que dans une struct, on ne peut pas utiliser un typedef qui n'est pas encore défini. On utilise le tag complet struct node_s qui, lui, est déjà connu à ce stade de la déclaration.

Chaque nœud en mémoire ressemble à ça :

  Adresse 0x100        Adresse 0x200       Adresse 0x300
  ┌──────────┬───────┐ ┌──────────┬───────┐ ┌──────────┬───────┐
  │  n = 42  │ 0x200 │→│  n = 7   │ 0x300 │→│  n = 13  │ NULL  │
  └──────────┴───────┘ └──────────┴───────┘ └──────────┴───────┘
     data      next        data      next       data      next
    (les nœuds sont éparpillés dans le HEAP, pas contigus)

CRÉER ET AJOUTER DES NŒUDS

🆕 CRÉER UN NŒUD — NEW_NODE

#include <stdlib.h>

node_t *new_node(int n)
{
    node_t *node;

    node = malloc(sizeof(node_t));
    if (node == NULL)
        return (NULL);           /* toujours vérifier malloc ! */
    node->n    = n;              /* assigner la donnée */
    node->next = NULL;          /* le nouveau nœud pointe vers rien */
    return (node);
}

➕ ADD EN DÉBUT — ADD_NODE (le plus simple)

Ajouter en début de liste est O(1) — la plus rapide des insertions.

node_t *add_node(node_t **head, int n)
{
    node_t *node = new_node(n);

    if (node == NULL)
        return (NULL);

    node->next = *head;  /* le nouveau pointe vers l'ancien head */
    *head = node;        /* head devient le nouveau nœud */
    return (node);
}

/* ⚠️ node_t **head = pointeur VERS le pointeur head
   On a besoin de ** pour MODIFIER head depuis la fonction
   (sinon on modifie une copie locale) */

Visualisation — ajouter 99 en tête :

Avant :  head → [42|*] → [7|*] → [13|NULL]

Étapes :
1. Créer node [99|*]
2. node->next = head        → [99|*] → [42|*] → [7|*] → [13|NULL]
3. head = node              → head pointe maintenant sur [99]

Après :  head → [99|*] → [42|*] → [7|*] → [13|NULL]

➕ ADD EN FIN — ADD_NODE_END

Ajouter à la fin nécessite de parcourir toute la liste jusqu'au dernier nœud — O(n).

node_t *add_node_end(node_t **head, int n)
{
    node_t *node = new_node(n);
    node_t *tmp;

    if (node == NULL)
        return (NULL);

    if (*head == NULL)         /* liste vide → le nœud devient head */
    {
        *head = node;
        return (node);
    }
    tmp = *head;
    while (tmp->next != NULL)  /* parcourir jusqu'au dernier */
        tmp = tmp->next;
    tmp->next = node;           /* l'ancien dernier pointe vers le nouveau */
    return (node);
}

PARCOURIR UNE LINKED LIST

🔍 TRAVERSER LA LISTE — LE PATTERN DE BASE

/* Afficher tous les nœuds */
void print_list(node_t *head)
{
    node_t *current = head;  /* on travaille sur une copie du pointeur */

    while (current != NULL)
    {
        printf("%d\n", current->n);
        current = current->next; /* avancer au nœud suivant */
    }
}

/* Compter les nœuds */
size_t list_len(node_t *head)
{
    size_t  len = 0;
    node_t *current = head;

    while (current != NULL)
    {
        len++;
        current = current->next;
    }
    return (len);
}

/* Chercher un élément */
node_t *search(node_t *head, int target)
{
    while (head != NULL)
    {
        if (head->n == target)
            return (head);     /* trouvé ! retourner le nœud */
        head = head->next;
    }
    return (NULL);             /* pas trouvé */
}

Le pattern universel : node_t *tmp = head; while (tmp != NULL) { ... tmp = tmp->next; }. Mémorise ce pattern — c'est la base de 90% des opérations sur les linked lists.

SUPPRIMER DES NŒUDS

🗑️ FREE — LIBÉRER CORRECTEMENT

/* Supprimer le premier nœud (pop front) */
node_t *pop_front(node_t **head)
{
    node_t *tmp;

    if (*head == NULL)
        return (NULL);          /* liste vide */
    tmp = *head;               /* sauvegarder le nœud à supprimer */
    *head = (*head)->next;     /* head passe au suivant */
    free(tmp);                 /* libérer l'ancien head */
    return (*head);
}

/* Libérer TOUTE la liste — INDISPENSABLE pour valgrind ✅ */
void free_list(node_t *head)
{
    node_t *tmp;

    while (head != NULL)
    {
        tmp  = head->next;  /* sauvegarder le suivant AVANT de free */
        free(head);         /* libérer le nœud actuel */
        head = tmp;         /* avancer */
    }
}

/* Supprimer un nœud par valeur */
void delete_node(node_t **head, int n)
{
    node_t *tmp = *head;
    node_t *prev = NULL;

    while (tmp != NULL && tmp->n != n)
    {
        prev = tmp;
        tmp  = tmp->next;
    }
    if (tmp == NULL) return;   /* pas trouvé */
    if (prev == NULL)            /* c'était le head */
        *head = tmp->next;
    else
        prev->next = tmp->next;  /* court-circuiter le nœud */
    free(tmp);
}

Dans free_list, toujours sauvegarder head->next dans tmp AVANT de free(head). Sinon tu accèdes à de la mémoire déjà libérée → undefined behavior.

LES 3 BOSS — EXEMPLES PROGRESSIFS

🐣 BOSS 1 — CRÉER ET AFFICHER UNE LISTE

⚔️ LVL 1 — FACILE

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

typedef struct node_s {
    int            n;
    struct node_s *next;
} node_t;

node_t *add_node(node_t **head, int n)
{
    node_t *node = malloc(sizeof(node_t));
    if (!node) return (NULL);
    node->n    = n;
    node->next = *head;
    *head = node;
    return (node);
}

void print_list(node_t *head)
{
    while (head)
    {
        printf("[%d] → ", head->n);
        head = head->next;
    }
    printf("NULL\n");
}

void free_list(node_t *head)
{
    node_t *tmp;
    while (head) { tmp = head->next; free(head); head = tmp; }
}

int main(void)
{
    node_t *head = NULL;  /* liste vide = NULL */

    add_node(&head, 13);
    add_node(&head, 7);
    add_node(&head, 42);
    print_list(head);   /* [42] → [7] → [13] → NULL */
    free_list(head);
    return (0);
}

⚔️ BOSS 2 — INVERSER UNE LISTE

🔥 LVL 2 — INTERMÉDIAIRE

/* Inverser la liste en place — O(n) temps, O(1) espace */
node_t *reverse_list(node_t **head)
{
    node_t *prev    = NULL;
    node_t *current = *head;
    node_t *next;

    while (current != NULL)
    {
        next           = current->next;  /* sauvegarder le suivant */
        current->next  = prev;           /* inverser le pointeur */
        prev           = current;        /* avancer prev */
        current        = next;           /* avancer current */
    }
    *head = prev;  /* prev est maintenant le nouveau head */
    return (*head);
}

/* Visualisation étape par étape :
   Avant  : head → [42] → [7] → [13] → NULL
   iter 1 :  NULL ← [42]   [7] → [13] → NULL
   iter 2 :  NULL ← [42] ← [7]   [13] → NULL
   iter 3 :  NULL ← [42] ← [7] ← [13]
   Après  : head → [13] → [7] → [42] → NULL */

💀 BOSS FINAL — LISTE TRIÉE (INSERT SORTED)

💀 LVL 3 — HOLBERTON STYLE

/* Insérer un nœud en maintenant la liste triée */
node_t *insert_sorted(node_t **head, int n)
{
    node_t *node = malloc(sizeof(node_t));
    node_t *tmp;

    if (!node) return (NULL);
    node->n    = n;
    node->next = NULL;

    /* Cas 1 : liste vide ou n plus petit que le head */
    if (*head == NULL || n <= (*head)->n)
    {
        node->next = *head;
        *head = node;
        return (node);
    }
    /* Cas 2 : chercher la bonne position */
    tmp = *head;
    while (tmp->next != NULL && tmp->next->n < n)
        tmp = tmp->next;
    node->next = tmp->next;  /* insérer entre tmp et tmp->next */
    tmp->next  = node;
    return (node);
}

/* Résultat :
   insert_sorted(&head, 5) sur [1] → [3] → [7] → NULL
   → [1] → [3] → [5] → [7] → NULL ✅ */

ERREURS CLASSIQUES — ❌ vs ✅

❌ ERREURS FRÉQUENTES

/* 1. Oublier de sauvegarder next avant free */
free(head);
head = head->next;  /* ❌ accès mémoire libérée */

/* 2. Modifier head directement (sans **) */
void add(node_t *head, int n)
{
    head = new_node; /* ❌ modifie une copie locale */
}

/* 3. Oublier de vérifier malloc */
node->n = n;  /* ❌ si malloc a retourné NULL */

/* 4. Oublier de free_list → valgrind pleure */
return (0);  /* ❌ sans free_list(head) */

/* 5. Perdre le head */
head = head->next;  /* ❌ si c'est le seul pointeur */

✅ CORRECT

/* 1. Sauvegarder next avant free */
tmp  = head->next;  /* ✅ sauvegarder d'abord */
free(head);
head = tmp;

/* 2. Passer le HEAD par double pointeur */
void add(node_t **head, int n)
{
    *head = new_node; /* ✅ modifie le vrai head */
}

/* 3. Toujours vérifier malloc */
if (!node) return (NULL);  /* ✅ */
node->n = n;

/* 4. Toujours libérer */
free_list(head);
return (0);  /* ✅ valgrind content */

/* 5. Utiliser un tmp pour parcourir */
node_t *tmp = head;  /* ✅ head est préservé */
tmp = tmp->next;

BONUS — DOUBLE LINKED LIST

🔗🔗 LISTE DOUBLEMENT CHAÎNÉE

Chaque nœud a deux pointeurs : next (suivant) et prev (précédent). On peut parcourir dans les deux sens.

typedef struct dnode_s
{
    int             n;
    struct dnode_s *next;  /* → suivant */
    struct dnode_s *prev;  /* ← précédent */
} dnode_t;

Visualisation :

  NULL ← [42|*↔*] ↔ [7|*↔*] ↔ [13|*↔*] → NULL
          head                    tail

Type	Avantages	Inconvénients
Singly (simple)	Moins de mémoire, plus simple	Parcours dans un seul sens
Doubly (double)	Parcours dans les 2 sens, suppression O(1)	2× plus de pointeurs à gérer

RÉSUMÉ — TOUT EN UN COUP D'ŒIL

🗺️ LA CARTE MENTALE COMPLÈTE

/*
 *  LA STRUCTURE DE BASE
 *  ────────────────────────────────────────────────────────
 *  typedef struct node_s {
 *      int            n;
 *      struct node_s *next;   ← struct node_s PAS node_t !
 *  } node_t;
 *
 *  node_t *head = NULL;       ← liste vide = NULL
 *
 *  LE PATTERN UNIVERSEL DE PARCOURS
 *  ────────────────────────────────────────────────────────
 *  node_t *tmp = head;
 *  while (tmp != NULL)
 *  {
 *      [... faire quelque chose avec tmp->n ...]
 *      tmp = tmp->next;
 *  }
 *
 *  LES OPÉRATIONS CLÉS
 *  ────────────────────────────────────────────────────────
 *  Ajouter en tête   → O(1) — changer head
 *  Ajouter en fin    → O(n) — parcourir jusqu'à NULL
 *  Rechercher        → O(n) — parcourir et comparer
 *  Supprimer         → O(n) — trouver + court-circuiter
 *  Libérer tout      → free_list(head) — OBLIGATOIRE valgrind
 *
 *  LES RÈGLES D'OR
 *  ────────────────────────────────────────────────────────
 *  1. Ne JAMAIS perdre le pointeur head
 *  2. Toujours utiliser **head pour modifier head en fonction
 *  3. Toujours sauvegarder tmp->next AVANT de free(tmp)
 *  4. Toujours vérifier malloc != NULL
 *  5. Toujours appeler free_list(head) avant return dans main
 *  6. head = NULL → liste vide (toujours initialiser à NULL)
 */