RIP Linked List - INRIA - Institut National de Recherche en Informatique et en Automatique Accéder directement au contenu
Pré-Publication, Document De Travail (Preprint/Prepublication) Année : 2023

RIP Linked List

Résumé

Linked lists have always been an excellent teaching tool in programming. The question arises as to whether it is really worthwhile to use linked lists in the programs we run on a daily basis. It seems that in most cases array-based data structures are more advantageous, both in terms of memory space and, most importantly, in terms of execution speed. While it is easy to calculate the complexity of the operations, what about the actual execution efficiency? In this paper we try to answer this question by introducing a new benchmark. Our survey compares several linked-list implementations with some array-based implementations. We also propose a new array-based data structure that is well suited for list operations.
Les listes chaînées constituent depuis toujours un excellent exercice d'apprentissage de la programmation. En ce qui concerne l'utilisation des listes chaînées dans les programmes que nous utilisons au jour le jour, la question se pose de savoir s'il est vraiment rentable ou non d'utiliser des listes chaînées. Il semble que, dans la plupart des cas, les structures de données à base de tableaux sont plus avantageuses à la fois en terme de place mémoire, mais aussi et surtout en terme de vitesse d'exécution. Même s'il est facile de calculer la complexité des opérations, qu'en est-il vraiment de l'efficacité en cas d'exécution réelle? Ici, nous cherchons à répondre à cette question en introduisant un nouveau benchmark. Notre étude confronte différentes implantation de liste chaînée avec quelques implantations à base de tableaux. Nous proposons également une nouvelle structure d'implantation à base de tableaux bien adaptée aux opérations propres aux listes.
Fichier principal
Vignette du fichier
RIP-link-en.pdf (215.16 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
licence : CC BY - Paternité

Dates et versions

hal-04124714 , version 1 (10-06-2023)
hal-04124714 , version 2 (29-03-2024)

Licence

Paternité

Identifiants

Citer

Benoît Sonntag, Dominique Colnet. RIP Linked List. 2023. ⟨hal-04124714v1⟩
12 Consultations
28 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More