Structures de données linéaires

Les structures linéaires organisent les éléments en séquence, mais leur représentation et les opérations permises diffèrent.

Comparaison

Structure	Accès indexé	Insertion/suppression en fin	Insertion/suppression à une position interne connue	Compromis principal
Tableau dynamique	$O(1)$	$O(1)$ amorti	décalages en $O(n)$	localité et accès aléatoire
Liste simplement chaînée	$O(n)$	insertion en $O(1)$ avec une queue ; suppression de la queue en $O(n)$	$O(1)$ si le prédécesseur est connu	indirection et surcoût des nœuds
Liste doublement chaînée	$O(n)$	$O(1)$ avec les extrémités	$O(1)$ si le nœud est connu	un lien supplémentaire par nœud
Pile	hors contrat	empiler/dépiler au sommet	interdit par l’interface	discipline LIFO
File	hors contrat	enfiler/défiler aux extrémités opposées	interdit par l’interface	discipline FIFO

Trouver un nœud ou une position interne est distinct de sa modification. Dire que « l’insertion dans une liste chaînée est en $O(1)$ » suppose implicitement que le nœud ou le prédécesseur concerné est déjà disponible.

Règles de sélection

• Préférez un tableau dynamique pour les séquences générales et les tâches dominées par l’itération.
• Préférez les nœuds chaînés lorsque l’identité stable des nœuds et les raccordements locaux dominent.
• Exposez une pile ou une file lorsque l’accès restreint communique mieux un invariant algorithmique qu’une liste générale.
• Employez un tampon circulaire pour une file bornée au stockage prévisible.

En Python, list est un tableau dynamique de références d’objets ; collections.deque prend en charge efficacement les opérations aux deux extrémités.

Choisir selon la prochaine opération

Pour atteindre directement le centième élément, lisez les tableaux. Pour raccorder à côté d’un nœud déjà détenu par l’algorithme, lisez les listes chaînées : connaître une position numérique ne fournit pas ce nœud. Pour apparier le dernier délimiteur encore ouvert, utilisez une pile. Pour traiter les arrivées dans l’ordre, utilisez une file.

Ici, $n$ désigne le nombre d’éléments stockés ; déplacer un emplacement ou suivre un lien est supposé constant. Le coût amorti borne toute une séquence d’opérations, redimensionnements occasionnels compris ; ce n’est pas une moyenne sur des entrées aléatoires. Les lignes pile et file décrivent des interfaces, dont les coûts d’implémentation se lisent séparément. Ces comparaisons concernent des conteneurs séquentiels en mémoire, pas la livraison concurrente de messages ni l’indexation sur disque.

Source

• Open Data Structures : interfaces

Mes lectures · Les notes ouvertes sont mémorisées dans ce navigateur.