La liste liée est-elle un ADT ou est-ce une structure de données, ou les deux?

Question

Si j'utilise la définition standard d'un type de données abstrait comme une boîte noire qui fournit certaines fonctions pour gérer une collection de données, une liste chaînée correspond à cette description:

Un conteneur qui offre des fonctions ajouter (x) et obtenir (i) (entre autres) qui peut être utilisé pour maintenir une liste d'objets.

Mais quand vous posez la question, quelle est la complexité temporelle de ces opérations, alors vous vous rendez compte que cela dépend de la façon dont ce conteneur est mis en œuvre:

Si vous venez de maintenir en interne un lien vers le noeud de tête, ce qui précède deux opérations se dérouleront en heure O (n). Si vous maintenez en plus un lien vers le noeud final, vous aurez le temps O (1) sur les deux. Par conséquent, ma question est la suivante: à des fins d'apprentissage, considérez-vous une liste liée comme un ADT ou une structure de données? Cette question est survenue lorsque j'essayais de mettre en œuvre un ADT Stack du Manuel de conception d'algorithmes de Skiena, et je lisais comment la performance de ses méthodes put (x) et get() dépend de la structure de données choisie. Mettre en œuvre. Le livre dit que dans ce cas, peu importe si vous choisissez un tableau ou une structure de données de liste liée pour implémenter cet ADT, ils offrent tous les deux des performances similaires.

Mais le font-ils? Cela ne dépend-il pas de la façon dont cette liste de liens est implémentée? Il y a plusieurs façons d'implémenter la liste chaînée elle-même, cela ne fait-il donc pas d'elle une autre ADT?

Answer 1

de Wikipédia sur ADT: In computing, an abstract data type (ADT) is a mathematical model for a certain class of data structures that have similar behavior donc, liste chaînée est un ADT, et chaque ADT est également une structure de données, la liste est à la fois liées entre elles.

EDIT:
Cependant, notez que seul lié liste et liste doublement chaînée, les deux ont les mêmes opérations et la même complexité de ces opérations, ils sont donc à la fois une liste chaînée ADT et nous ne distinguons pas entre eux comme ADT concerné. Mais ce sont des structures de données différentes!

Answer 2

Une liste liée elle-même n'est pas abstraite, c'est concret. C'est considéré comme une structure de données. La complexité temporelle de l'accès aux données dans une liste liée dépend de l'élément auquel vous accédez et du nombre d'éléments présents dans la liste, car vous devez les parcourir pour accéder à l'élément souhaité.

http://en.wikipedia.org/wiki/Linked_list

Answer 3

La liste chaînée est un ADT.

Quand vous parlez de structures de données, vous avez essentiellement - Stacks, et listes (Queues Ne pas appeler cette liste chaînée), les arbres, etc.

Lorsque vous interroger sur la liste chaînée, il est un ADT. Un type de données abstrait. Donc, indépendamment, cela n'a aucune valeur. Mais lorsque vous souhaitez implémenter une liste ou une pile ou une file d'attente, vous devez utiliser une liste liée ou un tableau.

Il est abstrait car il comporte plusieurs opérations qui peuvent lui être associées au fur et à mesure des besoins et selon le type d'implémentation.

Liste dans la bibliothèque de modèles standard de C et C++ implémentent la liste à double liaison. La liste liée a toujours été utilisée dans la mise en œuvre des listes et c'est pourquoi elle est devenue synonyme de structures de données List.