doubly_linked list Insert after a certain node ends in loop python

Question

Trying to learn Data Structures in Python, implementing doubly linked list. When I am trying to insert a new element after an element, it is ending up in a continuous loop. Please try to explain where I am going wrong and why is it ending it continuous loop.

I am posting my entire code here but the issue is at insertAt. Please help.

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

class Double_list:
    def __init__(self):
        self.head = None
    
    def beginning(self, data):
        node = Node(data)
        if not self.head:
            self.head = node
        else:
            temp = self.head
            node.next = temp
            temp.prev = node

    def addelement(self, data):
        node = Node(data)
        if not self.head:
            self.beginning(data)
            return
        temp = self.head
        last = temp
        while temp.next:
            temp = temp.next
        temp.next = node
        node.prev = temp
    
    def ending(self, data):
        self.addelement(data)

    def insertAt(self, data, after=None):
        node = Node(data)
        temp = self.head
        while temp and after:           
            import pdb; pdb.set_trace()
            last = temp
            temp = temp.next
            if last.data == after:
                last.next = node
                node.prev = last
                node.next = temp
                temp.prev = node
            

    def remove(self,data):
        temp = self.head
        while temp:
            if temp.data == data:
                break
            last = temp
            temp =temp.next
        last.next = temp.next
        temp.next.prev = last

    def printll(self):
        temp = self.head
        while temp:
            print (temp.data, end=" ")
            temp = temp.next

obj = Double_list()
obj.beginning(1)
obj.addelement(2)
obj.ending(3)
obj.insertAt(data=4,after=1)
obj.remove(2)
obj.printll()

Why does your insertAt have a before parameter? It is never used... Please also provide the (minimal) driver code with which the problem is reproduced. — trincot
– trincot, Commented Dec 17, 2021 at 17:37
Is insertAt intended to insert multiple nodes when after occurs multiple times in the list? — trincot
– trincot, Commented Dec 17, 2021 at 17:45
Hi @trincot Thanks for your response. No. It is intended to add single element only. I have modified the code. — rohit tadiparti
– rohit tadiparti, Commented Dec 17, 2021 at 17:48

trincot · Accepted Answer · 2021-12-17 17:53:45Z

As insertAt is intended to insert at most one node, you should exit the loop as soon as it has been added (break). Because this doesn't happen in your code, there is a risk that the same node is added a second time (when after occurs a second time), and this will lead to an inconsistently linked list.

Some other issues in that method:

you should protect your algorithm from accessing temp.prev when temp happens to be None.
The while loop condition should not have anything about after.
The function doesn't use before, so this shouldn't be a parameter.
If the after value is not found in the list, no node should be inserted, and thus it is better to only create the node when after has been found.

So:

    def insertAt(self, data, after=None): # No `before`
        temp = self.head
        while temp:  # No condition on `after`
            last = temp
            temp = temp.next
            if last.data == after:
                node = Node(data)  # <-- moved!
                last.next = node
                node.prev = last
                node.next = temp
                if temp:  # avoid error
                    temp.prev = node
                break  # stop looking further

Another remark: the beginning method should always do self.head = node even if the list already had nodes.

Collectives™ on Stack Overflow

doubly_linked list Insert after a certain node ends in loop python

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related