Suppression du k-ème index de la liste chaînée en une seule passe  Bienvenue à nouveau, avec un autre problème à résoudre ! Aujourd'hui, nous avons affaire à des listes chaînées et à la suppression de leurs éléments. Nous discuterons un peu de ce que sont les listes chaînées, nous en créerons une et verrons comment en supprimer des éléments.  Avant de commencer, les clauses de non-responsabilité habituelles :  Ces problèmes sont fournis par la merveilleuse newsletter Daily Coding Problem, à laquelle vous pouvez vous abonner  . Découvrez-le et essayez également de résoudre vos défis !   ici  Je ne suis pas un programmeur expert : Juste un gars qui aime partager ses clichés ! Si vous avez une solution meilleure ou plus rapide pour un algorithme, veuillez la soumettre dans les commentaires ! J'aimerais en savoir plus à ce sujet !  Assez de bruit ; passons au problème !  Ce problème a été initialement posé par Amazon      , supprimez le k-ème nœud de la fin de la liste et renvoyez la tête de la liste. Étant donné une liste chaînée et un entier k    est garanti inférieur à la longueur de la liste. k   Faites cela en un seul passage.  Bon alors, expliquons un peu ce qui se passe ici : on nous donne une liste chaînée et un élément d'index   à supprimer de la liste. Après cela, nous devrions retourner la tête de la liste chaînée. k  Enfin, nous devons faire tout cela en une seule passe, ce qui signifie que nous ne pouvons pas parcourir la liste plus d'une fois.  Nous sommes également assurés que l'indice   est   dans la liste, nous n'avons donc pas à vérifier qu'il dépasse la longueur réelle de la liste. k contenu  Nous allons utiliser Go pour construire l'algorithme aujourd'hui puisque sa syntaxe est géniale pour ce genre de travail, et en même temps, il reste assez simple à comprendre.  Commençons par le début : construire une simple liste chaînée.  La liste liée  Le concept derrière la liste chaînée est assez simple : c'est une liste faite d'objets (généralement appelés   ), et chaque nœud doit avoir au moins deux propriétés : une   (quelque chose réellement contenu par le nœud) et un   vers le nœud suivant. nodes valeur lien  Habituellement, un   est utilisé comme lien pour passer d'un nœud à un autre. pointeur  De plus, le premier nœud de la liste est généralement appelé la   de la liste, qui est également le nœud que le problème nous demande de renvoyer. tête  Voici un exemple graphique :   Le premier noeud à gauche est la tête de liste, qui contient sa valeur v₀ et un pointeur mémoire   qui redirige la liste vers le noeud suivant   Le nœud suivant   contiendra sa valeur et un pointeur   vers le nœud suivant, et ainsi de suite. P(n₁) n₁. n₁ P(n₂)  Le nœud final, bien sûr, n'aura rien vers lequel pointer, donc la valeur de son pointeur sera   . null  Voyons le code pour en créer un !   https://gist.github.com/NicolaM94/03bd49c6f65054a3440e8c9eef3c560c?embedable=true  Le code est assez simple : nous créons deux structures, une pour le nœud interne et une pour la liste chaînée.  Le nœud, comme nous venons de le voir, aura deux propriétés, à savoir la propriété   et la propriété   , qui contient un type   comme pointeur vers le nœud suivant. Value Next *Node  La liste chaînée, une structure pour « initialiser » la liste chaînée, qui n'aura qu'une seule propriété, la   de liste. Head  Après cela, nous initialisons simplement la liste dans la fonction principale et donnons à sa tête un nœud avec une valeur aléatoire de 10.  La clé derrière la compréhension de la liste chaînée est que maintenant   nœud             , qui contiendra le nœud suivant. Ce dernier nœud aura alors sa propriété   pour sauter sur le nœud suivant, et ainsi de suite. le Head , puisqu'il est de type Node , aura intrinsèquement une propriété Next Next  Tout sera plus clair une fois que nous aurons ajouté quelques nœuds à la liste, alors allons-y ! Nous avons deux options : soit nous le faisons manuellement, un travail   fastidieux, soit nous écrivons une méthode pour que la classe de liste chaînée ajoute des nœuds supplémentaires. Regardons ça! très  Ajout de nœuds : liste mutable déguisée  Même si vous avez peu d'expérience en programmation, dans presque tous les langages de programmation, l'un des premiers concepts dont vous devriez avoir entendu parler est la différence entre les listes   et   . modifiables immuables  Comme leur nom l'indique,   . Les immuables, au contraire, ont une   avec de nouveaux éléments. Mais pourquoi c'est comme ça? les listes modifiables sont des listes auxquelles vous pouvez manipuler et ajouter des éléments taille fixe et ne peuvent pas être ajoutés  Les listes immuables sont   , ce qui signifie que leurs éléments sont   : pour une liste de 3 éléments, si le premier élément est stocké à 0x00, alors le second sera à 0x01 et le dernier à 0x02. contiguës en mémoire stockés en mémoire séquentiellement  C'est pourquoi il est si rapide d'itérer sur un tableau fixe, une liste immuable ou un tuple en Python, car le processeur rappelle simplement les index de mémoire un par un.  D'autre part, les listes mutables ne sont contiguës en mémoire que lors de leur première initialisation : à ce stade, si des éléments sont ajoutés, ils ne seront plus séquentiels. Alors, comment pouvons-nous boucler sur eux?    , ce qui nous amènera l'élément to ajouté, et ainsi de suite.  Eh bien, parce que le dernier élément de la première initiation aura un pointeur que l'élément ajouté après lui Alors oui, les listes modifiables sont très souvent des listes chaînées déguisées !  Voyons maintenant le code :   https://gist.github.com/NicolaM94/9f587f4cd675dbbdb098327b22628284?embedable=true  Nous avons ajouté la méthode   aux méthodes de notre liste chaînée. Le processus pour ajouter un nœud se déroule comme suit : AddNode  Tout d'abord, nous stockons la valeur   dans une variable appelée  Head current  Ensuite, nous parcourons la liste chaînée en mettant à jour la variable   avec le nœud suivant à chaque fois, jusqu'à ce que le nœud suivant soit nul.  current Une fois que le nœud sur lequel nous nous trouvons actuellement a un pointeur nul, nous savons que nous sommes sur le dernier nœud de la liste.  Enfin, nous mettons à jour ce dernier nœud avec un nouveau nœud et une nouvelle valeur (le pointeur   de ce nouveau nœud sera mis à null si nous le laissons vide) Next  Graphiquement, ce processus ressemble à ceci :   Nous pouvons vérifier le bon fonctionnement de cette méthode dans la fonction principale, en imprimant les valeurs des nœuds dans la liste chaînée.  Suppression du nœud  Passons maintenant à la dernière partie et à la solution à notre problème : supprimer un nœud avec le bon index. Tout d'abord, que signifie supprimer un nœud d'une liste chaînée ? Si nous y réfléchissons,   , n'est-ce pas ? un nœud dans une liste chaînée n'existe que s'il est connecté au précédent  Par exemple, si nous donnons au n-1ᵗʰ une valeur   nulle, nous pouvons déconnecter la valeur nᵗʰ de la liste.  Next  Que faire si l'élément que nous voulons supprimer n'est pas le dernier ? Eh bien, on peut   !  dissocier l'élément en connectant le précédent au suivant  Donc pour supprimer l'élément kᵗʰ, il faut trouver l'élément k-1ᵗʰ et le lier au nœud k+1ᵗʰ. Nous devrons stocker le   . nœud précédent (k-1ᵗʰ)  Évidemment,   : essayer quelque chose comme   ne fera que générer une erreur. Compte tenu de cela cependant, nous pouvons considérer la tête de la liste comme l'index 0, et son nœud suivant comme l'index 1, et ainsi de suite, et nous pouvons également boucler sur les nœuds, comme nous l'avons fait auparavant. nous ne pouvons pas indexer directement la liste linkedlist[n]  Ce que nous pouvons faire alors, c'est implémenter un   pour garder une trace du nœud sur lequel nous nous trouvons ! compteur  Codons-le alors.   https://gist.github.com/NicolaM94/e08509c42ede81834ac65ff7aa65828b?embedable=true  Regardons la fonction   qui accepte un attribut   . Après cela, nous initialisons trois variables : RemoveNode index    , qui contiendra le nœud précédent previousNode    , qui contiendra le nœud sur lequel nous nous trouvons pendant la boucle current    , initialement égal à 0, qui maintiendra notre position sur la liste counter  Laissons de côté le premier bloc if pour le moment et concentrons-nous plutôt sur la boucle for. Nous commençons à boucler jusqu'à ce que notre variable   soit strictement inférieure à notre   : chaque boucle mettra alors  counter index à jour le nœud précédent avec celui en cours et passera à la mise à jour du nœud en cours et du compteur.    cela signifie que            Lorsque la boucle se casse, nous sommes juste sur le nœud avant notre index souhaité : nous avons juste besoin de mettre à jour le pointeur du nœud précédent, prev.Next , avec le nœud suivant dans la liste à partir de celui sur lequel nous sommes, qui sera current.Next . Enfin, nous retournons la tête de la liste chaînée.  Que se passe-t-il maintenant si l'index à supprimer est la tête, qui a un index de 0 ? La boucle ne démarrerait jamais car elle commencerait avec   et   , et la condition serait instantanément fausse. On peut gérer ce premier cas avec le bloc if en haut. counter = 0 index = 0  Fondamentalement, si l'index est 0, nous pouvons directement mettre à jour l'en-tête de la liste chaînée avec le nœud à côté, et le renvoyer. J'aimerais attirer votre attention, en particulier sur la ligne 31 : Go, comme dans de nombreux autres langages,   , ce qui signifie que la fonction conserve une   de l'objet passé,   . transmet les attributs aux functions par value copie et non l'objet réel que vous passez  Ce concept est clairement visible dans cet exemple :   package main import "fmt" func printMemoryAddress(value int) { fmt.Println(&value) } func main() { a := 10 fmt.Println(&a) printMemoryAddress(a) } // 0xc00010a000 // 0xc00010a008 // Program exited.  Nous créons une fonction pour imprimer l'adresse mémoire de la valeur passée en attribut. Ensuite, dans la fonction principale, nous créons une variable a et affichons son adresse mémoire. Ensuite, nous passons la même variable à la fonction et imprimons son adresse mémoire.  Comme vous pouvez le voir, si vous essayez, les résultats seront différents : c'est parce que les attributs sont transmis aux fonctions en tant que valeur, ce qui signifie qu'une copie de   est créée uniquement dans le but de la transmettre à la fonction. a  De retour à notre liste liée, nous devons utiliser des pointeurs pour obtenir la vraie tête pour le même problème ci-dessus.              Donc, pour arriver au "vrai" ll.Node nous devons rappeler son pointeur, *ll.Node et le déplacer plus loin avec *ll.Node = *ll.Node.Next .  Dans la fonction principale, nous ajoutons les appels à la méthode, par exemple en appelant   et   , et nous pouvons vérifier le résultat où le nœud 0 et le nœud 2 seront manquants. ll.RemoveNode(0) ll.RemoveNode(2)  Conclusion  Nous sommes arrivés au bout !  Si vous avez lu jusqu'à ce point, toute ma gratitude va vers vous. Si vous êtes prêt à laisser un like ou deux et à partager l'article, cela fera ma journée et m'aidera à continuer à écrire ces articles !  Rendez-vous dans le prochain article, et, comme toujours, merci d'avoir lu.   Nicolas

Read My Stories

Cet audio est produit dans la langue originale de l'histoire !

Problème de codage quotidien : supprimer le k-ième index de la liste liée en une seule passe

About Author

COMMENTAIRES

ÉTIQUETTES

CET ARTICLE A ÉTÉ PARU DANS

Related Stories

Vous voulez gagner un concours d’écriture HackerNoon ? Voici ce que recommandent les gagnants du concours #crypto-api

Libérer la puissance de l’IA. Une revue systématique des techniques de pointe : résumé et introduction

Valhalla de Floki se joint en tant que sponsor associé de la tournée indienne au Sri Lanka

Les couches invisibles : pourquoi les entretiens avec les utilisateurs sont un atout irremplaçable

Vous voulez gagner un concours d’écriture HackerNoon ? Voici ce que recommandent les gagnants du concours #crypto-api

Libérer la puissance de l’IA. Une revue systématique des techniques de pointe : résumé et introduction

Valhalla de Floki se joint en tant que sponsor associé de la tournée indienne au Sri Lanka

Les couches invisibles : pourquoi les entretiens avec les utilisateurs sont un atout irremplaçable

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps