mettre en œuvre liste liée à l'aide du tableau - avantages & inconvénients

Je sais comment mettre en œuvre liste liée à l'aide du tableau. Par exemple
nous définissons une structure comme suit:

struct Node{
    int data;
    int link;
}

"données" magasins de l'info et de "lien" stocke l'index dans le tableau de nœud suivant.

Quelqu'un peut-il me dire quel est l'avantage et l'inconvénient de la mise en œuvre d'une liste liée à l'aide du tableau par rapport à "ordinaire" liste chaînée? Toutes suggestions seront appréciées.

OriginalL'auteur yvetterowe | 2012-05-07

  1. 10

    Si vous sauvegardez une liste liée à un tableau, vous vous retrouverez avec les inconvénients des deux. Par conséquent, ce n'est probablement pas une très bonne façon de le mettre en œuvre.

    Immédiat inconvénients:

    1. Vous aurez de l'espace mort dans le tableau (les entrées qui ne sont pas actuellement utilisés pour les éléments) de prendre de la mémoire
    2. Vous aurez à garder la trace des entrées gratuites - après quelques insertions et suppressions, ces entrées gratuites pourrait être n'importe où.
    3. L'aide d'un tableau imposer une limite supérieure sur la taille de la liste chaînée.

    Je suppose que certains avantages sont:

    1. Si vous êtes sur un système 64 bits, votre "pointeurs" prendra moins de place (si l'espace supplémentaire requis par des entrées gratuites sans doute l'emporte sur cet avantage)
    2. Vous pourriez serialise le tableau sur le disque et de le lire avec un mmap() appeler facilement. Cependant, vous feriez mieux d'utiliser un certain type de protocole de la mémoire tampon pour la portabilité.
    3. Vous pourriez faire quelques garanties sur les éléments de la matrice étant proches les uns des autres dans la mémoire.

    OriginalL'auteur Timothy Jones

  2. 2

    Quelqu'un peut-il me dire quel est l'avantage et l'inconvénient de la mise en œuvre de la liste liée à l'aide du tableau par rapport à "ordinaire" liste chaînée?

    listes liées sont les suivantes complexité:

    • contre x xs : O(1)
    • ajouter n m : O(n)
    • index i xs : O(n)

    si votre représentation utilise une stricte contigu tableau, vous avez différentes complexité:

    • contre nécessitera la copie de l'ancien tableau: O(n)
    • append besoin de copier les deux tableaux dans un nouvel espace contigu: O(n + m)
    • index peut être mis en œuvre comme l'accès au tableau: O(1)

    Qui est, une liste liée API mises en œuvre en termes de tableaux va se comporter comme un tableau.

    Vous pouvez atténuer un peu cela en utilisant une liste chaînée ou de l'arbre de la stricte tableaux, conduisant à des cordes ou du doigt les arbres ou paresseux séquences.

    Il semble que l'insertion est O(1) toujours, et pas de O(n), de sorte qu'il n'est pas exactement comme un tableau.

    OriginalL'auteur Don Stewart

  3. 0

    pile dans l'implémentation de deux façon.
    d'abord à l'aide du tableau et le second est à l'aide de liste liée.

    certains disadvatages en utilisant la matrice de la plupart des programmeurs utilisent liste liée dans la pile de mettre en œuvre.

    première est pile à l'aide de liste liée d'abord de ne pas déclarer la taille de la pile et ne se limite pas magasin de données dans la pile. la deuxième est liée liste à pointeur essai de déclarer et de l'utiliser.

    un seul pointeur utiliser dans la liste chaînée. son appelé pointeur supérieur.

    pile lifo l'utilisation d'une méthode. mais certains inconvénients liés liste du programme de mise en œuvre.

    Plus de programmeur utilisation de la pile mise en place de l'aide aimé liste.

    OriginalL'auteur Solomon Bindavid

  4. 0

    À l'aide de la Matrice de mise en œuvre, vous pouvez avoir séquentielle & un accès plus rapide à des nœuds de la liste, d'autre part,
    Si vous implémentez la liste Liée à l'aide de pointeurs, vous pouvez avoir accès aléatoire à des nœuds.
    Tableau de mise en œuvre est utile lorsque vous traitez avec des fixe pas. Éléments parce que le redimensionnement d'un tableau est cher comme la mesure de la performance est concerné, parce que si vous devez insérer/supprimer des nœuds à partir du milieu de la liste, il vous faut déplacer chaque nœud afterwise.
    Contrairement à cela, Vous devez utiliser le pointeur de la mise en œuvre quand vous ne savez pas. de nœuds que vous voulez, en tant que telle liste peut croître ou réduire efficacement & vous n'avez pas besoin de déplacer les nœuds, il peut être fait simplement référence à & référencement des pointeurs.

    OriginalL'auteur Shashikant Mitkari