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

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 ici . Découvrez-le et essayez également de résoudre vos défis !

• 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

Étant donné une liste chaînée et un entier k , supprimez le k-ème nœud de la fin de la liste et renvoyez la tête de la liste.

k est garanti inférieur à la longueur de la liste.

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 k à supprimer de la liste. Après cela, nous devrions retourner la tête de la liste chaînée.

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 k est contenu dans la liste, nous n'avons donc pas à vérifier qu'il dépasse la longueur réelle de la liste.

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 nodes ), et chaque nœud doit avoir au moins deux propriétés : une valeur (quelque chose réellement contenu par le nœud) et un lien vers le nœud suivant.

Habituellement, un pointeur est utilisé comme lien pour passer d'un nœud à un autre.

De plus, le premier nœud de la liste est généralement appelé la tête de la liste, qui est également le nœud que le problème nous demande de renvoyer.

Voici un exemple graphique :

Le premier noeud à gauche est la tête de liste, qui contient sa valeur v₀ et un pointeur mémoire P(n₁) qui redirige la liste vers le noeud suivant n₁. Le nœud suivant n₁ contiendra sa valeur et un pointeur P(n₂) vers le nœud suivant, et ainsi de suite.

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 !

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é Value et la propriété Next , qui contient un type *Node comme pointeur vers le nœud suivant.

• La liste chaînée, une structure pour « initialiser » la liste chaînée, qui n'aura qu'une seule propriété, la Head de liste.

  
  

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 le nœud Head , puisqu'il est de type Node , aura intrinsèquement une propriété Next , qui contiendra le nœud suivant. Ce dernier nœud aura alors sa propriété Next pour sauter sur le nœud suivant, et ainsi de suite.

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 très fastidieux, soit nous écrivons une méthode pour que la classe de liste chaînée ajoute des nœuds supplémentaires. Regardons ça!

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 modifiables et immuables .

Comme leur nom l'indique, les listes modifiables sont des listes auxquelles vous pouvez manipuler et ajouter des éléments . Les immuables, au contraire, ont une taille fixe et ne peuvent pas être ajoutés avec de nouveaux éléments. Mais pourquoi c'est comme ça?

Les listes immuables sont contiguës en mémoire , ce qui signifie que leurs éléments sont stockés en mémoire séquentiellement : pour une liste de 3 éléments, si le premier élément est stocké à 0x00, alors le second sera à 0x01 et le dernier à 0x02.

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?

Eh bien, parce que le dernier élément de la première initiation aura un pointeur que l'élément ajouté après lui , ce qui nous amènera l'élément to ajouté, et ainsi de suite. Alors oui, les listes modifiables sont très souvent des listes chaînées déguisées !

Voyons maintenant le code :

Nous avons ajouté la méthode AddNode aux méthodes de notre liste chaînée. Le processus pour ajouter un nœud se déroule comme suit :

• Tout d'abord, nous stockons la valeur Head dans une variable appelée current

• Ensuite, nous parcourons la liste chaînée en mettant à jour la variable current avec le nœud suivant à chaque fois, jusqu'à ce que le nœud suivant soit nul. 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 Next de ce nouveau nœud sera mis à null si nous le laissons vide)

  
  

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, un nœud dans une liste chaînée n'existe que s'il est connecté au précédent , n'est-ce pas ?

Par exemple, si nous donnons au n-1ᵗʰ une valeur Next nulle, nous pouvons déconnecter la valeur nᵗʰ de la liste.

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, nous ne pouvons pas indexer directement la liste : essayer quelque chose comme linkedlist[n] 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.

Ce que nous pouvons faire alors, c'est implémenter un compteur pour garder une trace du nœud sur lequel nous nous trouvons !

Codons-le alors.

Regardons la fonction RemoveNode qui accepte un attribut index . Après cela, nous initialisons trois variables :

• previousNode , qui contiendra le nœud précédent

• current , qui contiendra le nœud sur lequel nous nous trouvons pendant la boucle

• counter , initialement égal à 0, qui maintiendra notre position sur la liste

  
  

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 counter soit strictement inférieure à notre index : chaque boucle mettra alors à jour le nœud précédent avec celui en cours et passera à la mise à jour du nœud en cours et du compteur.

Lorsque la boucle se casse, cela signifie que 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 counter = 0 et index = 0 , et la condition serait instantanément fausse. On peut gérer ce premier cas avec le bloc if en haut.

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, transmet les attributs aux functions par value , ce qui signifie que la fonction conserve une copie de l'objet passé, 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 a est créée uniquement dans le but de la transmettre à la fonction.

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 ll.RemoveNode(0) et ll.RemoveNode(2) , et nous pouvons vérifier le résultat où le nœud 0 et le nœud 2 seront manquants.

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