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()

CodePudding user response：

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.