Python Program for Double Linked List and Operations

Python Program for Double Linked List and Operations

Double Linked list is a linear data structure and it is used to store elements in sequence and maintains the links to previous and next element using pointers.
double linked list diagram
Double linked list contains three fields in each node.
  • 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();        
Output:
$ 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

Privacy Policy  |  Copyright@2017 - All Rights Reserved.  |  Contact us   |  Report website issues in Github   |  Facebook page   |  Google+ page

Email Facebook Google LinkedIn Twitter
^