Skip to main content

Linked List in Python


Single Linked List Implementation in Python:

What is a linked list?
A linked list is a linear data structure, in which the elements are not stored at contiguous memory locations. The elements in a linked list are linked using pointers.
In simple words, a linked list consists of nodes where each node contains a data field and a reference(link) to the next node in the list.



Below is the code for the following:
  1. Creating a linked list
  2. Inserting elements(at the beginning, at the end, at the middle, insert after an element, insert at an index, inserting a set of values together)
  3. Deleting elements (remove by value , remove at an index)
  4. Length of the list
  5. Removing odd numbers from the list
Source Code:

 class Node:
    def __init__(self,data=None,next=None):
        self.data=data
        self.next=next
class SingleLinkedList:
    
    def __init__(self):
        self.head=None 
    
    def insert_at_the_beginning(self,data):
        node=Node(data,self.head)
        self.head=node
        
    def print_list(self):
        if self.head is None:
            print("Linked list is empty ")
            return
        itr=self.head
        elements=''
            
        while itr:
            elements+=str(itr.data)+'-->'
            itr=itr.next
            
        print(elements)
            
    def insert_at_the_end(self,data):
        if self.head is None:
            self.head=Node(data,None)
            return
        itr=self.head
        while itr.next:
            itr=itr.next
        itr.next=Node(data,None)
        
    def insert_values(self,data_list):
        self.head=None
        for x in data_list:
            self.insert_at_the_end(x)
            
    def get_length(self):
        itr=self.head
        len=0
        while itr:
            len+=1
            itr=itr.next
        return len
        
    def remove_at(self,index):
        if index==0:
            self.head=self.head.next
            return
        if index<0 or index>self.get_length():
            raise Exception("Invalid Index")
            return
        count=0
        itr=self.head
        while itr:
            if count==index-1:
                itr.next=itr.next.next
                break
            itr=itr.next
            count+=1
            
    def insert_at(self,index,data):
        if index==0:
            self.insert_at_the_beginning(data)
            return
        if index<0 or index>self.get_length():
            raise Exception("Invalid Index")
            return
        count=0
        itr=self.head
        while itr:
            if count==index-1:
                node=Node(data,itr.next)
                itr.next=node
                break
            
            itr=itr.next
            count+=1
        
    def insert_after(self,data_after,data_to_insert):
        #search for first occurences of data_after in linked list 
        #insert data_to_insert value after the node with data_after value 
        itr=self.head
        while itr:
            if(itr.data==data_after):
                node=Node(data_to_insert,itr.next)
                itr.next=node 
                break
            itr=itr.next
    
    def remove_by_value(self,data):
        #remove first node that contain data 
        itr=self.head
        index=0
        while itr:
            if(itr.data==data):
                break
            itr=itr.next
            index+=1
        self.remove_at(index)
    
    def remove_odds(self):
        # special case: head node
        # remove odd head elements by simply setting head to the next element after
        while (self.head is not None) and (self.head.data % 2 == 1):
            self.head = self.head.next
        # regular case: the rest of the nodes
        itr = self.head
        while (itr is not None) and (itr.next is not None):
            # if the next node's data is odd, then
            if itr.next.data % 2 == 1:
                # skip that node by pointing this node's .next to the next node's .next
                itr.next = itr.next.next
            # otherwise, move forwards in the list
            else:
                itr = itr.next
    
if __name__=='__main__':
    
    sll=SingleLinkedList()
    sll.insert_at_the_beginning(2)
    sll.insert_at_the_beginning(1)
    sll.insert_at_the_beginning(0)
    sll.insert_at_the_beginning(3)
    sll.insert_at_the_beginning(14)
    sll.insert_at_the_beginning(13)
    sll.print_list()
    print(sll.get_length())
    sll.remove_odds()
    sll.print_list()
    
    sll.insert_at_the_end(10);
    sll.insert_at_the_end(20);
    sll.print_list()
    print(sll.get_length())
    
    sll2=SingleLinkedList()
    sll2.insert_values([10,20,30,40,50])
    sll2.print_list()
    print(sll2.get_length())
    
    sll3=SingleLinkedList()
    sll3.insert_values(['apple','ball','cat','dog','egg'])
    sll3.print_list()
    print(sll3.get_length())
    
    sll3.remove_at(3)
    sll3.print_list()
    print(sll3.get_length())
    
    sll3.insert_at(0,'app')
    sll3.print_list()
    
    sll3.insert_at(2,'orange')
    sll3.print_list()
    
    sll3.insert_at(4,'mango')
    sll3.print_list()
    
    sll3.remove_by_value('apple')
    sll3.print_list()
    
    sll3.insert_after('mango','banana')
    sll3.print_list()


_____________________________________________________________________________

Related articles:
Removing odd numbers from a linked list
Stacks and Queues in python


______________________________________________________________________________

Please Like, Comment and Share for more! 😉

Labels:

Comments

Post a Comment

Popular posts from this blog

Fibonacci Pattern/Series C program

C Program to print fibonacci pattern till N Input: 5 (N value) Output: 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 Solution:   #include <stdio.h> int Fibonacci(int num){     if(num<=1)         return num;     else     return Fibonacci(num-1)+Fibonacci(num-2) ;//2,1 } int main() { int n,f=1;     scanf("%d",&n);     for(int row=1;row<=n;row++,printf("\n")){         for(int col=1;col<=row;col++){             printf("%d\t",Fibonacci(f++));         }     }     return 0; } ___________________________________________________________ Please Like, Comment and Share! 😉
2 comments
Read more

Leetcode Solutions (Array101) in C++

Max Consecutive Ones Given a binary array  nums , return  the maximum number of consecutive  1 's in the array . Example1: Input: nums=[1,1,0,1,1,1] Output: 3 Explanation:   The first two digits or the last three digits are consecutive 1s.  The maximum number of consecutive 1s is 3. Example2: Input: nums=[1,0,1,1,0,1] Output: 2 Constraints: 1 <= nums.length <= 10 5 nums[i]  is either  0  or  1 . CPP Code:     int findMaxConsecutiveOnes(vector<int>& nums) {         int max=0,count=0;         for (int x: nums)         {             if(x==1){                 count++;                 if(count>max)                     max=count;             }         ...
Post a Comment
Read more

Removing Odd numbers from a linked list

Deleting odd numbers from a linked list in python: In this program, we will see  how to remove odd numbers from a linked list in Python. This is a very interesting program where we will learn how to remove odd numbers from a linked list. This contains a very easy to understand method of making a linked list. So when you know how to use the linked list we will learn how to remove odd numbers from it. (Note that the program done here is done without using recursion for further simplicity). For removing odd number we first find out the position of the “ head “.  The head is the starting node in a linked list.   Source Code:   class Node:     def __init__(self,data=None,next=None):         self.data=data         self.next=next class SingleLinkedList:          def __init__(self):         self.head=None           def print_list(self):   ...
Post a Comment
Read more