Insérer un nœud à une position donnée

Question

J'apprends le python et la structure de données. Je mettais en œuvre des méthodes de liste à lien unique qui incluaient l'insertion en tête et à un poste donné. Je fini par écrire ce code:

class Node : 
    def __init__(self,data=None,next_node=None) : 
     self.data = data 
     self.next = next_node 

class LinkedList : 
    def __init__(self) : 
     self.head = None 

    def insertathead(self,new_data) : 
     new_node = Node(new_data) 
     new_node.next = self.head 
     self.head = new_node 


    def InsertNpos(self,new_data,pos): 
     start = self.head 
     if pos == 0: 
      return Node(new_data, self.head) 
     while pos > 1: 
      self.head = self.head.next 
      pos -= 1 
     self.head.next = Node(new_data, self.head.next) 
     return start 

    def PrintLinkList(self) : 
     temp = self.head 
     while (temp) : 
      print (temp.data) 
      temp = temp.next 

if __name__ == '__main__' : 
    llist = LinkedList() 
    llist.insertathead(8) 
    llist.insertathead(3)  
    llist.insertathead(10) 
    llist.insertathead(12) 
    llist.insertathead(15) 
    llist.insertathead(2) 
    llist.InsertNpos(1,2) 
    llist.PrintLinkList() 

Sortie:

15 
1 
12 
10 
3 
8 

Maintenant, juste insérer à la tête fonctionne très bien, mais InsertNpos (1,2) donne une sortie erronée. La sortie est censée être 2,15,1,12,10,3,8. S'il vous plaît dites-moi où mon code est faux.

Answer 1

Lorsque vous insérez à la position pos, votre insertion de routine supprime les premiers pos-1 éléments de la liste. change le pointeur de tête à chaque itération. Vous avez besoin d'une variable locale pour parcourir la liste. Aussi, pourquoi renvoyez-vous une valeur? Vous ne l'utilisez jamais. Le seul but de cette méthode est de mettre à jour la liste en place.

def InsertNpos(self,new_data,pos): 
    if pos == 0: 
     self.head = Node(new_data, self.head) 
     return 

    start = self.head 
    while pos > 1: 
     start = start.next 
     pos -= 1 
    start.next = Node(new_data, start.next) 

sortie Nouveau:

Before insertion 
2 
15 
12 
10 
3 
8 
After insertion 
2 
15 
1 
12 
10 
3 
8 

Answer 2

Même si la réponse a déjà été acceptée, j'ai essayé la solution et que AChampion a suggéré qu'il ne travaille pas pour moi pour l'insertion à 0, mais ma solution ne :

class Node : 
    def __init__(self,data=None,next_node=None) : 
     self.data = data 
     self.next = next_node 

class LinkedList : 
    def __init__(self) : 
     self.head = None 

    def insertathead(self,new_data) : 
     new_node = Node(new_data) 
     new_node.next = self.head 
     self.head = new_node 


    def InsertNpos(self,new_data,pos): 
     if pos == 0: 
      self.head = Node(new_data, self.head) 
      return self.head 
     i = 0 
     curr = self.head 
     while curr.next: 
      if i == pos - 1: 
       curr.next = Node(new_data, curr.next) 
       return self.head 
      curr = curr.next 
      i += 1 
     curr.next = Node(new_data) 
     return self.head 

    def PrintLinkList(self) : 
     temp = self.head 
     while (temp) : 
      print (temp.data) 
      temp = temp.next 

Ceci insère l'élément à la fin si pos est hors de portée.