DOUBLY
LINKED LISTS

/* Convention Holberton pour les doubly linked lists */

typedef struct dlistint_s
{
    int                  n;     /* la donnée */
    struct dlistint_s  *prev;  /* ← pointeur vers le nœud PRÉCÉDENT */
    struct dlistint_s  *next;  /* → pointeur vers le nœud SUIVANT */
} dlistint_t;

/* Déclaration — toujours initialiser head ET tail à NULL */
dlistint_t *head = NULL;
dlistint_t *tail = NULL;  /* la doubly a souvent un tail aussi */

O(1) avec tail, O(n) sans. Insère après le dernier nœud.

/* Version avec tail passé en paramètre — O(1) */
dlistint_t *dlistint_add_end(dlistint_t **head, dlistint_t **tail, int n)
{
    dlistint_t *node = create_dlistint_node(n);

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

    if (*head == NULL)           /* liste vide */
    {
        *head = node;
        *tail = node;
        return (node);
    }
    node->prev  = *tail;         /* nouveau ← ancien tail */
    node->next  = NULL;          /* nouveau est le dernier : pas de next */
    (*tail)->next = node;         /* ← CRUCIAL : ancien tail → nouveau */
    *tail = node;                 /* tail devient le nouveau nœud */
    return (node);
}

/* Version sans tail — O(n) */
dlistint_t *dlistint_add_end_no_tail(dlistint_t **head, int n)
{
    dlistint_t *node = create_dlistint_node(n);
    dlistint_t *tmp;

    if (node == NULL) return (NULL);
    if (*head == NULL) { *head = node; return (node); }
    tmp = *head;
    while (tmp->next != NULL)
        tmp = tmp->next;          /* parcourir jusqu'au dernier */
    tmp->next  = node;
    node->prev = tmp;             /* ← lier le prev aussi ! */
    return (node);
}

/* ── AVANT : head → tail (comme singly) ────────────────────── */
size_t print_dlistint(const dlistint_t *h)
{
    size_t count = 0;

    while (h != NULL)
    {
        printf("%d\n", h->n);
        h = h->next;
        count++;
    }
    return (count);
}

/* ── ARRIÈRE : tail → head (unique à la doubly !) ────────────── */
size_t print_dlistint_reverse(const dlistint_t *tail)
{
    size_t count = 0;

    while (tail != NULL)
    {
        printf("%d\n", tail->n);
        tail = tail->prev;   /* ← utiliser prev au lieu de next */
        count++;
    }
    return (count);
}

/* ── COMPTER LES NŒUDS ──────────────────────────────────────── */
size_t dlistint_len(const dlistint_t *h)
{
    size_t len = 0;

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

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

typedef struct dlistint_s {
    int               n;
    struct dlistint_s *prev;
    struct dlistint_s *next;
} dlistint_t;

dlistint_t *add_front(dlistint_t **h, int n)
{
    dlistint_t *node = malloc(sizeof(dlistint_t));
    if (!node) return (NULL);
    node->n    = n;
    node->prev = NULL;
    node->next = *h;
    if (*h) (*h)->prev = node;
    *h = node;
    return (node);
}

int main(void)
{
    dlistint_t *head = NULL;
    dlistint_t *tmp;

    add_front(&head, 13);
    add_front(&head, 7);
    add_front(&head, 42);

    /* Afficher en avant */
    tmp = head;
    while (tmp) { printf("%d ", tmp->n); tmp = tmp->next; }
    printf("\n");  /* → 42 7 13 */

    /* Aller jusqu'au tail puis afficher en arrière */
    tmp = head;
    while (tmp->next) tmp = tmp->next;  /* atteindre le tail */
    while (tmp) { printf("%d ", tmp->n); tmp = tmp->prev; }
    printf("\n");  /* → 13 7 42 */
    return (0);
}

/*
 *  LA STRUCTURE
 *  ─────────────────────────────────────────────────────────
 *  typedef struct dlistint_s {
 *      int               n;
 *      struct dlistint_s *prev;   ← pointe vers le précédent
 *      struct dlistint_s *next;   → pointe vers le suivant
 *  } dlistint_t;
 *
 *  head->prev = NULL   (toujours)
 *  tail->next = NULL   (toujours)
 *  node->next->prev = node  (invariant de cohérence)
 *
 *  LES OPÉRATIONS — COMPLEXITÉS
 *  ─────────────────────────────────────────────────────────
 *  add_front          → O(1)    mettre à jour prev de l'ancien head
 *  add_end (+ tail)   → O(1)    mettre à jour next de l'ancien tail
 *  add_end (- tail)   → O(n)    parcourir jusqu'au dernier
 *  insert_before      → O(1)    grace à prev — avantage vs singly !
 *  delete (any node)  → O(1)    grace à prev — avantage vs singly !
 *  search             → O(n)    parcourir (peut aller dans les 2 sens)
 *  print forward      → O(n)    head → tail via next
 *  print backward     → O(n)    tail → head via prev
 *  free               → O(n)    libérer chaque nœud
 *
 *  LES 4 CAS DU DELETE
 *  ─────────────────────────────────────────────────────────
 *  1. node a un prev → prev->next = node->next
 *  2. node est HEAD  → head = node->next
 *  3. node a un next → next->prev = node->prev
 *  4. node est TAIL  → tail = node->prev
 *
 *  RÈGLES D'OR
 *  ─────────────────────────────────────────────────────────
 *  1. Toujours init prev ET next à NULL
 *  2. Toute modification de next doit s'accompagner de prev
 *  3. Tester NULL avant d'accéder à node->prev ou node->next
 *  4. Gérer le cas nœud unique (head == tail)
 *  5. Si tu as un tail, le maintenir à jour à chaque opération
 *  6. free : sauvegarder next AVANT free (même chose qu'en singly)
 */