Listes liée

Une liste liée est une séquence d'éléments de données, qui sont reliés entre eux par des liens. Chaque élément de données contient une connexion vers un autre élément de données sous la forme d'un pointeur. Python n'a pas de listes liées dans sa bibliothèque standard. Nous implémentons le concept de listes liées en utilisant le concept de nœuds, comme nous l'avons vu dans le chapitre précédent.

Nous avons déjà vu comment créer une classe de nœuds et comment parcourir les éléments d'un nœud. Dans ce cours, nous allons étudier les types de listes liées connues sous le nom de listes singulièrement liées. Dans ce type de structure de données, il n'y a qu'un seul lien entre deux éléments de données. Nous créons une telle liste et créons des méthodes supplémentaires pour insérer, mettre à jour et supprimer des éléments de la liste.

Création d'une liste liée

Une liste liée est créée en utilisant la classe Node que nous avons étudiée dans le dernier chapitre. Nous créons un objet Node et une autre classe pour utiliser cet objet. Nous passons les valeurs appropriées à travers l'objet node pour pointer vers les éléments de données suivants. Le programme ci-dessous crée la liste liée avec trois éléments de données. Dans la section suivante, nous verrons comment traverser la liste liée.

class Node:
    def __init__(self, dataval=None):
        self.dataval = dataval
        self.nextval = None

class SLinkedList:
    def __init__(self):
        self.headval = None

list1 = SLinkedList()
list1.headval = Node("Mon")
e2 = Node("Tue")
e3 = Node("Wed")
# Link first Node to second node
list1.headval.nextval = e2

# Link second Node to third node
e2.nextval = e3

Traverser une liste liée

Les listes singulièrement liées ne peuvent être parcourues que dans le sens direct en commençant par le premier élément de données. Nous imprimons simplement la valeur de l'élément de données suivant en assignant le pointeur du nœud suivant à l'élément de données actuel.

Exemple