Python Programming Singly Linked List

Singly linked list python program

Linked list is a linear data structure and it is used to store elements in sequence and maintains the links to next element using pointers.
singly linked list diagram
Singly linked list contains two fields in each node.
  • Data
  • Pointer to next element
#!/usr/bin/python                                                               

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

# inserts new node at specific position in singly 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, temp_next);                                                
    current_node.next = node;                                                               
            
# prints singly linked list values.                                                                    
def print_list():                                                               
    global head, tail;                                                          
    print("Single 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 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:                                       
                previous_node.next = current_node.next;                         
            else:                                                               
                head = current_node.next;                                       
        previous_node = current_node;                                           
        current_node = current_node.next;                                       
                            
# reverses singly linked list values.                                                    
def reverse_linked_list():                                                      
    global head, tail;                                                          
    current_node = head;                                                        
    previous_node = None;                                                       
    while(current_node is not None):                                            
        next_node = current_node.next;                                          
        current_node.next = previous_node;                                      
        previous_node = current_node;                                           
        current_node = next_node;                                               
        head = previous_node;  

# getting nodes count in singly 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 "Single 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();                                                               
    remove_node(13);                                                            
    print "After removal of node 13";                                           
    print_list();                                                               
    reverse_linked_list();                                                      
    print "After reversing singly linked list";                                 
    print_list();  
    count();       
Output:
$ python singly_linked_list.py 
Single linked list
head --> 20 --> 13 --> 24 --> 56 --> End
After insert node at 2
Single linked list
head --> 20 --> 13 --> 45 --> 24 --> 56 --> End
After removal of node 13
Single linked list
head --> 20 --> 45 --> 24 --> 56 --> End
After reversing singly linked list
Single linked list
head --> 56 --> 24 --> 45 --> 20 --> End
Single 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
^