Reverse a Doubly Linked List is going in a Infinite Loop

The function Reversedll is going into infinite loop here Can anyone help me identify the cause for it????? Program Details : The given function reverseDLL(), which takes head reference as argument and should reverse the elements so that the tail becomes the new head and all pointers are correctly pointed. You need to return the new head of the reversed list.

For a test case : 1 5 1 2 3 4 5 The Output is something like this : 5 4 3 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2

def reverseDLL(head):
    ptr1=head
    ptr2=ptr1.next
    temp=head
    while ptr2:
        ptr2.prev=ptr2.next
        ptr2.next=ptr1
        ptr1=ptr2
        ptr2=ptr2.prev
        
    return ptr1
    


class Node: 
    def __init__(self, data): 
        self.data = data  
        self.next = None
        self.prev = None
  
class DoublyLinkedList: 
    def __init__(self): 
        self.head = None
   
    def push(self, new_data,tail):
        if not self.head:
            self.head=Node(new_data)
            return self.head
        Nnode=Node(new_data)
        Nnode.prev=tail
        tail.next=Nnode
        return Nnode
        
    def printList(self, node): 
        while(node is not None): 
            print (node.data,end=' ') 
            node = node.next
            

            
if __name__ == '__main__':
    t=int(input())
    
    for tcs in range(t):
        n=int(input())
        arr=[int(x) for x in input().split()]
        
        
        dll=DoublyLinkedList()
        tail=None
        
        for e in arr:
            tail=dll.push(e,tail)
        
        resHead=reverseDLL(dll.head)
        dll.printList(resHead)
        print()

Answer

The problem in reverseDLL is that it never changes head.next. As head will become the last node in the reversed list, it will keep pointing the one-but-last as the next node, which in turn links to that final node again, … leading to the infinite loop.

So you should change this line:

temp=head

With this:

head.next = None

Other Remarks

Although the above will fix your immediate problem, there are some other things to consider:

• If you pass an empty list (head = None) to that function, it will throw an error. There should be a check for this potential None value.

• You have a DoublyLinkedList class, but then provide the above function as stand alone function. It would make more sense if it were a method of this class. That way, the head member of the class instance can be updated when the list is reversed, and remains self-consistent.

• While you have defined head as a member of that class, you have not defined tail as a member. Instead you require the push method to get the current tail reference, and it returns the new tail. This is strange. You should really consider tail to be an instance member that is maintained by the class, not by the caller of its methods.

• printList is defined as a method of this class, but still you have to provide it the head node as argument. This is strange: the class instance already has a head member, so you should not have to provide it as argument.

• I would not let a method have as a goal to print. Printing should be the responsibility of the caller (separation of concern). Note that none of the standard data structures (like list, dict,…) provide such print methods, and for a good reason. Instead of printList, provide a method that iterates of the list values. That way it becomes very easy for the caller to do what they want with it, like printing.

• To make printing super easy, provide your class with a __str__ implementation. This will return the string equivalent of the list. It gets called by default when you do print(dll)

• You can make the constructor of DoublyLinkedList more powerful by allowing it to get a list of values to start with.

• Instead of push returning a node, I would actually hide the Node instances completely from the caller. If you want to return something, then return the DoublyLinkedList instance itself. That way the caller can chain method calls one after the other, like dll.push(1).push(2).

Here is how I would have coded it:

class Node: 
    def __init__(self, data): 
        self.data = data  
        self.next = None
        self.prev = None
  
class DoublyLinkedList: 
    def __init__(self, values=None):
        self.head = None
        self.tail = None  # Should be member of the instance
        # Give possibility to immediate populate with values 
        if values:
            for data in values:
                self.push(data)
   
    def push(self, new_data):
        node = Node(new_data)
        node.prev = self.tail
        if not self.head:
            self.head = node
        else:
            self.tail.next = node
        self.tail = node  # Keep updated
        return self  # Allow chaining of method calls
        
    def __iter__(self): 
        node = self.head  # Instance method should use instance 
        while node is not None: 
            yield node.data   # Keep it generic: don't print, but yield
            node = node.next

    def __str__(self):
        return "->".join(map(str, self))

    def reverse(self):
        if not self.head:
            return  # Nothing to do
        prev = self.head
        curr = prev.next
        while curr:
            nxt = curr.next
            # Establish links between prev and curr
            curr.next = prev
            prev.prev = curr
            # Move on..
            prev = curr
            curr = nxt
        # Swap head/tail references
        self.head, self.tail = self.tail, self.head
        # Set the two None-links that every non-empty list has
        self.head.prev = None
        self.tail.next = None

And here is how you can use the above code:

dll = DoublyLinkedList([1,2,3,4,5])
print(dll)  # Quite easy to print thanks to __str__ and __iter__
dll.reverse()
print(dll)