Linked list implementation

In this post we can show how to implement a linked list in python.

In computer science , a linked list is a data structure used for collecting a sequence of objects, which allows efficient addition, removal and retrieval of elements from any position in the sequence. It is implemented as nodes, each of which contains a reference (i.e., a link) to the next and/or previous node in the sequence.

        A linked list whose nodes contain two fields: an integer value and a link to the next node

Linked lists are among the simplest and most common data structures. They can be used to implement several other common abstract data structures, including stacks, queues, associative arrays, and symbolic expressions.

The principal benefit of a linked list over a conventional array is that the list elements can easily be added or removed without reallocation or reorganization of the entire structure because the data items need not be stored contiguously in memory or on disk. Linked lists allow insertion and removal of nodes at any point in the list.

In python, we can simply implement a linked list by using class.

class node:
    def __init__(self):
        self.data = None # contains the data
        self.next = None # pointer to next node
class linked_list:
    def __init__(self):
        self.pointer = None
    def add_node(self, data):
        new_node = node() # create new node
        new_node.data = data
        new_node.next = self.pointer # Link the pointer to the  previous node
        self.pointer = new_node #  set the current node to the new one.
    def list_print(self):
        node = ll.pointer
        while node:
            print node.data
            node = node.next
ll = linked_list() # Create an object of class 'Linked_list'
ll.add_node(21)
ll.add_node(32)
ll.add_node(45)
ll.list_print() # Print the node data

 Output:

anoop@anoop-laptop:~$ python linked.py
45
32
21

Program to find the power of a number using recursion

In the following example shows how to find the power of a number using recursion. 

def power(a,b):
    if b==0:
        return 1
    elif a==0:
        return 0
    elif b==1:
        return a
    else:
        return a*power(a,b-1)

print power(2,4)

Output:  16

Here the function 'power()' recursively called to find the power of a number.

This is the simple way to find the power of a number. But it is not a good way, that is it is not optimized. It means, suppose when the given power of a number is 100, then the function 'power()' is recursively called 99 times, also time complexity increases. 

Following program shows the optimized solution for the same problem.

def power(x,y):
    if y==0:
        return 1
    elif x==0:
        return 0
    elif y==1:
        return x
    elif y%2==0:
        var_even=power(x,y/2)
        return var_even*var_even
    else:
        var_odd=power(x,(y-1)/2)    
        return x*var_odd*var_odd
    

print power(5,10)

Output: 9765625

This is the optimized solution. Here also use the recursion, at the same time optimized recursive calls are done to find the power of a number.

That is, suppose 'n' is the power of a number 'x', and also it is an even number, then x^n=( x^n/2)*(x^n/2).

If it is in the case of odd number, x^n=x*(x^(n-1)/2)*(x^(n-1)/2). In this optimized case, the number of iterations are reduced, also we can reduce the time complexity.

Selection sort using python

def selection(list1):
        x=0
        while(x<len(list1)):
                small_index=x
                for y in range(x+1,len(list1)):
                        if list1[y]<list1[small_index]:
                                small_index=y
                list1[x],list1[small_index]=list1[small_index],list1[x]
                x+=1

        print "\nSorted list is : "
        print list1


def main():
        #Unsorted list
        list1=[5,2,8,6,5,9,0,3,11,54,67,34]
        selection(list1)

if __name__=='__main__':
        main()