Insertion des éléments

Selon l’endroit où vous souhaitez insérer un élément, il existe différentes façons d’insérer des éléments dans une seule liste chaînée

.Insertion d’éléments au début

La façon la plus simple d’insérer un élément dans une liste chaînée est d’ajouter un élément au début de la liste. La fonction suivante permet d’insérer un élément au début de la liste. Ajoutez cette fonction à la classe LinkedList que nous avons créée précédemment.

    def insert_at_start(self, data):
        new_node = Node(data)
        new_node.ref = self.start_node
        self.start_node= new_node

Dans le script ci-dessus, nous créons une méthode insert_at_start(), la méthode accepte un paramètre, qui est essentiellement la valeur de l’élément que nous voulons insérer. À l’intérieur de la méthode, nous créons simplement un objet de la classe Node et nous fixons sa référence au start_node puisque start_node stockait auparavant le premier nœud, qui après l’insertion d’un nouveau nœud au départ deviendra le deuxième nœud.

Par conséquent, nous ajoutons la référence de start_node à la variable ref du nouveau nœud. Maintenant, puisque new_node est le premier nœud, nous fixons la valeur de la variable start_node à new_node.

Insertion d’éléments à la fin

La fonction suivante est utilisée pour ajouter un élément à la fin de la liste chaînée.

  def insert_at_end(self, data):
        new_node = Node(data)
        if self.start_node is None:
            self.start_node = new_node
            return
        n = self.start_node
        while n.ref is not None:
            n= n.ref
        n.ref = new_node;

Pour un aperçu, 👉 cliquez sur une couverture pour feuilleter le livre sur Amazon 📚.

Dans le script ci-dessus, nous créons une fonction insert_at_end(), qui insère l’élément à la fin de la liste chaînée. La valeur de l’élément que nous voulons insérer est passée en argument à la fonction. La fonction se compose de deux parties. Tout d’abord, nous vérifions si la liste chaînée est vide ou non. Si la liste chaînée est vide, il suffit de fixer la valeur de la variable start_node à l’objet new_node.

D’autre part, si la liste contient déjà quelques nœuds. Nous initialisons une variable n avec le nœud de départ. Nous itérons ensuite à travers tous les nœuds de la liste en utilisant une boucle while comme nous l’avons fait dans le cas de la fonction traverse_list. La boucle se termine lorsque nous atteignons le dernier nœud. Nous fixons alors la référence du dernier nœud au nouveau new_node nouvellement créé.

Ajoutez la fonction insert_at_end() à la classe LinkedList.

Insertion d’un élément après un autre élément

Il se peut que nous devions ajouter un élément après l’autre dans une seule liste chaînée. Pour ce faire, nous pouvons utiliser la fonction insert_after_item() telle que définie ci-dessous :

    def insert_after_item(self, x, data):

        n = self.start_node
        print(n.ref)
        while n is not None:
            if n.item == x:
                break
            n = n.ref
        if n is None:
            print("Elément dans la liste")
        else:
            new_node = Node(data)
            new_node.ref = n.ref
            n.ref = new_node

La fonction insert_after_item() accepte deux paramètres : x et data. Le premier paramètre est l’élément après lequel vous voulez insérer le nouveau noeud tandis que le second paramètre contient la valeur du nouveau noeud.

Nous commençons par créer une nouvelle variable n et lui attribuer la variable start_node. Ensuite, nous parcourons la liste liée en utilisant la boucle while. La boucle while s’exécute jusqu’à ce que n devienne None. Au cours de chaque itération, nous vérifions si la valeur stockée dans le nœud actuel est égale à la valeur passée par le paramètre x. Si la comparaison est vraie, nous rompons la boucle.

Ensuite, si l’élément est trouvé, la variable n ne sera pas None. La référence du new_node est définie comme référence stockée par n et la référence de n est définie comme new_node. Ajoutez la fonction insert_after_item() à la classe LinkesList.

