Microsoft demande: liste simple ou double liste? Quels sont les avantages et les inconvénients de l'utilisation de chacun?

Je me suis posé cette question et j'ai mes propres paroles, mais je ne suis pas vraiment sûr de ce qu'-à-dire sur les inconvénients et les avantages? Microsoft a demandé cette question à l'un de ses candidats.

Individuellement liée liste vous permet d'aller de direction. Considérant que la liste doublement chaînée a deux sens suivant et précédent.

Voici une photo de bonne qualité qui attire le Seul et Doublement LinkedLists.

Microsoft demande: liste simple ou double liste? Quels sont les avantages et les inconvénients de l'utilisation de chacun?

Cependant, comment expliquez-vous les avantages et les inconvénients de ces éléments dans la plus ordonnée?

source d'informationauteur Tarik

  1. 14

    Je me suis posé cette question et j'ai mes propres paroles, mais je ne suis pas vraiment sûr de ce qu'-à-dire sur les inconvénients et les avantages?

    Il s'agit de l'utilisation. Il y a un compromis ici.

    Seule liste liée est plus simple en termes de mise en œuvre, et a généralement une plus petite capacité de mémoire qu'il a seulement besoin de garder l'attaquant membre de référencement en place.

    Liste doublement chaînée est plus efficace itération, surtout si vous devez toujours effectuer une itération à l'inverse (ce qui est horriblement inefficace avec une seule liste chaînée), et les plus efficaces de suppression de nœuds spécifiques.

    Cela étant dit, puisque vous avez ce tag .NET, double listes liées ont également l'avantage d'être directement dans le cadre de la forme de la LinkedList<T> classe. Cela donne un grand avantage, c'est que vous n'avez pas à mettre en œuvre, tester et maintenir votre propre classe de collection.

  2. 10

    Que cette question a déjà été répondu, je suis de toute façon pas satisfait de la réponse (n'en déplaise signifié), voici donc comment je pourrais répondre à ça:

    Qu'à utiliser Individuellement ou par liste Doublement chaînée dépend de ce que vous voulez atteindre et des limitations du système, le cas échéant.

    Liste liée individuellement:

    Avantages: Simple dans sa mise en œuvre, nécessite relativement moindre de mémoire pour le stockage, si vous avez besoin de supprimer/insérer () en regard du nœud – suppression/insertion est plus rapide.

    Inconvénients: Ne peut pas être répétées dans le sens inverse, la nécessité de maintenir une poignée pour le nœud de tête de la liste d'autre, la liste sera perdu dans la mémoire. Si vous êtes à la suppression de nœud précédent ou de l'insertion au nœud précédent, vous aurez besoin de parcourir la liste de tête de nœud précédent pour être en mesure de mener à bien ces opérations, – O(N) fois.

    --Donc, ce devrait être utilisée lorsque vous avez moins de mémoire et votre objectif principal est l'insertion/délétion et pas à la recherche d'éléments.

    Liste à double liaison:

    Avantages: Peut être réitéré en avant, ainsi que le sens inverse. En cas de besoin de supprimer nœud précédent, il n'est pas nécessaire de parcourir de la tête de nœud, le nœud supprimé peut être trouvé à partir de"."pointeur.

    Contre: Relativement complexe à mettre en œuvre, nécessite plus de mémoire pour le stockage (1 ‘."pointeur par nœud). Les Insertions et les suppressions sont relativement plus de temps (attribution/réaffectation ‘."pointeur pour les noeuds voisins)

    --Ce doit être utilisée lorsque vous avez peu ou pas de limitations sur la mémoire, et votre objectif principal est de rechercher pour les éléments.

    Si il y en a plus des avantages et des inconvénients, s'il vous plaît n'hésitez pas à ajouter, réponse dans les commentaires. Merci!

  3. 4

    Alors que seule liste liée utilise moins de mémoire par nœud (un pointeur vs deux pointeurs), son opération de suppression est O(N) si tout ce que vous avez est un pointeur vers le nœud que vous souhaitez supprimer, tandis que la double liaison suppression est O(1). Il y a une astuce peu connue qui vous permet de supprimer à partir d'une liste liée individuellement dans O(1)mais la liste doit être circulaire pour que cela fonctionne (déplacer le contenu de la next dans le courant, et de supprimer next).

    Doublement lié listes peuvent être utilisés dans des lieux où liée individuellement des listes de fonctionne pas (un doublement clos de la file d'attente), mais ils nécessitent un peu plus de "ménage", et sont légèrement moins efficace sur les insertions comme résultat.

  4. 2

    Avantage de la double liste chaînée: Peut parcourir dans les deux sens

    Avantage de la simple liste chaînée: Moins de ménage à faire sur update/insert/delete, moins l'utilisation de la mémoire.

  5. 2

    Eh bien, cela dépend de la situation. Si vous avez besoin d'être en mesure d'obtenir rapidement les deux précédentes ainsi que l'élément suivant à partir d'un élément donné ensuite une liste doublement chaînée est le meilleur.

    Si vous avez seulement besoin d'obtenir l'élément suivant à partir d'un élément donné, puis une seule liste liée est assez bon.