Est Lié Liste d'ADT ou est-il une Structure de Données, ou les deux?

Si j'utilise la définition standard d'un Type Abstrait de Données comme une boîte noire qui fournit des fonctions pour gérer une collection de données, une Liste Liée correspond à cette description:

Un conteneur qui offre des fonctions add(x) et get(i) (entre autres) qui peuvent être utilisés pour maintenir une liste d'objets.

Mais quand vous posez la question, qu'est-ce que le temps de la complexité de ces opérations, alors vous vous rendez compte qu'il dépend de la façon dont ce conteneur est mis en œuvre:

Si vous venez en interne conserver un lien vers le nœud de tête, ces deux opérations s'exécuter en O(n) fois. Si vous avez en outre de maintenir un lien à la queue nœud, vous obtiendrez O(1) fois sur deux.

Donc ma question est, à des fins d'apprentissage, considérez-vous une Liste Liée à un ADT ou une Structure de Données?

Cette question est venu à propos, quand j'ai essayé de mettre en œuvre une Pile ADT de Skiena l'Algorithme du Manuel de Conception, et a été la lecture sur la façon dont le rendement de il est mis(x) et get() méthodes dépendra de la Structure de Données est choisi de la mettre en œuvre. Le livre dit, dans ce cas, il n'a pas tellement d'importance si vous choisissez un tableau ou d'une liste liée structure de données pour mettre en œuvre cette ADT, ils offrent des performances similaires.

Mais le font-ils? N'est-ce pas dépendre de la façon dont cette liste de liens est mis en œuvre? Il existe de nombreuses façons de mettre en œuvre la liste liée elle-même, n'est pas que le fait de faire juste une autre ADT lui-même?

OriginalL'auteur dvanaria | 2011-06-30

  1. 7

    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, la liste chaînée est un ADT, et tous les ADT est également une structure de données liée liste à la fois.

    EDIT:

    Toutefois, notez que liée individuellement-liste, et doublement la liste liée, les deux ont les mêmes opérations et les mêmes complexité de ces opérations, de sorte qu'ils sont à la fois une liste liée de l'ADT, et nous ne distinguons pas entre eux comme l'outil ADT concernés. Mais ils sont de différentes structures de données!

    OriginalL'auteur amit

  2. 2

    Liste chaînée est une ADT.

    Quand vous parlez des structures de données, vous avez des Piles, les Files d'attente et les Listes(N'appelez pas cette liste liée), les Arbres, etc.

    Lorsque vous êtes en questionnement sur Liste Liée, c'est un outil ADT. Un Type Abstrait De Données. De manière indépendante, il n'a pas de valeur. Mais quand vous voulez une Liste ou d'une Pile ou d'une File d'attente de mise en œuvre, vous devez utiliser une Liste ou d'une Matrice.

    Qu'elle est abstraite, car il a de multiples opérations qui peuvent y être associés en tant que de besoin et selon le type de mise en œuvre.

    Liste dans la Bibliothèque de modèles Standard de C et C++ en œuvre Liste Doublement chaînée. Liste liée a toujours été utilisé dans la mise en œuvre de Listes et c'est pourquoi il l'est devenu synonyme avec la Liste des structures de données.

    OriginalL'auteur Niraj Agarwal

  3. 0

    Une liste liée elle-même n'est pas abstrait, c'est du béton. Il est considéré comme une structure de données. Le temps de la complexité de l'accès aux données dans une liste, sera fonction de l'élément de votre accès et de combien d'éléments sont dans la liste, que vous avez à parcourir pour arriver à votre élément souhaité.

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

    une liste chaînée est une ADT. le "résumé" de Type Abstrait de Données ne fait pas référence au fait qu'il n'est pas en béton, mais plutôt le fait qu'il peut être utilisé sans savoir qu'est-ce que les données qui seront stockées dans celui-ci (par exemple, en C, les données seront conservées comme void*)
    My bad, a confondu ce type abstrait de données pour une classe abstraite.

    OriginalL'auteur MGZero