Insertion d’un élément avant un autre élément

      def insert_before_item(self, x, data):
        if self.start_node is None:
            print("La liste n'a pas d'élément.")
            return

        if x == self.start_node.item:
            new_node = Node(data)
            new_node.ref = self.start_node
            self.start_node = new_node
            return

        n = self.start_node
        print(n.ref)
        while n.ref is not None:
            if n.ref.item == x:
                break
            n = n.ref
        if n.ref is None:
            print("L'élément n'est pas dans la liste.")
        else:
            new_node = Node(data)
            new_node.ref = n.ref
            n.ref = new_node

Dans le script ci-dessus, nous définissons la fonction insert_before_item(). Cette fonction comporte trois parties. Examinons chaque partie en détail.

   if self.start_node is None:
        print("La liste n'a pas d'élément.")
        return

Dans le script ci-dessus, nous vérifions si la liste est vide. Si elle est effectivement vide, nous imprimons simplement que la liste n’a pas d’élément et nous revenons de la fonction.

Ensuite, nous vérifions si l’élément se trouve dans le premier index. Regardez le script suivant :

     if x == self.start_node.item:
        new_node = Node(data)
        new_node.ref = self.start_node
        self.start_node = new_node
        return

Si l’élément après lequel on veut insérer un nouveau nœud se trouve au premier index. Nous fixons simplement la référence du nœud nouvellement inséré au start_node, puis nous fixons la valeur de start_node à new_node.

Enfin, si la liste n’est pas None et que l’élément ne se trouve pas au premier index, nous créons une nouvelle variable n et lui attribuons la variable start_node. Ensuite, nous parcourons la liste liée en utilisant la boucle while. La boucle while-loop s’exécute jusqu’à ce que n.ref devienne None. Au cours de chaque itération, nous vérifions si la valeur stockée dans la référence du nœud courant est égale à la valeur passée par le paramètre x. Si la comparaison est vraie, nous cassons la boucle.

Ensuite, si l’élément est trouvé, la variable n.ref ne sera pas None. La référence du nouveau_nœud est fixée à la référence de n et la référence de n est fixée à new_node. Regardez le script suivant :

    if n.ref is None:
        print("L'élément n'est pas dans la liste.")
    else:
        new_node = Node(data)
        new_node.ref = n.ref
        n.ref = new_node

Ajoutez la fonction insert_before_item() à la classe LinkedList.

Insertion d’un élément à un index spécifique

Parfois, nous avons besoin d’insérer un élément à un index spécifique, nous pouvons le faire à l’aide du script suivant :

    def insert_at_index (self, index, data):
        if index == 1:
            new_node = Node(data)
            new_node.ref = self.start_node
            self.start_node = new_node
        i = 1
        n = self.start_node
        while i < index-1 and n is not None:
            n = n.ref
            i = i+1
        if n is None:
            print("Index out of bound")
        else: 
            new_node = Node(data)
            new_node.ref = n.ref
            n.ref = new_node

Dans le script, nous vérifions d’abord si l’index dans lequel nous voulons stocker l’élément est 1, puis nous attribuons simplement start_node à la référence du new_node et nous fixons ensuite la valeur de start_node à new_node.

Ensuite, on exécute une boucle while qui s’exécute jusqu’à ce que le compteur i devienne supérieur ou égal à l’index-1. Par exemple, si vous voulez ajouter un nouveau nœud au troisième index. Au cours de la première itération de la boucle while, i deviendra 2 et le nœud actuellement itéré sera “2”. La boucle ne s’exécutera pas à nouveau puisque i est maintenant 2, ce qui est égal à l’index 1 (3-1=2). Par conséquent, la boucle sera interrompue. Ensuite, nous ajoutons un nouveau nœud après le nœud actuellement itéré (qui est le nœud 2), ce qui fait que le nouveau nœud est ajouté à l’index.

Il est important de mentionner que si l’index ou l’emplacement passé en argument est supérieur à la taille de la liste liée, un message sera affiché à l’utilisateur indiquant que l’index est hors de portée ou hors limite.

Il ne vous reste plus qu’à tester vos fonctions d’insertion en Python.