Tableaux et listes

#Tableaux et listesCopier le lien

Modèles séquentiels: accès aléatoire vs itératif, coûts d’insertion/suppression et itérations.

#Tableaux dynamiquesCopier le lien

• Accès indexé O(1) amorti, bonne localité mémoire.
• Insertion/suppression au milieu: O(n) (décalage).
• Redimensionnement amorti (facteur ×2).

#Listes chaînéesCopier le lien

• Insertion/suppression en tête O(1), au milieu O(1) si pointeur connu.
• Accès par index O(n), localité faible.

#ExemplesCopier le lien

1# Insertion triée dans une liste chaînée (pseudo‑code)2def insert_sorted(head, x):3    if not head or x < head.val:4        return Node(x, head)5    cur = head6    while cur.next and cur.next.val < x:7        cur = cur.next8    cur.next = Node(x, cur.next)9    return head

#Animation: insérer un élémentCopier le lien