Qu'est-ce qu'une liste chaînée simple et quand l'utiliser?

Question

Accepted Answer

Une **liste chaînée simple** est une chaîne de **nœuds**, où chaque nœud contient une valeur et un pointeur vers le **nœud suivant**. Contrairement à un array, les nœuds ne sont pas contigus — ils peuvent se situer n'importe où en mémoire, connectés par des références.

## Structure

```text
head
  |
  v
[10|*]--->[20|*]--->[30|null]
 val next   val next  val next
```

## Exemple

```python
class Node:
    def __init__(self, val):
        self.val = val
        self.next = None

# Insert at head -> O(1)
def push_front(head, val):
    node = Node(val)
    node.next = head     # point new node at old head
    return node          # new head

# Search -> O(n): must walk the chain
def find(head, target):
    cur = head
    while cur:
        if cur.val == target:
            return cur
        cur = cur.next
    return None
```

## Complexité

| Opération | Temps |
|---|---|
| Insertion/suppression au début | O(1) |
| Accès par index | O(n) |
| Recherche | O(n) |

## Compromis

- **Avantages:** O(1) pour insérer/supprimer au début ; croissance sans réallocation ; aucune capacité gaspillée.
- **Inconvénients:** pas d'accès aléatoire ; chaque nœud porte une surcharge de pointeur ; mauvaise localité spatiale (mémoire dispersée).

## Pourquoi c'est important

Les listes chaînées excellent quand vous ajoutez ou supprimez fréquemment aux extrémités et rarement au milieu — par exemple, comme base de piles, files et listes d'adjacence.

Comprendre la manipulation de pointeurs ici est fondamental pour les arbres, les graphes et de nombreux problèmes d'entretien.

Opération	Temps
Insertion/suppression au début	O(1)
Accès par index	O(n)
Recherche	O(n)