Comment implémenter une liste liée en Python?

Le langage de programmation Python est un langage open-source avec diverses implémentations prêtes à l'emploi qui le rendent unique et plus facile à apprendre. Bien que ne prend pas en charge le concept de liste chaînée, il existe un moyen de le contourner grâce à une implémentation différente pour obtenir une liste chaînée. Dans cet article, nous allons apprendre comment créer une liste chaînée en Python. Voici les sujets abordés dans ce blog:

• Qu'est-ce que la liste liée?
• Implémentation d'une liste liée
• Méthodes de liste chaînée

Commençons!!

Qu'est-ce que la liste liée?

La liste de liens est une séquence de nœuds ayant un type de données similaire, chaque nœud contient un objet de données et un pointeur vers le nœud suivant.

Une liste chaînée est une structure de données linéaire avec la collection de plusieurs nœuds. Où eChaque élément stocke ses propres données et un pointeur vers l'emplacement de l'élément suivant. Le dernier lien d'une liste liée pointe vers null, indiquant la fin de la chaîne. Un élément d'une liste liée est appelé un nœud . Le premier nœud s'appelle le tête .Le dernier nœud est appeléla queue .
La bibliothèque Python standard n'a pas de liste liée. Nous pouvons implémenter le concept de structure de données de liste de liens en utilisant le concept de nœuds.

Maintenant que nous avons appris ce qu'est Linked. Passons donc à la mise en œuvre d'une liste liée.

Implémentation d'une liste liée

Pour créer une liste liée, nous créons un objet nœud et créons une autre classe pour utiliser cet objet nœud.
Code pour créer la classe Node.
Le programme ci-dessus crée une liste liée avec trois éléments de données.

class Node (object): # Constructeur pour initialiser les variables de classe def __init __ (self, data = None, next_node = None): self.data = data self.next_node = next_node #get data def get_data (self): return self.data # obtenir la valeur suivante def get_next (self): return self.next_node # définir les données suivantes def set_next (self, new_next): self.next_node = new_next

La mise en œuvre de la liste de liens comprend les fonctionnalités suivantes dans une liste liée
un. Insérer : Cette méthode insérera un nouveau nœud dans une liste chaînée.
2. Taille : Cette méthode renverra la taille de la liste liée.
3. Chercher : Cette méthode retournera un nœud contenant les données, sinon provoquera une erreur
Quatre. Effacer : Cette méthode supprimera un nœud contenant les données, sinon provoquera une erreur

Permet de voir la liste des méthodes liées

Méthode init dans une liste liée

class LinkedList (objet): def __init __ (self, head = None): self.head = head

La méthode Init est utilisée pour l'initialisation d'un classe variable si la liste n'a pas de nœuds, elle est définie sur aucun.

Insérer:

def insert (self, data): new_node = Node (données) new_node.set_next (self.head) self.head = new_node

Cette méthode d'insertion prend des données, initialise un nouveau nœud avec les données données et les ajoute à la liste. Techniquement, vous pouvez insérer un nœud n'importe où dans la liste, mais le moyen le plus simple de le faire est de le placer en tête de la liste et de pointer le nouveau nœud vers l'ancienne tête (sorte de pousser les autres nœuds sur la ligne).

Taille

# Renvoie le nombre total de nœuds dans la liste def size (self): current = self.head count = 0 while current: count + = 1 current = current.get_next () return count

La méthode de taille est très simple, elle compte essentiellement les nœuds jusqu'à ce qu'elle ne puisse plus trouver et renvoie le nombre de nœuds trouvés. La méthode commence au nœud principal, parcourt la ligne de nœuds jusqu'à ce qu'elle atteigne la fin (le courant sera Aucun quand elle atteindra la fin) tout en gardant une trace du nombre de nœuds qu'elle a vus.

Chercher

# Renvoie le nœud dans la liste ayant nodeData, une erreur s'est produite si le nœud n'est pas présent def search (self, nodeData): current = self.head isPresent = False pendant que courant et isPresent est False: if current.get_data () == nodeData: isPresent = True else: current = current.get_next () si current est None: augmenter ValueError ('Data not present in list') return current

La recherche est en fait très similaire à la taille, mais au lieu de parcourir toute la liste des nœuds, elle vérifie à chaque arrêt pour voir si le nœud actuel a les données demandées. Si tel est le cas, renvoie le nœud contenant ces données. Si la méthode parcourt toute la liste mais n’a toujours pas trouvé les données, elle génère une erreur de valeur et informe l’utilisateur que les données ne figurent pas dans la liste.

Effacer

# Supprimer le nœud de la liste liée renvoie une erreur si le nœud n'est pas présent def delete (self, nodeData): current = self.head previous = None isPresent = False pendant que courant et isPresent est False: if current.get_data () == nodeData: isPresent = True else: previous = current current = current.get_next () si current est None: augmenter ValueError ('Données non présentes dans la liste') si previous is None: self.head = current.get_next () else: previous.set_next ( current.get_next ())

La méthode de suppression parcourt la liste de la même manière que la recherche, mais en plus de garder une trace du nœud actuel, la méthode de suppression se souvient également du dernier nœud visité. Lorsque la suppression arrive enfin au nœud qu'elle souhaite supprimer. Il supprime simplement ce nœud de la chaîne en le «sautant».

Je veux dire par là que lorsque la méthode de suppression atteint le nœud qu’elle souhaite supprimer, elle examine le dernier nœud visité (le nœud «précédent») et réinitialise le pointeur de ce nœud précédent. Plutôt que de pointer vers le nœud sur le point d'être supprimé.

Il pointera vers le nœud suivant de la ligne. Étant donné qu'aucun nœud ne pointe vers le nœud pauvre qui est en cours de suppression, il est effectivement supprimé de la liste!

Cela nous amène à la fin de cet article où nous avons appris comment créer une liste chaînée en python avec une implémentation similaire même si python ne prend pas vraiment en charge le concept de liste chaînée. J'espère que vous êtes clair avec tout ce qui a été partagé avec vous dans ce tutoriel.

Si vous avez trouvé cet article sur 'Liste liée en Python' pertinent, consultez le Une entreprise d'apprentissage en ligne de confiance avec un réseau de plus de 250 000 apprenants satisfaits répartis dans le monde entier.

Nous sommes là pour vous aider à chaque étape de votre voyage et proposer un programme conçu pour les étudiants et les professionnels qui souhaitent devenir . Le cours est conçu pour vous donner une longueur d'avance dans la programmation Python et vous former aux concepts Python de base et avancés ainsi que divers comme

qu'est-ce que tostring en java

Si vous rencontrez des questions, n'hésitez pas à poser toutes vos questions dans la section commentaires de «Linked List In Python» et notre équipe se fera un plaisir de vous répondre.