Ce sont des exemples du monde réel de lorsque les Listes Liées devraient être utilisés?
Un autre programmeur a mentionner qu'ils n'ont pas trouvé un cas d'utilisation pour l'utilisation d'une liste liée structure de données dans tout logiciel professionnel dans sa carrière. Je ne pouvais pas penser à des bons exemples sur le dessus de ma tête. Il s'agit surtout de C# et Java developer
Quelqu'un peut-il donner quelques exemples où c'était la bonne structure de données pour résoudre un même monde réel problème?
Connexes: Ce qui est pratique dans le monde réel, l'exemple de la Liste chaînée?
- Si vous avez réellement lu les deux questions, il n'est pas dupe du tout. La question liée à une veut un monde réel analogie à une liste liée, cette question veut des exemples du monde réel de l'aide de l'un.
Vous devez vous connecter pour publier un commentaire.
D'un exemple réel serait une file d'attente FIFO. Un simple tableau liste est assez mauvais pour que, parce que vous devez ajouter à une extrémité et retirez à l'autre extrémité, et l'une de ces opérations sera en O(n) avec une matrice à base de liste (sauf si vous ajoutez plus logique de travailler avec un début ET la fin de l'index), alors que les deux sont en O(1) avec une liste, sans effort supplémentaire.
Listes liées offrent plusieurs avantages par rapport à données comparables structures comme statique ou dynamique de l'expansion des tableaux.
Tout lieu où ces avantages seraient considérablement précieux pour un programme (et les inconvénients d'une LinkedList étaient négligeables) serait un lieu d'utiliser une LinkedList.
Les Listes chaînées (jumelé avec une table de hachage) sont vraiment utiles pour LRU Caches.
Chaque Get doit frapper un nœud à l'avant de la liste, une opération qui est vraiment bon marché avec les listes chaînées.
Intrusive listes chaînées sont intéressants bêtes pour le développement d'un jeu. Par exemple, il est assez courant d'avoir un intrusive individuellement ou à double liaison "rendu" de la liste:
classe Restituable /* ou Objet de classe, quel que soit */ { //... Restituable * m_pNext; Restituable * m_pPrev; //ou pas, si liée individuellement //... }Comme Renderables venir dans et hors de l'existence, ils peuvent s'inscrire eux-mêmes avec cette liste-sans provoquer aucune allocation de la mémoire. Si leur rendre la profondeur ou la priorité est changé, ils peuvent retirez et réinsérez eux-mêmes, etc.
Quand vient le temps de rendu, tout ce que vous devez faire est de trouver la tête de la liste et zip à travers, l'appel de la méthode appropriée!
(Il y en a, bien sûr, de nombreuses variations sur ce thème, avec de multiples listes séparées, etc. Et vous n'avez pas besoin d'avoir un intrusive liste pour faire ce travail, je viens de trouver l'intrusion de ceux intéressant.)
Les piles et les files d'attente sont très clairement des exemples de listes liées, mais que d'autres ont déjà parlé, je voudrais ajouter quelques autres exemples:
DOM magasins de nœuds que les listes liées. Un simple échantillon de javascript qui est vraiment le même dans toutes les langues:
J'imagine qu'un développeur java a trouver XML à un certain point.
Les arbres sont un autre de bons exemples de listes liées, même si elles ne sont pas simples à une seule dimension chers. Quelqu'un qui a fait beaucoup de développement java est sans doute à travers les Arborescences et TreeSets.
L'ensemble de la discussion semble un peu ridicule à moi. Les listes chaînées sont fondamental de la structure de données qui est utilisé partout. La seule raison que l'on peut penser que il/elle n'a pas venir à travers eux, c'est que vous n'avez pas vraiment à vous soucier de la mise en œuvre de structures de données dans l'actuel haut niveau de langues, mais bien sûr ils sont toujours là.
Ils se produisent tout le temps, partout où un objet a une propriété qui pointe vers un autre objet du même type. Dans le CLR, les exceptions forme d'une liste liée, en raison de la
InnerExceptionpropriété.Un immuable liste chaînée est une très précieux de la structure, puisque vous pouvez "partager structure' avec d'autres listes avec la même queue. La plupart des langages fonctionnels comprennent immuable liées type de liste comme l'un de leurs fondamentaux des structures de données, et ces types sont utilisés partout dans l'endroit.
Que peut-être le meilleur du monde réel exemple .Net envisager la MultiCastDelegate.
Listes liées mises en œuvre dans cette voie, où la liste de chaînage aspect est soutenu directement dans le type plutôt que comme un récipient séparé, peut être extrêmement puissant et efficace. Ils viennent toutefois avec une variété de compromis.
Un plus évident est la duplication de code, vous devez faire cuire cette logique de chaque type. Des Techniques telles que l'extension d'une classe de base fournissant le pointeur sont désordonnées (vous perdez taper fort sans les génériques) et souvent inacceptable d'un point de vue des performances.
Une autre est que vous êtes limité à une mise en œuvre par type. Vous ne pouvez pas faire une seule structure liée à un doublement liés l'un sans l'insertion d'un champ supplémentaire dans chaque instance et la mise à jour de toutes les parties du code.
J'ai écrit un BIOS extension (en gros un pilote de périphérique pour un BIOS, écrit en assembleur) pour un contrôleur hôte USB. -- La mise en œuvre de haut niveau de l'apparence abstraite, structure de données, comme une liste liée dans l'assemblée n'est pas aussi difficile qu'il y paraît. -- Le contrôleur serviced demandes d'e/S pour le clavier et disque à l'aide d'une liste liée de paquets dans la mémoire principale. J'ai maintenu une piscine de libre paquets dans une autre liste liée. Effectuer des e/S ont consisté essentiellement à l'accaparement des gratuitement un paquet à partir du début de la liste libre, la configuration du paquet, en ajoutant le paquet de l'appareil de la liste, et de rajouter le paquet pour le début de la gratuite de la piscine lors de l'I/O terminé. Les listes chaînées sont rapides comme l'éclair pour se déplacer les objets de ce genre, surtout lorsque les objets sont grands, car les objets n'ont pas réellement de se déplacer. Seulement leurs pointeurs doivent être mis à jour.
Un tableau basé sur la file d'attente aurait requis:
Donc, les listes chaînées sont une belle façon de mettre en œuvre un arbitrairement long first-in-first-out de la file d'attente des objets de grande taille.
Autre chose que d'être prudent, c'est que pour les petits objets ou où vous allouer des objets à partir d'un classique tas au lieu d'un personnalisé gratuit piscine, les tableaux peuvent être plus rapides, car la copie n'est pas vraiment ce lent si cela ne se fait pas souvent, et la répétition de l'allocation dans le tas qu'une liste liée exigerait que chaque fois qu'un nouvel élément est ajouté lentement.
Bien sûr, vous pouvez simuler et mesurer votre scénario avec quelques jetable code de test pour trouver la réponse. Je tiens à lancer des boucles de quelques millions de fois avec des listes et des tableaux, avec les petits et les grands objets, et de temps combien de temps prend en temps réel. Parfois, vous serez surpris.
Comme l'a dit déjà lié listes sont très utiles lorsque vous avez besoin d'insérer et de supprimer des éléments.
Par exemple pour aider à déboguer la gestion de la mémoire dans mon code j'ai récemment implemeneted d'une liste de liens entre tous mes refrence objets comptés qu'à la fin du programme (lorsque les références devraient tous avoir frappé zéro et supprimé les objets) j'ai pu voir exactement ce qui était encore à gauche, useually résultant en moi d'être en mesure de trouver un seul objet à la racine du problème.
Disponible met en œuvre quelque chose de similir avec une énorme liste liée entre presque tous lors de sa construction avec le débogage.
De réponse pour le tag "Structures de Données", à un bas niveau tels que le montage, les listes chaînées sont un moyen idéal pour stocker la variable longueur des listes d'autres structures de données. Il n'y a pas de frais généraux pour le maintien de la liste de longueur ou à la fin, et qu'il n'est besoin de taille fixe les éléments de la liste. La dernière raison s'applique également à un langage de haut niveau.
Liste chaînée est l'essentiel de la structure de données pour La Danse Des Liens, qui est la technique utilisée pour mettre en œuvre efficacement Algorithme X, qui est un retour en arrière algorithme pour trouver toutes les solutions pour la NP-complet exact couverture problème, à qui de nombreux problèmes sont naturellement réductible.
Quelques exemple de l'unique liste liée.
par un GPS est un exemple d'Ajouter et de Supprimer des opérations de la carte de données.
Quelques exemples de double liste chaînée.
Comme daustin777 le souligne, les listes chaînées sont tout autour de vous et vous ne pouvez pas le savoir. Mais l'aspect pratique de la question, c'est qu'ils permettent pour certains assez opérations de base à effectuer avec une relative facilité et la flexibilité. Par exemple, de ne pas trier, il vous suffit de changer les pointeurs de autour de. Besoin d'insérer ou de supprimer à des emplacements arbitraires? Insérer ou de retirer votre pointeurs à l'intérieur de la liste. À itérer en avant et en arrière ... liste liée. Tout n'est pas précisément une entreprise exemple, j'espère que cela clarifie il vous suffit de l'appliquer à votre propre monde réel des affaires cas.
Si je peut répondre à cette question d'une manière un peu différente que les autres ont, dernièrement, j'ai été à l'aide de listes liées à organiser des listes de musique. Les listes de fournir un excellent moyen de stocker et trier musique par artiste, chanson, album, même classements ou de la durée de la chanson. La mienne est une liste doublement chaînée, mais je pouvais voir qu'il est applicable avec une seule liste liée aussi bien. Des listes de courses serait bien, et si vous êtes dans le trouble obsessionnel-compulsif comme ma mère, vous pouvez facilement organiser elle être allée et d'aliments surgelés en dernier!
Si l'on inclut les piles et les files d'attente, ce qui est évident pour les files d'attente d'impression de la file d'attente ou une liste de lecture musicale (listes dans tous les sens, sont bien évidemment).
Les piles et les Files d'attente sont des exemples de listes liées.
Pour des problèmes où le nombre maximum de nœuds sont limitées à 100 ou au-dessous ou alors, les listes chaînées sont une solution raisonnable. La même chose peut être vrai des choses comme le tri à bulles et d'autres choses qui sont censés être sous-optimale.
Liste liée pros:
Liste liée inconvénients:
Hors de ma tête, j'aimerais mettre en œuvre les piles, les files d'attente et messagepumps à l'aide de listes chaînées. Je voudrais aussi mettre en œuvre une datatree de l'utilisation de multi-référence listes liées rapide pour l'insertion /suppression.