Python Program for Double Linked List and Operations

Python Program for Double Linked List and Operations

• Data
• Pointer to previous element
• Pointer to next element

#!/usr/bin/python                                                               

# Each double linked list item has value, pointer to previous value and pointer to next value.                                                                                                                                                             
class Node:                                                                     
     def __init__(self, val, prev_ref, next_ref):                               
         self.val = val;                                                        
         self.prev = prev_ref;                                                  
         self.next = next_ref;                                                    
                                                                                
       
# Global variable for header and tail pointer in double linked list.                                                                         
head = tail = None;                                                             
         
# appends new node at the end in double linked list.                                                                       
def append_node(val):                                                           
    global head, tail;                                                          
    node = Node(val, None, None);                                               
    if head is None:                                                            
        head = node;                                                            
    else:                                                                       
        tail.next = node;                                                       
        node.prev = tail;                                                       
    tail = node;      

# inserts new node at specific position in double linked list.
def insert_node(val, position):                                                 
    global head, tail;                                                          
    current_node = head;                                                        
    while(position > 1):                                                        
        position -= 1;                                                          
        current_node = current_node.next;                                       
    temp_next = current_node.next;                                              
    node = Node(val, current_node, temp_next);                                  
    current_node.next = node;                                                   
    if(temp_next.next is not None):                                             
        temp_next.prev = node;                                                               
            
# prints double linked list values.                                                                    
def print_list():                                                               
    global head, tail;                                                          
    print("Double linked list");                                                
    current_node = head;                                                        
    print "head <==>",;                                                         
    while(current_node is not None):                                            
        print current_node.val, "<==>",;                                        
        current_node = current_node.next;                                       
    print "End";                 
                                              
# removes matching first node for particular value in double linked list.                                                                              
def remove_node(val):                                                           
    global head, tail;                                                          
    current_node = head;                                                        
    previous_node = None;                                                       
    while(current_node is not None):                                            
        if current_node.val == val:                                             
            if previous_node is not None:                                       
                current_node.next.prev = current_node.prev;                     
                previous_node.next = current_node.next;                         
            else:                                                               
                current_node.next.prev = None;                                  
                head = current_node.next;                                       
        previous_node = current_node;                                           
        current_node = current_node.next;                                     
                            
# reverses double linked list values.                                                    
def reverse_linked_list():                                                      
    global head, tail;                                                          
    print("Double linked list reverse order");                                  
    current_node = tail;                                                        
    print "tail <==>",;                                                         
    while(current_node is not None):                                            
        print current_node.val, "<==>",;                                        
        current_node = current_node.prev;                                       
    print "End";   

# getting nodes count in double linked list.
def count():                                                                    
    global head, tail;                                                          
    current_node = head;                                                        
    counter = 0;                                                                
    while(current_node is not None):                                            
        counter += 1;                                                           
        current_node = current_node.next;                                       
    print "Double linked list node count:", counter;                            
                                                                                
if __name__ == "__main__":                                                      
    append_node(20);                                                            
    append_node(13);                                                            
    append_node(24);                                                            
    append_node(56);                                                            
    print_list();                                                               
    insert_node(45, 2);                                                         
    print "After insert node at 2";                                             
    print_list();                                                               
    reverse_linked_list();                                                      
    remove_node(13);                                                            
    print "After removal of node 13";                                           
    print_list();                                                               
    reverse_linked_list();                                                      
    count();        

$ python double_linked_list.py 
Double linked list
head <==> 20 <==> 13 <==> 24 <==> 56 <==> End
After insert node at 2
Double linked list
head <==> 20 <==> 13 <==> 45 <==> 24 <==> 56 <==> End
Double linked list reverse order
tail <==> 56 <==> 24 <==> 45 <==> 13 <==> 20 <==> End
After removal of node 13
Double linked list
head <==> 20 <==> 45 <==> 24 <==> 56 <==> End
Double linked list reverse order
tail <==> 56 <==> 24 <==> 45 <==> 20 <==> End
Double linked list node count: 4