Search code examples
pythondoubly-linked-list

How does implementation of reverse of doubly linked list work?


How does implementation of reverse of doubly linked list in Python work? Specifically current = current.prev and head=temp.prev

def reverse(head):
    temp = None
    current = head 
        
    
    while current is not None: 
        temp = current.prev  
        current.prev = current.next
        current.next = temp 
        current = current.prev 

    
    if temp is not None: 
        head = temp.prev 
    return head

Solution

  • Take a Doubly linked list: [1] <-> [2] <-> [3]

     head = 1
     temp = None
     current = head = 1
    
     while current is not None:
         # loop 1, current = 1
         temp = head.prev = None
         current.prev = current.next = 2
         current.next = temp = None
         current = current.next = 2
         # This now looks like this
         # [2] <- [1] -> None 
         # loop 2, current = 2
         temp = current.prev = 1
         current.prev = current.next = 3
         current.next = temp = 1
         current = current.next = 3
         # Now we have
         # [3] <- [2] <-> [1] -> None
         # Last time: 
         temp = current.prev = 2
         current.prev = current.next = None
         current.next = temp = 2
         current = current.next = None
         # [3] <-> [2] <-> [1]
         # break out of loop
    
              
    # I think this should be while temp is not None
    if temp is not None:
        temp = 2
        head = temp.prev = 3
    
    return head