CODEWITHSUNDEEP
python
user14635413
user14635413

Reputation:

singly linked list infinite loop when inserting an element at the end python

When I want to add an element at the end of my linked list it result in an infinite loop, here's the method i used

#insert at the end of the list

def append(self, data=None):
    new_node = Node(data)
    if self.head is None:
        self.head = new_node
    itr = self.head
    while itr.next:
        itr.next = new_node
        itr = itr.next

Upvotes: 0

Views: 652

Answers (2)

Oli
Oli

Reputation: 2602

Your problem is in the loop:

while itr.next:
   itr.next = new_node
   itr = itr.next

When appending an item to an empty list, itr is initially is equal to new_node. You set itr.next to new_node, so now new_node.next is equal to new_node. You have now created a cycle in your list, so it will loop forever.

When appending an item to your list, you should only be modifying the last element - the loop only serves to traverse the list to get to the end. It should look like:

def append(self, data=None):
    new_node = Node(data)
    if self.head is None:
        self.head = new_node
    else: 
        # you only need to traverse the list when it isn't empty
        itr = self.head
        while itr.next:
            itr = itr.next
        itr.next = new_node # only add the new node after traversing the list

That being said, this method of appending is O(n) complexity, and you can make it O(1) by keeping a pointer to the tail of the list and modifying the tail without traversing the list to find it.

Upvotes: 1

pudup
pudup

Reputation: 131

Your code should return after adding the new node at the head if the list is empty.

After that your while loop is an infinite loop

You need to update it's position BEFORE you add to it and then add to it outside the loop

def append(self, data=None):
    new_node = Node(data)
    if self.head is None:
        self.head = new_node
        return
    itr = self.head
    while itr.next:
        itr = itr.next
    itr.next = new_node

Also your Node() should have a parameter for next

Upvotes: 1

Related Questions