Chaînage, insertion et variantes

Version "a la main"

Un tableau simule la memoire. Chaque cellule contient (valeur, suivant). L'indice free pointe la prochaine case libre.

Version pointeurs

typedef struct Node { int value; struct Node *next; } Node;

Node *list_push_front(Node *head, int v) {
  Node *n = malloc(sizeof(Node));
  if (!n) return head;
  n->value = v; n->next = head; return n;
}
          

Insertion en tete en O(1), mais il faut penser a liberer.

Variantes

Liste doublement chainee, circulaire, ou avec sentinelle pour simplifier les cas limites.

Erreurs classiques

Oublier de liberer, reutiliser un noeud apres free, perdre la tete.