Tableaux et listes chaînées

Les tableaux et les listes chaînées sont les deux principales méthodes pour stocker une séquence ordonnée d'éléments : les tableaux les placent en mémoire contiguë pour un accès indexé en temps constant, tandis que les listes chaînées les relient via des pointeurs pour une insertion et une suppression peu coûteuses.

Definition

Un tableau stocke les éléments dans des emplacements mémoire contigus indexés par position, permettant un accès aléatoire en temps constant ; une liste chaînée stocke les éléments dans des nœuds séparés, chacun contenant une référence au nœud suivant (et éventuellement précédent), permettant une insertion ou une suppression en temps constant étant donné une référence de nœud.

Scope

Ce sujet aborde les structures linéaires basées sur des séquences et les types de données abstraits qui en découlent — les tableaux statiques et dynamiques, les listes chaînées simples et doubles, ainsi que les types de données abstraits (TDA) de pile et de file d'attente. Il compare leurs coûts d'accès, d'insertion et de suppression, traite du redimensionnement des tableaux dynamiques et de son analyse amortie, et explique les conséquences de l'organisation de la mémoire, telles que la localité de cache. Il exclut les structures associatives et hiérarchiques couvertes par les tables de hachage et les arbres de recherche.

Core questions

• Quand le stockage contigu (tableau) surpasse-t-il le stockage lié par pointeurs (liste) ?
• Comment un tableau dynamique réalise-t-il une insertion (append) en temps constant amorti malgré des redimensionnements occasionnels ?
• Quels sont les compromis de coût entre les tableaux et les listes chaînées pour l'insertion, la suppression et l'accès ?
• Comment les piles et les files d'attente sont-elles implémentées à partir de ces structures ?
• Comment l'organisation de la mémoire affecte-t-elle les performances réelles via le comportement du cache ?

Key concepts

• mémoire contiguë
• accès indexé
• redimensionnement de tableau dynamique
• listes chaînées simples et doubles
• piles (LIFO)
• files d'attente (FIFO)
• coût amorti
• localité de cache

Key theories

Accès aléatoire versus liaison séquentielle

Les tableaux permettent un accès indexé en O(1) mais une insertion ou suppression en O(n) au milieu, tandis que les listes chaînées permettent une insertion/suppression en O(1) étant donné un nœud, mais un accès par position en O(n) ; le bon choix dépend du mélange d'opérations.

Croissance amortie des tableaux dynamiques

Un tableau dynamique qui double sa capacité lorsqu'il est plein effectue des copies occasionnelles en O(n) mais s'amortit à O(1) par ajout sur toute séquence d'opérations, par la méthode agrégée ou potentielle.

Clinical relevance

Les tableaux et les listes constituent le substrat de presque tous les programmes : les tableaux dynamiques implémentent les types de liste/vecteur par défaut dans la plupart des langages, les files d'attente sont à la base de l'ordonnancement et de la recherche en largeur, les piles sont à la base de la gestion des appels de fonctions et de l'évaluation des expressions, et le compromis entre tableau et liste est une décision de conception pratique courante qui affecte les performances.

History

Les tableaux figurent parmi les premières structures de données, présentes dans les premiers langages de programmation, et les listes chaînées ont été introduites pour le traitement symbolique et de listes (notamment dans l'IPL de Newell, Shaw et Simon, puis Lisp) à la fin des années 1950. Le traitement systématique de Knuth dans The Art of Computer Programming a établi leur analyse canonique.

Key figures

• Donald Knuth
• Robert Sedgewick

Seminal works

• knuth1997vol1
• cormen2009

Frequently asked questions

Pourquoi utiliser une liste chaînée si les tableaux permettent un accès aléatoire rapide ?

Les listes chaînées permettent l'insertion ou la suppression en temps constant étant donné une référence à un nœud, sans déplacer d'autres éléments, ce que les tableaux ne peuvent pas faire au milieu. Elles sont utiles lorsque la séquence change fréquemment et que l'accès aléatoire positionnel n'est pas nécessaire.

Pourquoi les ajouts (appends) aux tableaux sont-ils considérés comme étant en temps constant si le redimensionnement copie tout ?

Le redimensionnement se produit rarement car la capacité double généralement, de sorte que le travail total de copie sur n ajouts est proportionnel à n. Réparti sur tous les ajouts, cela donne un coût constant amorti par ajout, même si les redimensionnements individuels sont en O(n).