Dans cet article, nous découvrirons la mise en œuvre d'une liste chaînée dans Python . Pour implémenter la liste chaînée en Python, nous utiliserons cours en Python . Maintenant, nous savons qu'une liste chaînée est composée de nœuds et que les nœuds ont deux éléments, à savoir des données et une référence à un autre nœud. Implémentons d'abord le nœud.
Qu'est-ce que la liste chaînée en Python
Une liste chaînée est un type de structure de données linéaire similaire aux tableaux. C'est un ensemble de nœuds liés les uns aux autres. Un nœud contient deux éléments : la première est des données et la deuxième est un lien qui le connecte à un autre nœud. Vous trouverez ci-dessous un exemple de liste chaînée avec quatre nœuds et chaque nœud contient des données de caractères et un lien vers un autre nœud. Notre premier nœud est l'endroit où tête points et nous pouvons accéder à tous les éléments de la liste chaînée en utilisant le tête.
Liste liée
Créer une liste chaînée en Python
Dans cette classe LinkedList, nous utiliserons la classe Node pour créer une liste chaînée. Dans cette classe, nous avons un __chaud__ méthode qui initialise la liste chaînée avec une tête vide. Ensuite, nous avons créé un insertAtBegin() méthode pour insérer un nœud au début de la liste chaînée, un insertAtIndex() méthode pour insérer un nœud à l'index donné de la liste chaînée, et insérerAtEnd() La méthode insère un nœud à la fin de la liste chaînée. Après cela, nous avons le supprimer_node() méthode qui prend les données comme argument pour supprimer ce nœud. Dans le supprimer_node() méthode, nous parcourons la liste chaînée si un nœud est présent égal aux données, nous supprimons ce nœud de la liste chaînée. Ensuite nous avons le tailleDeLL() méthode pour obtenir la taille actuelle de la liste chaînée et la dernière méthode de la classe LinkedList est printLL() qui parcourt la liste chaînée et imprime les données de chaque nœud.
Création d'une classe de nœud
Nous avons créé une classe Node dans laquelle nous avons défini un __chaud__ fonction pour initialiser le nœud avec les données passées en argument et une référence avec None car si nous n'avons qu'un seul nœud alors il n'y a rien dans sa référence.
Python3
class> Node:> >def> __init__(>self>, data):> >self>.data>=> data> >self>.>next> => None> |
>
>
Insertion dans une liste chaînée
Insertion au début dans la liste chaînée
Cette méthode insère le nœud au début de la liste chaînée. Dans cette méthode, nous créons un nouveau_node avec le donné données et vérifions si la tête est un nœud vide ou non si la tête est vide alors nous faisons le nouveau_node comme tête et retour sinon on insère la tête au suivant nouveau_node et faire le tête égal à nouveau_node.
Python3
def> insertAtBegin(>self>, data):> >new_node>=> Node(data)> >if> self>.head>is> None>:> >self>.head>=> new_node> >return> >else>:> >new_node.>next> => self>.head> >self>.head>=> new_node> |
>
>
Insérer un nœud à une position spécifique dans une liste chaînée
Cette méthode insère le nœud à l'index donné dans la liste chaînée. Dans cette méthode, nous créons un nouveau_node avec des données données, un current_node égal à la tête et un compteur 'position' s'initialise avec 0. Maintenant, si l'index est égal à zéro, cela signifie que le nœud doit être inséré au début, nous avons donc appelé Méthode insertAtBegin() sinon nous exécutons une boucle while jusqu'à ce que le noeud_actuel n'est pas égal à Aucun ou (poste+1) n'est pas égal à l'index que nous devons à une position en arrière pour insérer à une position donnée pour faire la liaison des nœuds et à chaque itération, nous incrémentons la position de 1 et faisons le noeud_actuel ensuite. Quand la boucle se rompt et si noeud_actuel n'est pas égal à Aucun nous insérons new_node après dans le noeud_actuel. Si noeud_actuel est égal à Aucun cela signifie que l'index n'est pas présent dans la liste et on imprime Index non présent.
Python3
# Indexing starts from 0.> def> insertAtIndex(>self>, data, index):> >new_node>=> Node(data)> >current_node>=> self>.head> >position>=> 0> >if> position>=>=> index:> >self>.insertAtBegin(data)> >else>:> >while>(current_node !>=> None> and> position>+>1> !>=> index):> >position>=> position>+>1> >current_node>=> current_node.>next> >if> current_node !>=> None>:> >new_node.>next> => current_node.>next> >current_node.>next> => new_node> >else>:> >print>(>'Index not present'>)> |
>
>
Insertion dans la liste chaînée à la fin
Cette méthode insère le nœud à la fin de la liste chaînée. Dans cette méthode, nous créons un nouveau_node avec les données fournies et vérifiez si le tête est un nœud vide ou non si le tête est vide alors on fait le nouveau_node comme tête et retour autre nous faisons un current_node égal à la tête traverser jusqu'au dernier nœud de la liste chaînée et quand nous obtenons Aucun après le current_node, la boucle while se brise et insère le nouveau_node dans le prochain de noeud_actuel qui est le dernier nœud de la liste chaînée.
Python3
def> inserAtEnd(>self>, data):> >new_node>=> Node(data)> >if> self>.head>is> None>:> >self>.head>=> new_node> >return> >current_node>=> self>.head> >while>(current_node.>next>):> >current_node>=> current_node.>next> >current_node.>next> => new_node> |
>
>
Mettre à jour le nœud d'une liste chaînée
Ce code définit une méthode appelée updateNode dans une classe de liste chaînée. Il est utilisé pour mettre à jour la valeur d'un nœud à une position donnée dans la liste chaînée.
java point java
Python3
# Update node of a linked list> # at given position> def> updateNode(>self>, val, index):> >current_node>=> self>.head> >position>=> 0> >if> position>=>=> index:> >current_node.data>=> val> >else>:> >while>(current_node !>=> None> and> position !>=> index):> >position>=> position>+>1> >current_node>=> current_node.>next> >if> current_node !>=> None>:> >current_node.data>=> val> >else>:> >print>(>'Index not present'>)> |
>
>
Supprimer un nœud dans une liste liée
Supprimer le premier nœud de la liste liée
Cette méthode supprime le premier nœud de la liste chaînée simplement en rendant le deuxième nœud tête de la liste chaînée.
Python3
def> remove_first_node(>self>):> >if>(>self>.head>=>=> None>):> >return> > >self>.head>=> self>.head.>next> |
>
>
Supprimer le dernier nœud de la liste liée
Dans cette méthode, nous supprimerons le dernier nœud. Tout d'abord, nous passons à l'avant-dernier nœud en utilisant la boucle while, puis nous créons le suivant de ce nœud. Aucun et le dernier nœud sera supprimé.
Python3
def> remove_last_node(>self>):> >if> self>.head>is> None>:> >return> >current_node>=> self>.head> >while>(current_node.>next>.>next>):> >current_node>=> current_node.>next> >current_node.>next> => None> |
>
>
Supprimer un nœud de liste chaînée à une position donnée
Dans cette méthode, nous supprimerons le nœud à l'index donné, cette méthode est similaire à le insert_at_inded() méthode. Dans cette méthode, si le tête est Aucun nous simplement retour sinon on initialise un noeud_actuel avec soi.tête et position avec 0. Si la position est égale à l'indice que nous appelons le supprimer_premier_node() Sinon, nous parcourons le nœud avant celui que nous voulons supprimer à l'aide de la boucle while. Après cela, lorsque nous sortons de la boucle while, nous vérifions ce nœud_actuel est égal à Aucun sinon, nous rendons le prochain de current_node égal au prochain nœud que nous voulons supprimer, sinon nous imprimons le message Index non présent parce que noeud_actuel est égal à Aucun.
Python3
# Method to remove at given index> def> remove_at_index(>self>, index):> >if> self>.head>=>=> None>:> >return> >current_node>=> self>.head> >position>=> 0> >if> position>=>=> index:> >self>.remove_first_node()> >else>:> >while>(current_node !>=> None> and> position>+>1> !>=> index):> >position>=> position>+>1> >current_node>=> current_node.>next> >if> current_node !>=> None>:> >current_node.>next> => current_node.>next>.>next> >else>:> >print>(>'Index not present'>)> |
>
>
Supprimer un nœud de liste chaînée d'une donnée donnée
Cette méthode supprime le nœud contenant les données données de la liste chaînée. Dans cette méthode, nous avons d'abord fait un noeud_actuel égal au tête et exécuter un boucle while pour parcourir la liste chaînée. Cette boucle while se brise lorsque noeud_actuel devient Aucun ou les données à côté du nœud actuel sont égales aux données données dans l'argument. Maintenant, après être sorti de la boucle, si le noeud_actuel est égal à Aucun cela signifie que le nœud n'est pas présent dans les données et que nous revenons simplement, et si les données à côté du noeud_actuel est égal aux données fournies, puis nous supprimons ce nœud en faisant du prochain de ce supprimé_node le prochain de current_node. Et ceci est implémenté en utilisant la condition if else.
Python3
def> remove_node(>self>, data):> >current_node>=> self>.head> ># Check if the head node contains the specified data> >if> current_node.data>=>=> data:> >self>.remove_first_node()> >return> >while> current_node>is> not> None> and> current_node.>next>.data !>=> data:> >current_node>=> current_node.>next> >if> current_node>is> None>:> >return> >else>:> >current_node.>next> => current_node.>next>.>next> |
>
>
Traversée de liste liée en Python
Cette méthode parcourt la liste chaînée et imprime les données de chaque nœud. Dans cette méthode, nous avons réalisé un noeud_actuel égal au tête et parcourez la liste chaînée en utilisant un boucle while jusqu'à ce que le noeud_actuel devient Aucun et imprime les données de noeud_actuel à chaque itération et faire le noeud_actuel à côté de cela.
Python3
def> printLL(>self>):> >current_node>=> self>.head> >while>(current_node):> >print>(current_node.data)> >current_node>=> current_node.>next> |
>
>
Obtenir la longueur d'une liste chaînée en Python
Cette méthode renvoie la taille de la liste chaînée. Dans cette méthode, nous avons initialisé un compteur 'taille' avec 0, puis si la tête n'est pas égale à None, nous parcourons la liste chaînée en utilisant un boucle while et incrémenter le taille avec 1 à chaque itération et renvoie la taille lorsque noeud_actuel devient Personne d'autre nous renvoyons 0.
Python3
def> sizeOfLL(>self>):> >size>=> 0> >if>(>self>.head):> >current_node>=> self>.head> >while>(current_node):> >size>=> size>+>1> >current_node>=> current_node.>next> >return> size> >else>:> >return> 0> |
>
caractère d'échappement Java
>
Exemple de liste chaînée en Python
Dans cet exemple, après avoir défini les classes Node et LinkedList, nous avons créé une liste chaînée nommée liste en utilisant la classe de liste chaînée, puis insérez quatre nœuds avec des données de caractères 'a B c d' et 'g' dans la liste chaînée puis nous imprimons la liste chaînée en utilisant printLL() classe de liste chaînée de méthode après cela, nous avons supprimé certains nœuds à l'aide des méthodes de suppression puis imprimez à nouveau la liste chaînée et nous pouvons voir dans la sortie que le nœud a été supprimé avec succès. Après cela, nous imprimons également la taille de la liste chaînée.
Python3
# Create a Node class to create a node> class> Node:> >def> __init__(>self>, data):> >self>.data>=> data> >self>.>next> => None> # Create a LinkedList class> class> LinkedList:> >def> __init__(>self>):> >self>.head>=> None> ># Method to add a node at begin of LL> >def> insertAtBegin(>self>, data):> >new_node>=> Node(data)> >if> self>.head>is> None>:> >self>.head>=> new_node> >return> >else>:> >new_node.>next> => self>.head> >self>.head>=> new_node> ># Method to add a node at any index> ># Indexing starts from 0.> >def> insertAtIndex(>self>, data, index):> >new_node>=> Node(data)> >current_node>=> self>.head> >position>=> 0> >if> position>=>=> index:> >self>.insertAtBegin(data)> >else>:> >while>(current_node !>=> None> and> position>+>1> !>=> index):> >position>=> position>+>1> >current_node>=> current_node.>next> >if> current_node !>=> None>:> >new_node.>next> => current_node.>next> >current_node.>next> => new_node> >else>:> >print>(>'Index not present'>)> ># Method to add a node at the end of LL> >def> insertAtEnd(>self>, data):> >new_node>=> Node(data)> >if> self>.head>is> None>:> >self>.head>=> new_node> >return> >current_node>=> self>.head> >while>(current_node.>next>):> >current_node>=> current_node.>next> >current_node.>next> => new_node> ># Update node of a linked list> ># at given position> >def> updateNode(>self>, val, index):> >current_node>=> self>.head> >position>=> 0> >if> position>=>=> index:> >current_node.data>=> val> >else>:> >while>(current_node !>=> None> and> position !>=> index):> >position>=> position>+>1> >current_node>=> current_node.>next> >if> current_node !>=> None>:> >current_node.data>=> val> >else>:> >print>(>'Index not present'>)> ># Method to remove first node of linked list> >def> remove_first_node(>self>):> >if>(>self>.head>=>=> None>):> >return> >self>.head>=> self>.head.>next> ># Method to remove last node of linked list> >def> remove_last_node(>self>):> >if> self>.head>is> None>:> >return> >current_node>=> self>.head> >while>(current_node.>next>.>next>):> >current_node>=> current_node.>next> >current_node.>next> => None> ># Method to remove at given index> >def> remove_at_index(>self>, index):> >if> self>.head>=>=> None>:> >return> >current_node>=> self>.head> >position>=> 0> >if> position>=>=> index:> >self>.remove_first_node()> >else>:> >while>(current_node !>=> None> and> position>+>1> !>=> index):> >position>=> position>+>1> >current_node>=> current_node.>next> >if> current_node !>=> None>:> >current_node.>next> => current_node.>next>.>next> >else>:> >print>(>'Index not present'>)> ># Method to remove a node from linked list> >def> remove_node(>self>, data):> >current_node>=> self>.head> >if> current_node.data>=>=> data:> >self>.remove_first_node()> >return> >while>(current_node !>=> None> and> current_node.>next>.data !>=> data):> >current_node>=> current_node.>next> >if> current_node>=>=> None>:> >return> >else>:> >current_node.>next> => current_node.>next>.>next> ># Print the size of linked list> >def> sizeOfLL(>self>):> >size>=> 0> >if>(>self>.head):> >current_node>=> self>.head> >while>(current_node):> >size>=> size>+>1> >current_node>=> current_node.>next> >return> size> >else>:> >return> 0> ># print method for the linked list> >def> printLL(>self>):> >current_node>=> self>.head> >while>(current_node):> >print>(current_node.data)> >current_node>=> current_node.>next> # create a new linked list> llist>=> LinkedList()> # add nodes to the linked list> llist.insertAtEnd(>'a'>)> llist.insertAtEnd(>'b'>)> llist.insertAtBegin(>'c'>)> llist.insertAtEnd(>'d'>)> llist.insertAtIndex(>'g'>,>2>)> # print the linked list> print>(>'Node Data'>)> llist.printLL()> # remove a nodes from the linked list> print>(>'
Remove First Node'>)> llist.remove_first_node()> print>(>'Remove Last Node'>)> llist.remove_last_node()> print>(>'Remove Node at Index 1'>)> llist.remove_at_index(>1>)> # print the linked list again> print>(>'
Linked list after removing a node:'>)> llist.printLL()> print>(>'
Update node Value'>)> llist.updateNode(>'z'>,>0>)> llist.printLL()> print>(>'
Size of linked list :'>, end>=>' '>)> print>(llist.sizeOfLL())> |
>
>Sortir
Node Data c a g b d Remove First Node Remove Last Node Remove Node at Index 1 Linked list after removing a node: a b Update node Value z b Size of linked list : 2>