Reverse Doubly Linked List

Source Code

class Node:
   def __init__(self,data):
        self.data = data
        self.left = None
        self.right = None

class Dll:
    def __init__(self):
        self.start = None

    def createlist(self):
         n=int(input("enter no of nodes"))
         for i in range(n):
            data = int(input("enter value"))
            newnode = Node(data)
            if self.start == None:
               self.start = newnode
            else:
               temp=self.start
               while temp.right != None:
                 temp=temp.right
               temp.right=newnode
               newnode.left=temp     

    def count(self):
        nc=0
        temp=self.start
        while temp!=None:
           nc=nc+1
           temp=temp.right
        print("number of nodes till now:%d" %nc)
        return nc               

    def display(self):
      print("elements in double linked list are:")
      if self.start == None:
            print("empty")
      else:
         temp=self.start
         while temp!= None:
            print("%d" %(temp.data))
            temp=temp.right
    def rev(self):     
        current = self.start       
        while current!=None:
            temp = current.left 
            current.left = current.right
            current.right = temp
            current = current.left       
        if temp!=None:
            self.start = temp.left
        print("Reverse done")

def menu():
    print("1.createlist\n2.count\n3.display\n4.reverse\n5.exit\n")   
def stop():
    print("you are about to terminate the program")
    exit(0)   
s=Dll()
def default():
    print("check your input")
menu()
while True:
    menu= {
    1: s.createlist,   
    2: s.count,
    3: s.display,
    4: s.rev,
    5:stop}
    option = int(input("Please enter your choice"))
    menu.get(option,default)()

output:

1.createlist

2.count

3.display

4.reverse

5.exit

Please enter your choice1

enter no of nodes3

enter value1

enter value2

enter value3

Please enter your choice2

number of nodes till now:3

Please enter your choice3

elements in double linked list are:

1

2

3

Please enter your choice4

Reverse done

Please enter your choice3

elements in double linked list are:

3

2

1

Please enter your choice5

Binary Search

This searching technique is applied on sorted list. First calculate mid point then follow the following procedure

1. Check whether a[mid] and key are equal , if condition is true print the position, if this is false

2.Compare whether key is greater than a[mid] ,if this is true update l to mid+1 and repeat the above procedure, if this is false

3. Update h to mid -1 and repeat the above procedure.

4. If all the above conditions are false print 'key not found'

Source Code: 

a=[]

flag=0

n=int(input("enter how many number of elements"))

for i in range(n):

    a.append(int(input()))

print("List is:\n")

print(a)

key=int(input("enter key"))

l=0

h=n-1

while l<=h:

    mid=(l+h)//2

    if key==a[mid]:

        flag=1

        break

    elif key>a[mid]:

        l=mid+1

    else:

        h=mid-1

if flag==1:

    print("%d found at %d position" %(key,mid))

else:

    print("%d not found" %key)

Output:

Python 3.4.0 (v3.4.0:04f714765c13, Mar 16 2014, 19:24:06) [MSC v.1600 32 bit (Intel)] on win32

Type "copyright", "credits" or "license()" for more information.

>>> ================================ RESTART ================================

>>> 

enter how many number of elements5

1

2

3

4

5

List is:

[1, 2, 3, 4, 5]

enter key10

10 not found

>>> ================================ RESTART ================================

>>> 

enter how many number of elements5

1

2

3

4

5

List is:

[1, 2, 3, 4, 5]

enter key1

1 found at 0 position

>>> ================================ RESTART ================================

>>> 

enter how many number of elements5

1

2

3

4

5

List is:

[1, 2, 3, 4, 5]

enter key2

2 found at 1 position

>>> ================================ RESTART ================================

>>> 

enter how many number of elements5

1

2

3

4

5

List is:

[1, 2, 3, 4, 5]

enter key5

5 found at 4 position

>>> 

Quick Sort using Python

Quick sort is a divide and conquer algorithm. In this sort pivot element is chosen for sorting. Usually first element of the list is chosen as pivot element. In this sorting comparison is done to move in forward direction and also in backward direction.

To move in forward direction (from left to right) element values should be less than or equal to pivot element value.

When this condition fails now start moving in backward direction(from right to left), to move so elements values should  be greater than pivot element.

When the above two conditions fail compare value of i and j, if i is less than j, swap a[i] and a[j].

When the above three conditions fails swap a[j] and a[p]. At this point list is broken in to two parts. The left part of pivot  contain elements less than pivot value and the right part contain elements greater than pivot value. Repeat the above process until sorted list is obtained.

Source Code:

def qsort(a,left,right):
    if left<right:
        i=left
        j=right
        p=left
        while i<j:
            while a[i]<=a[p] and i<right:
                i=i+1
            while a[j]>a[p] and j>left:
                j=j-1
            if i<j:
                a[i],a[j]=a[j],a[i]
        a[p],a[j]=a[j],a[p]
        qsort(a,left,j-1)
        qsort(a,j+1,right)
a=[]
n=int(input("enter number of elements"))
for i in range(n):
    a.append(int(input()))
print("List before sorting")
print(a)
left=0
right=n-1
qsort(a,left,right)
print("List after sorting")

print(a)

Output:

Python 3.4.0 (v3.4.0:04f714765c13, Mar 16 2014, 19:24:06) [MSC v.1600 32 bit (Intel)] on win32

Type "copyright", "credits" or "license()" for more information.

>>> ================================ RESTART ================================

>>> 

enter number of elements5

3

4

2

5

1

List before sorting

[3, 4, 2, 5, 1]

List after sorting

[1, 2, 3, 4, 5]

>>>

Now my new Blog on Fundamentals of Python can be found at https://fundamentalsofpython.blogspot.com/2020/02/list-manipulations.html

Selection sort

As per my logic selection sort find minimum element from the list and put it in the starting of the list at the end of first iteration. In the second iteration second minimum element is placed in the second position and so on.

Source Code:

a=[]

n=int(input("Enter number of elements"))

for i in range(n):

    a.append(int(input()))

print("List before sorting")

print(a)

for i in range(n):

    for j in range(i+1,n):

        if a[i]>a[j]:

            a[i],a[j]=a[j],a[i]

print("List after sorting")

print(a)

Output:

Enter number of elements5

5

4

3

2

1

List before sorting

[5, 4, 3, 2, 1]

List after sorting

[1, 2, 3, 4, 5]

Insertion Sort using python

This is comparison based sorting. Playing cards is an example of insertion sort.

Source Code:

def insertion(a,n):
    for i in range(n):
        temp=a[i]
        j=i
        while j>0 and a[j-1]>temp:
            a[j]=a[j-1]
            j=j-1
            a[j]=temp
a=[]
n=int(input("Enter number of elements"))
for i in range(n):
    a.append(int(input()))
print("list before sorting")
print(a)
insertion(a,n)
print("list after sorting")

print(a)

Output:

Python 3.4.0 (v3.4.0:04f714765c13, Mar 16 2014, 19:24:06) [MSC v.1600 32 bit (Intel)] on win32

Type "copyright", "credits" or "license()" for more information.

>>> ================================ RESTART ================================

>>> 

Enter number of elements5

10

30

20

11

5

list before sorting

[10, 30, 20, 11, 5]

list after sorting

[5, 10, 11, 20, 30]

>>> 

Fibonacci Search

Fibonacci Search is a searching technique, where key position is found by using fibonacci list. In this technique two lists are used  one is input list and one is fibonacci list. For this search input list should contain numbers in ascending order.

Source Code:

def fibonacii(a,key):
    fib=[0,1,1,2,3,5,8,13]
    k=len(a)
    begin=0
    while k>0:
        k=k-1
        pos = begin+fib[k]
        if key == a[pos]:
            return pos
        elif key<a[pos]:
            continue
        else:
            begin=pos+1
            k=k-3
    return -1
a=[]
n=int(input("how many elements u want to enter"))
for i in range(n):
    a.append(int(input()))
key=int(input("enter the key"))
p=fibonacii(a,key)
if p==-1:
    print("%d not found" %key)
else:

    print("%d is found" %key)

Output:

how many elements u want to enter5

1

2

3

4

5

enter the key1

1 is found

>>> ================================ RESTART 

how many elements u want to enter5

1

2

3

4

5

enter the key3

3 is found

>>> ================================ RESTART  

how many elements u want to enter5

1

2

3

4

5

enter the key5

5 is found

>>> ================================ RESTART  

how many elements u want to enter5

1

2

3

4

5

enter the key100

100 not found

>>> 

Merge Sort using Python

Merge sort contains two phases.
1. Partition phase
2. Merge phase

In partition phase the list is broken in to parts by calculating mid point.
In merging phase the list is merged by sorting. Finally a sorted list is obtained.

 Merge sort is a divide and conqure algorithm. Divide and Conqure means divide the problem in to small parts, solve these sub parts and finally combine the solutions to get the final answer.

Source Code:

def part(a,l,r):
    if l<r:
        m=(l+r)//2
        part(a,l,m)
        part(a,m+1,r)
        merge(a,l,m,r)
    #print(b)
def merge(a,l,m,r):
    b=[]
    k=0
    i=l
    j=m+1
    while i<=m and j<=r:
        if a[i]<a[j]:
            b.append(a[i])
            k=k+1
            i=i+1
        else:
            b.append(a[j])
            k=k+1
            j=j+1
    while i<=m:
        b.append(a[i])
        k=k+1
        i=i+1
    while j<=r:
        b.append(a[j])
        k=k+1
        j=j+1
    for i in range(k):
        a[l]=b[i]
        l=l+1
a=[ ]
n=int(input("enter n"))
for i in range(n):
    a.insert(i,int(input()))
l=0
r=n-1
part(a,l,r)
print(a)
   
Output:   

Python 3.4.0 (v3.4.0:04f714765c13, Mar 16 2014, 19:24:06) [MSC v.1600 32 bit (Intel)] on win32
Type "copyright", "credits" or "license()" for more information.
>>> ================================ RESTART ================================
>>>
enter n5
10
5
3
7
2
[2, 3, 5, 7, 10]
>>>


       

Queue Using List

Queue is a linear data structure. Queue has  First In First Out (FIFO) policy. In Queue elements are inserted at one end and deleted at other end. Queue does the insertion by using rear variable and deletion by using front variable. Rear value increases by one unit at insertion and Front value increases by one unit at deletion.

Source Code:

def display():
    if not MyQueue:
        print("queue is empty")
    else:
        print(MyQueue)
def insert():
    global rear
    if rear < size:
        value=int(input("enter number"))
        MyQueue.append(value)
        rear=rear+1
    else:
        print("Queue overflow!")
def delete():
    global front
    if not MyQueue:
        print("queue underflow")
    else:
        print("element deleted is %d" %MyQueue[front])
        del MyQueue[front]
def stop():
    print("you are about to terminate the program")
    exit(0)
def menulist():
    print("1.insert\n2.delete")
    print("3.display")
    print("4.exit")
def default():
    print("check your input")
MyQueue = []
rear=0
front=0
size=int(input("enter the size of queue"))
menulist()
while True:
    menu= {
    1: insert,
    2: delete,
    3: display,
    4: stop}
    option = int(input("Please enter your choice"))
    menu.get(option,default)()


Output:

Python 3.4.0 (v3.4.0:04f714765c13, Mar 16 2014, 19:24:06) [MSC v.1600 32 bit (Intel)] on win32
Type "copyright", "credits" or "license()" for more information.
>>> ================================ RESTART ================================
>>>
enter the size of queue3
1.insert
2.delete
3.display
4.exit
Please enter your choice1
enter number10
Please enter your choice1
enter number20
Please enter your choice1
enter number30
Please enter your choice3
[10, 20, 30]
Please enter your choice1
Queue overflow!
Please enter your choice2
element deleted is 10
Please enter your choice3
[20, 30]
Please enter your choice2
element deleted is 20
Please enter your choice3
[30]
Please enter your choice2
element deleted is 30
Please enter your choice3
queue is empty
Please enter your choice2
queue underflow
Please enter your choice4
you are about to terminate the program

>>>

Stack using Lists

Queue is a linear data structure. Queue has  First In First Out (FIFO) policy. In Queue elements are inserted at one end and deleted at other end. Queue does the insertion by using rear variable and deletion by using front variable. Rear value increases by one unit at insertion and Front value increases by one unit at deletion.

Source Code:

MyStack = []
size=int(input("enter the size of stack"))
def display():
 print("Stack currently contains:")
 for Item in MyStack:
  print(Item)
def push():
 if len(MyStack) < size:
    value=int(input("enter number"))
    MyStack.append(value)
 else:
  print("Stack is overflow!")
def pop():
 if len(MyStack) > 0:
  MyStack.pop()
 else:
  print("Stack is underflow.")
def stop():
    print("you are about to terminate the program")
    exit(0)
def menulist():
    print("1.push\n2.pop")
    print("3.display")
    print("4.exit")
def default():
    print("check your input")
menulist()
while True:
    menu= {
    1: push,
    2: pop,
    3: display,
    4: stop}
    option = int(input("Please enter your choice"))
    menu.get(option,default)()



Output:

Python 3.4.0 (v3.4.0:04f714765c13, Mar 16 2014, 19:24:06) [MSC v.1600 32 bit (Intel)] on win32
Type "copyright", "credits" or "license()" for more information.
>>> ================================ RESTART ================================
>>>
enter the size of stack3
1.push
2.pop
3.display
4.exit
Please enter your choice1
enter number10
Please enter your choice1
enter number20
Please enter your choice1
enter number30
Please enter your choice3
Stack currently contains:
10
20
30
Please enter your choice1
Stack is overflow!
Please enter your choice2
Please enter your choice3
Stack currently contains:
10
20
Please enter your choice2
Please enter your choice3
Stack currently contains:
10
Please enter your choice2
Please enter your choice3
Stack currently contains:
Please enter your choice2
Stack is underflow.

Please enter your choice4

Linear Search Using Python

Linear Search is the simplest way of searching key element from the list of elements. In linear search the order of elements can be in ascending order or can be in descending order. The elements in the list can be redundant. Time complexity of this search is O(n).

Source Code:

a=[]
count=0
n=int(input("how many elements u want to enter"))
for i in range(n):
    num=int(input("enter number"))
    a.append(num)
print(a)
key=int(input("enter the key to be serched"))
for i in range(n):
    if key==a[i]:
        print("%d found in %d" %(key,i))
        count=count+1
if count==0:
    print("%d not found" %key)
else:
    print("%d found %d time(s)" %(key,count))

Output:

Python 3.4.0 (v3.4.0:04f714765c13, Mar 16 2014, 19:24:06) [MSC v.1600 32 bit (Intel)] on win32

Type "copyright", "credits" or "license()" for more information.

>>> ================================ RESTART ================================

>>> 

how many elements u want to enter6

enter number1

enter number2

enter number3

enter number4

enter number5

enter number6

[1, 2, 3, 4, 5, 6]

enter the key to be serched3

3 found in 2

3 found 1 time(s)

>>> ================================ RESTART ================================

>>> 

how many elements u want to enter6

enter number1

enter number2

enter number3

enter number3

enter number4

enter number5

[1, 2, 3, 3, 4, 5]

enter the key to be serched3

3 found in 2

3 found in 3

3 found 2 time(s)

>>> 

Binary Search Tree

Binary Search Tree 

Binary search tree is a binary tree where node values greater than root node are placed towards right side of root and node values less than or equal to root node are placed towards left side of root.

Source Code:

class Node:
    def __init__(self,data):
        self.data=data
        self.rchild=None
        self.lchild=None
class Bst:
    def __init__(self):
        self.root=None             
 
    def createtree(self,data):
        if self.root==None:
            self.root = Node(data)
        else:
            temp = self.root
            while temp !=None:
                if data < temp.data:
                    if temp.lchild==None:
                        temp.lchild = Node(data)
                        return
                    else:
                        temp = temp.lchild
                else:
                    if temp.rchild==None:
                        temp.rchild = Node(data)
                        return
                    else:
                        temp = temp.rchild
     
    def inorder(self, root):
        if root!=None:
            self.inorder(root.lchild)
            print(root.data)
            self.inorder(root.rchild)
 
    def preorder(self, root):
        if root!=None:
            print(root.data)
            self.preorder(root.lchild)         
            self.preorder(root.rchild)
         
    def postorder(self,root):
        if root!=None:
            self.postorder(root.lchild)         
            self.postorder(root.rchild)
            print(root.data)

    def display(self,root):
        if root!=None:         
            print(root.data)
            self.inorder(root.rchild)
            self.inorder(root.lchild)
         
    def count(self, root):
        if root == None:
            return 0
        else:
            return 1 + self.count(root.lchild) + self.count(root.rchild)

def menu():
    global ch
    print("\n1.create\n2.preorder\n3.postorder\n4.inorder
                   \n5.display\n6.count\n7.stop")
    ch=int(input("enter u r choice"))

t=Bst()
while True:
    menu()
    if ch==1:
         n=int(input("enter no of node for tree"))
         for i in range(n):
            data=int(input("enter data"))
            t.createtree(data)
    elif ch==2:
       print("preorder")
       t.preorder(t.root)
    elif ch==3:
       print("postorder")
       t.postorder(t.root)
    elif ch==4:
       print("inorder")
       t.inorder(t.root)
    elif ch==5:
       t.display(t.root)
    elif ch==6:
        print("number of nodes in binary search tree")
        print(t.count(t.root))
    else:
        exit(0)
 

 

 


 

Output:

Python 3.4.0 (v3.4.0:04f714765c13, Mar 16 2014, 19:24:06) [MSC v.1600 32 bit (Intel)] on win32
Type "copyright", "credits" or "license()" for more information.
>>> ================================ RESTART ================================
>>>

1.create
2.preorder
3.postorder
4.inorder
5.display
6.count
7.stop
enter u r choice1
enter no of node for tree3
enter data20
enter data10
enter data30

1.create
2.preorder
3.postorder
4.inorder
5.display
6.count
7.stop
enter u r choice2
preorder
20
10
30

1.create
2.preorder
3.postorder
4.inorder
5.display
6.count
7.stop
enter u r choice3
postorder
10
30
20

1.create
2.preorder
3.postorder
4.inorder
5.display
6.count
7.stop
enter u r choice4
inorder
10
20
30

1.create
2.preorder
3.postorder
4.inorder
5.display
6.count
7.stop
enter u r choice5
20
30
10

1.create
2.preorder
3.postorder
4.inorder
5.display
6.count
7.stop
enter u r choice6
number of nodes in binary search tree
3

1.create
2.preorder
3.postorder
4.inorder
5.display
6.count
7.stop
enter u r choice7
>>>

Now my new Blog on Fundamentals of Python can be found at https://fundamentalsofpython.blogspot.com/2020/02/list-manipulations.html

Sparse Matrix Using Linked List

This is sparse matrix program. A matrix in which number of zeros are greater than half the size of matrix is known as sparse matrix.

Source Code:

class Node:
  def __init__(self,r,c,v):
    self.r=r
    self.c=c
    self.v=v
    self.next=None
class Sparse:
  def __init__(self):
    self.start=None
  def createlist(self,newnode):
    temp=self.start
    if self.start==None:
      self.start=newnode
    else:
      while temp.next!=None:
        temp=temp.next
      temp.next=newnode
  def display(self):
    temp=self.start
    print("row\tcol\tval")
    while temp!=None:
      print("%d\t%d\t%d" %(temp.r,temp.c,temp.v))
      temp=temp.next

row=int(input("enter number of rows : "))
col=int(input("enter number of coloumns : "))

X = [[0]*col for j in range(row)]
count=0
sp=Sparse()
print ("entry elements")
for i in range (row):
  for j in range (col): 
    X[i][j] = int(input())

print("matrix is:")
for i in range(row):
    for j in range(col):
        print(X[i][j], end=' ')
    print()

for i in range(row):
    for j in range(col):
        if X[i][j]==0:
            count=count+1

print("number of zeros:",count)

if count>(row*col)//2:
    print("sparse matrix")
    for i in range(row):
      for j in range(col):
        if X[i][j]!=0:
          newnode=Node(i,j,X[i][j])
          sp.createlist(newnode)       
    sp.display()
else:

    print("not sparse matrix")

Output:

Python 3.4.0 (v3.4.0:04f714765c13, Mar 16 2014, 19:24:06) [MSC v.1600 32 bit (Intel)] on win32

Type "copyright", "credits" or "license()" for more information.

>>> ================================ RESTART ================================

>>> 

enter number of rows : 3

enter number of coloumns : 3

entry elements

1

2

3

0

0

0

4

5

6

matrix is:

1 2 3 

0 0 0 

4 5 6 

number of zeros: 3

not sparse matrix

>>> ================================ RESTART ================================

>>> 

enter number of rows : 3

enter number of coloumns : 3

entry elements

1

2

3

0

0

0

0

0

4

matrix is:

1 2 3 

0 0 0 

0 0 4 

number of zeros: 5

sparse matrix

row col val

0 0 1

0 1 2

0 2 3

2 2 4

>>>

Now my new Blog on Fundamentals of Python can be found at https://fundamentalsofpython.blogspot.com/2020/02/list-manipulations.html

Sparse Matrix Using List

This is sparse matrix program. A matrix in which number of zeros are greater than half the size of matrix is known as sparse matrix.

Source Code:

row=int(input("enter number of rows : "))
col=int(input("enter number of coloumns : "))

X = [[0]*col for j in range(row)]
count=0

print ("entry elements")
for i in range (row):
  for j in range (col): 
    X[i][j] = int(input())

print("matrix is:")
for i in range(row):
    for j in range(col):
        print(X[i][j], end=' ')
    print()

for i in range(row):
    for j in range(col):
        if X[i][j]==0:
            count=count+1

print("number of zeros:",count)

if count>(row*col)//2:
    print("sparse matrix")
else:

    print("not sparse matrix")

Output:

Python 3.4.0 (v3.4.0:04f714765c13, Mar 16 2014, 19:24:06) [MSC v.1600 32 bit (Intel)] on win32

Type "copyright", "credits" or "license()" for more information.

>>> ================================ RESTART ================================

>>> 

enter number of rows : 3

enter number of coloumns : 3

entry elements

1

2

3

0

0

0

4

5

6

matrix is:

1 2 3 

0 0 0 

4 5 6 

number of zeros: 3

not sparse matrix

>>> ================================ RESTART ================================

>>> 

enter number of rows : 3

enter number of coloumns : 3

entry elements

1

2

3

0

0

0

0

4

5

matrix is:

1 2 3 

0 0 0 

0 4 5 

number of zeros: 4

not sparse matrix

>>> ================================ RESTART ================================

>>> 

enter number of rows : 3

enter number of coloumns : 3

entry elements

1

2

3

0

0

0

0

0

4

matrix is:

1 2 3 

0 0 0 

0 0 4 

number of zeros: 5

sparse matrix

>>>

Now my new Blog on Fundamentals of Python can be found at https://fundamentalsofpython.blogspot.com/2020/02/list-manipulations.html

Towers of Hanoi using python

This is Towers of Hanoi program. This concept uses three towers namely source, intermediate and destination. The concept is to place the disks from source tower to destination tower. Smaller disk should be always on larger disk vice versa is not possible. The order of disks on source tower and on destination tower should be same. This concept uses recursion.

Source code:

def hanoi(n,s,i,d):
    if n==1:
        print("move 1 disk from",s,"to",d)
        return
    else:
        hanoi(n-1,s,d,i)
        hanoi(1,s,i,d)
        hanoi(n-1,i,s,d)

n=int(input("enter no of disks"))
hanoi(n,"s","i","d")

 

Output:

Python 3.4.0 (v3.4.0:04f714765c13, Mar 16 2014, 19:24:06) [MSC v.1600 32 bit (Intel)] on win32

Type "copyright", "credits" or "license()" for more information.

>>> ================================ RESTART ================================

>>> 

enter no of disks3

move 1 disk from s to d

move 1 disk from s to i

move 1 disk from d to i

move 1 disk from s to d

move 1 disk from i to s

move 1 disk from i to d

move 1 disk from s to d

>>>
Now my new Blog on Fundamentals of Python can be found at https://fundamentalsofpython.blogspot.com/2020/02/list-manipulations.html

Queue using Linked list

This program is about Queue using Linked list. This program contains functions
1.Insert
2.Delete
3.Display

Source code:

class Node:
    def __init__(self,data):
        self.data=data
        self.next=None
class Queuell:
    def __init__(self):
        self.rear=None
        self.front=None
    def insert(self):
        data=int(input("enter data"))
        newnode=Node(data)
        if self.front == None:
            self.front=newnode
            self.rear=newnode
        else:
            self.rear.next=newnode
            self.rear=newnode
        print("element inserted")
    def delete(self):
        if self.front == None:
            print("empty")
        else:
            temp=self.front
            print("element deleted is %d" %(temp.data))
            self.front=self.front.next
            del temp

    def display(self):
        if self.front==None:
            print("empty")
        else:
            temp=self.front
            print("elements in Queue")
            while temp!=None:
                print("%d" %(temp.data))
                temp=temp.next
def menu():
    print("1.insert\n2.delete\n3.display\n4.quit")
def stop():
    print("you are about to terminate the program")
    exit(0)     
s=Queuell()
def default():
    print("check your input")
menu()
while True:
    menu= {
    1: s.insert,
    2: s.delete,
    3: s.display,
    4: stop}
    option = int(input("Please enter your choice"))

    menu.get(option,default)()

Output:

Python 3.4.0 (v3.4.0:04f714765c13, Mar 16 2014, 19:24:06) [MSC v.1600 32 bit (Intel)] on win32

Type "copyright", "credits" or "license()" for more information.

>>> ================================ RESTART ================================

>>> 

1.insert

2.delete

3.display

4.quit

Please enter your choice1

enter data1

element inserted

Please enter your choice1

enter data2

element inserted

Please enter your choice1

enter data3

element inserted

Please enter your choice3

elements in Queue

1

2

3

Please enter your choice2

element deleted is 1

Please enter your choice3

elements in Queue

2

3

Please enter your choice2

element deleted is 2

Please enter your choice3

elements in Queue

3

Please enter your choice2

element deleted is 3

Please enter your choice3

empty

Please enter your choice4
Now my new Blog on Fundamentals of Python can be found at https://fundamentalsofpython.blogspot.com/2020/02/list-manipulations.html

Stacks Using Linked list

This program is stacks using linked list. the program covers the following funtions:
1.Push
2.Pop
3.Display

Source Code:


class Node:
    def __init__(self,data):
        self.data=data
        self.next=None
class Stackll:
    def __init__(self):
        self.start=None
        self.top=None
    def push(self):
        data=int(input("enter data"))
        newnode=Node(data)
        if self.start==None:
           self.start=newnode
           self.top=newnode
        else:
            temp=self.start
            while temp.next!=None:
                temp=temp.next
            temp.next=newnode
            top=newnode
    def pop(self):
        temp=self.start
        if temp.next ==None:
            print ("last element of stack deleted is %d" %(temp.data))
            self.start=None
            del self.top
            self.top=None
        else:
            temp=self.start
            prev=self.start
            while temp.next != None:
                prev=temp
                temp=temp.next
         
            prev.next=None
            del temp
     
 
    def display(self):
        if self.top==None:
            print("stack empty")
        else:
            temp=self.start
            print("elements in stack are")
            while temp!=None:
                print ("%d" %(temp.data))
                temp=temp.next
             
def menu():
    print("1.push\n2.pop\n3.display\n4.quit")
def stop():
    print("you are about to terminate the program")
    exit(0)     
s=Stackll()
def default():
    print("check your input")
menu()
while True:
    menu= {
    1: s.push,
    2: s.pop,
    3: s.display,
    4: stop}
    option = int(input("Please enter your choice"))
    menu.get(option,default)()

Output:

Python 3.4.0 (v3.4.0:04f714765c13, Mar 16 2014, 19:24:06) [MSC v.1600 32 bit (Intel)] on win32
Type "copyright", "credits" or "license()" for more information.
>>> ================================ RESTART ================================
>>>
1.push
2.pop
3.display
4.quit
Please enter your choice1
enter data10
Please enter your choice1
enter data20
Please enter your choice1
enter data30
Please enter your choice3
elements in stack are
10
20
30
Please enter your choice2
Please enter your choice3
elements in stack are
10
20
Please enter your choice2
Please enter your choice3
elements in stack are
10
Please enter your choice2
last element of stack deleted is 10
Please enter your choice3
stack empty

Please enter your choice4

Now my new Blog on Fundamentals of Python can be found at https://fundamentalsofpython.blogspot.com/2020/02/list-manipulations.html

     
         

Double linked list

This is python program for Double linked list concept. This code covers the following functions of Double linked list.
1.Creation of the list
2.Insertion at the beginning of the list
3. Insertion at the end of list
4. Insertion at intermediate position in the list
5. Deletion from the beginning of the list
6. Deletion at the end of the list
7.Deletion from intermediate position of the list
8.Count nodes of a list
9.Display the list
10.Reverse display

Source Code:

class Node:

   def __init__(self,data):
        self.data = data
        self.left = None
        self.right = None

class Dll:

    def __init__(self):
        self.start = None
     
   
    def createlist(self):
         n=int(input("enter no of nodes"))
         for i in range(n):
            data = int(input("enter value"))
            newnode = Node(data)
            if self.start == None:
               self.start = newnode
            else:
               temp=self.start
               while temp.right != None:
                 temp=temp.right
               temp.right=newnode
               newnode.left=temp
       

    def insertend(self):
        data=int(input("enter value"))
        newnode = Node(data)
        if self.start == None:
               self.start = newnode
        else:
           temp=self.start
           while temp.right != None:
                temp=temp.right
           temp.right=newnode
           newnode.left=temp
     

    def insertmid(self):
        data=int(input("enter value"))
        newnode = Node(data)
        pos=int(input("enter position"))
        c=self.count()
        if pos>1 and pos<=c:
              temp=self.start
              prev=temp
              i=1
              while i<pos:
                 prev=temp
                 temp=temp.right
                 i=i+1
              prev.right=newnode
              newnode.left=prev
              temp.left=newnode
              newnode.right=temp
           
        else:
              print("check position")       
       
    def count(self):
        nc=0
        temp=self.start
        while temp!=None:
           nc=nc+1
           temp=temp.right
        print("number of nodes till now:%d" %nc)
        return nc

    def deletemid(self):
      count=1
      if self.start==None:
         print("empty")
      else:
         position=int(input("enter position"))
         c=self.count()
         if position>c:
            print("check position")
         if position>1 and position<c:
            temp=prev=self.start
            while count<position:
               prev=temp
               temp=temp.right
               count=count+1
            prev.right=temp.right
            temp1=temp.right
            temp1.left=prev
            del temp
            print("node deleted")
         else:
            print("check position")
     
    def deleteend(self):
        global prev
        if self.start == None:
            print('empty')
        else:
            temp=self.start
            prev=self.start
            while temp.right != None:
                prev=temp
                temp=temp.right
            prev.right=None
            temp.left=None
            del temp
         
     
    def insertbegin(self):
        data=int(input("enter value"))
        newnode = Node(data)
        if self.start == None:
            self.start=newnode
        else:
           temp=self.start
           newnode.right=temp
           temp.left=newnode
           self.start=newnode
     
     
    def deletebegin(self):
        global prev
        if self.start == None:
            print('empty')
        else:
            temp=self.start
            self.start=self.start.right
            self.start.left=None
            del temp
                 
    def display(self):
      print("elements in double linked list are:")
      if self.start == None:
            print("empty")
      else:
         temp=self.start
         while temp!= None:
            print("%d" %(temp.data))
            temp=temp.right
         
    def reversedisplay(self):
       temp=self.start
       print("reverse display")
       if self.start==None:
          priint("empty")
       else:
          while temp.right!=None:
             temp=temp.right
          while temp!=None:
             print("%d" %(temp.data))
             temp=temp.left
     
       
def menu():
    print("1.createlist\n2.insertbegin\n3.insertend\n4.insertmid")
    print("5.deletebegin\n6.deleteend\n7.deletemid\n8.count\n9.display\n10.reversedisplay\n11.exit")
def stop():
    print("you are about to terminate the program")
    exit(0)     
s=Dll()
def default():
    print("check your input")
menu()
while True:
    menu= {
    1: s.createlist,
    2: s.insertbegin,
    3: s.insertend,
    4: s.insertmid,
    5: s.deletebegin,
    6: s.deleteend,
    7: s.deletemid,
    8: s.count,
    9: s.display,
    10: s.reversedisplay,
    11:stop}
    option = int(input("Please enter your choice"))
    menu.get(option,default)()


Output:

Python 3.4.0 (v3.4.0:04f714765c13, Mar 16 2014, 19:24:06) [MSC v.1600 32 bit (Intel)] on win32
Type "copyright", "credits" or "license()" for more information.
>>> ================================ RESTART ================================
>>>
1.createlist
2.insertbegin
3.insertend
4.insertmid
5.deletebegin
6.deleteend
7.deletemid
8.count
9.display
10.reversedisplay
11.exit
Please enter your choice1
enter no of nodes3
enter value2
enter value3
enter value4
Please enter your choice9
elements in double linked list are:
2
3
4
Please enter your choice10
reverse display
4
3
2
Please enter your choice2
enter value1
Please enter your choice9
elements in double linked list are:
1
2
3
4
Please enter your choice3
enter value5
Please enter your choice9
elements in double linked list are:
1
2
3
4
5
Please enter your choice4
enter value0
enter position3
number of nodes till now:5
Please enter your choice9
elements in double linked list are:
1
2
0
3
4
5
Please enter your choice7
enter position3
number of nodes till now:6
node deleted
Please enter your choice9
elements in double linked list are:
1
2
3
4
5
Please enter your choice5
Please enter your choice9
elements in double linked list are:
2
3
4
5
Please enter your choice6
Please enter your choice9
elements in double linked list are:
2
3
4
Please enter your choice8
number of nodes till now:3

Please enter your choice10

Now my new Blog on Fundamentals of Python can be found at https://fundamentalsofpython.blogspot.com/2020/02/list-manipulations.html

Representation of Polynomial using single Linked list

This program is about representation of Polynomial expression using single linked list. Polynomial representation is one of the applications of single linked list.

Source Code:

class Node:

   def __init__(self,coeff,expo):
        self.coeff = coeff
        self.expo = expo
        self.next = None

class Polynomial:

    def __init__(self):
        self.start = None
     
    def createnode(self):
       coeff = int(input("enter coeff"))
       expo=int(input("enter expo"))
       newnode = Node(coeff,expo)
       return newnode
   
    def createpolynomiallist(self):
        while True:
            print("do you want to create polynomial node")
            answer=input()
            if answer == 'n':
                break
            newnode = self.createnode()
            if self.start == None:
               self.start = newnode
            else:
               temp=self.start
               while temp.next != None:
                 temp=temp.next
               temp.next=newnode
       
    def display(self):
         temp=self.start
         while temp!= None:
            print("%dx^%d+" %(temp.coeff,temp.expo),end="")
            temp=temp.next
            #print ("%d" %(temp.data))
   
p=Polynomial()
p.createpolynomiallist()
p.display()

 
Output:

Python 3.4.0 (v3.4.0:04f714765c13, Mar 16 2014, 19:24:06) [MSC v.1600 32 bit (Intel)] on win32
Type "copyright", "credits" or "license()" for more information.
>>> ================================ RESTART ================================
>>>
do you want to create polynomial node
y
enter coeff3
enter expo2
do you want to create polynomial node
y
enter coeff2
enter expo1
do you want to create polynomial node
y
enter coeff1
enter expo0
do you want to create polynomial node
n
3x^2+2x^1+1x^0+
>>>

Now my new Blog on Fundamentals of Python can be found at https://fundamentalsofpython.blogspot.com/2020/02/list-manipulations.html

Circular Single linked list using python

This program is about circular single linked list. In circular single linked list as the last node contains the address of first node there will be no concept of Null. Either for deletion or insertion it is necessary to find the last node in this linked list except for insertion and deletion at intermediate position.

The program covers the following functions:

1.Creation of circular linked list
2.Insertion of node at beginning
3.Insertion of node at the end
4.Insertion of node at intermediate position
5.Deletion of node at beginning
6.Deletion of node at the end
7.Deletion of node at intermediate position
8.Count of nodes
9.Display of nodes
class Node:

   def __init__(self,data):
        self.data = data
        self.next = None

class Csll:

    def __init__(self):
        self.start = None
     
   
    def createlist(self):
         n=int(input("enter no of nodes"))
         for i in range(n):
             data = int(input("enter value"))
             newnode = Node(data)
             if self.start == None:
               self.start = newnode
            else:
               temp=self.start
               while temp.next != None:
                 temp=temp.next
               temp.next=newnode
         newnode.next=self.start
       

    def insertend(self):
        data=int(input("enter value"))
        newnode = Node(data)
        if self.start == None:
               self.start = newnode
        else:
           temp=self.start
           while temp.next != self.start:
                temp=temp.next
           temp.next=newnode
        newnode.next=self.start
     

    def insertmid(self):
        data=int(input("enter value"))
        newnode = Node(data)
        pos=int(input("enter position"))
        c=self.count()
        if pos>1 and pos<=c:
              temp=self.start
              prev=temp
              i=1
              while i<pos:
                 prev=temp
                 temp=temp.next
                 i=i+1
              prev.next=newnode
              newnode.next=temp
           
        else:
              print("check position")       
       
    def count(self):
        nc=1
        temp=self.start
        while temp.next!=self.start:
           nc=nc+1
           temp=temp.next
        print("number of nodes till now:%d" %nc)
        return nc

    def deletemid(self):
      count=1
      if self.start==None:
         print("empty")
      else:
         position=int(input("enter position"))
         c=self.count()
         if position>c:
            print("check position")
         if position>1 and position<c:
            temp=prev=self.start
            while count<position:
               prev=temp
               temp=temp.next
               count=count+1
            prev.next=temp.next
            del temp
            print("node deleted")
         else:
            print("check position")
     
    def deleteend(self):
        global prev
        if self.start == None:
            print('empty')
        else:
            temp=self.start
            prev=self.start
            while temp.next != self.start:
                prev=temp
                temp=temp.next
         
            prev.next=self.start
            del temp
         
     
    def insertbegin(self):
        data=int(input("enter value"))
        newnode = Node(data)
        if self.start == None:
               self.start = newnode
               newnode.next=self.start
        else:
           temp=self.start
           while temp.next!=self.start:
              temp=temp.next
           newnode.next=self.start
           self.start=newnode
        temp.next=self.start
     
     
    def deletebegin(self):
        global prev
        if self.start == None:
            print('empty')
        else:
            temp=last=self.start
            while last.next!=self.start:
               last=last.next
            self.start=self.start.next
            last.next=self.start
            del temp
            #self.start=newstart
                 
    def display(self):
      print("elements in single linked list are:")
      if self.start == None:
            print("empty")
      else:
         temp=self.start
         print ("%d" %(temp.data))
         while temp.next != self.start:
            temp=temp.next
            print ("%d" %(temp.data))
def menu():
    print("1.createlist\n2.insertbegin\n3.insertend\n4.insertmid")
    print("5.deletebegin\n6.deleteend\n7.deletemid\n8.count\n9.display\n10.exit")
def stop():
    print("you are about to terminate the program")
    exit(0)     
s=Csll()
def default():
    print("check your input")
menu()
while True:
    menu= {
    1: s.createlist,
    2: s.insertbegin,
    3: s.insertend,
    4: s.insertmid,
    5: s.deletebegin,
    6: s.deleteend,
    7: s.deletemid,
    8: s.count,
    9: s.display,
    10: stop}
    option = int(input("Please enter your choice"))
    menu.get(option,default)()

Output:
Python 3.4.0 (v3.4.0:04f714765c13, Mar 16 2014, 19:24:06) [MSC v.1600 32 bit (Intel)] on win32
Type "copyright", "credits" or "license()" for more information.
>>> ================================ RESTART ================================
>>>
1.createlist
2.insertbegin
3.insertend
4.insertmid
5.deletebegin
6.deleteend
7.deletemid
8.count
9.display
10.exit
Please enter your choice1
enter no of nodes3
enter value1
enter value2
enter value3
Please enter your choice9
elements in single linked list are:
1
2
3
Please enter your choice2
enter value4
Please enter your choice9
elements in single linked list are:
4
1
2
3
Please enter your choice3
enter value5
Please enter your choice9
elements in single linked list are:
4
1
2
3
5
Please enter your choice4
enter value6
enter position3
number of nodes till now:5
Please enter your choice9
elements in single linked list are:
4
1
6
2
3
5
Please enter your choice8
number of nodes till now:6
Please enter your choice5
Please enter your choice9
elements in single linked list are:
1
6
2
3
5
Please enter your choice6
Please enter your choice9
elements in single linked list are:
1
6
2
3
Please enter your choice7
enter position2
number of nodes till now:4
node deleted
Please enter your choice9
elements in single linked list are:
1
2
3
Please enter your choice8
number of nodes till now:3
Please enter your choice

Now my new Blog on Fundamentals of Python can be found at https://fundamentalsofpython.blogspot.com/2020/02/list-manipulations.html

Single linked list program using python in data structures

This is python program for single linked list concept. This code covers the following functions of single linked list.
1.Insertion at the beginning of the list
2. Insertion at the end of list
3. Insertion at intermediate position in the list
4. Deletion from the beginning of the list
5. Deletion at the end of the list
6.Deletion from intermediate position of the list
7.Count nodes of a list
8.Display the list
9.Creation of the list

source code:

class Node:

   def __init__(self,data):

        self.data = data 

        self.next = None

class Sll:

    def __init__(self):

        self.start = None

        

          

    def createlist(self):

         n=int(input("enter no of nodes"))

         for i in range(n):
             data = int(input("enter value"))

             newnode = Node(data)

            if self.start == None:

               self.start = newnode

            else:

               temp=self.start

               while temp.next != None:

                 temp=temp.next

               temp.next=newnode

         

    def insertend(self):

        data=int(input("enter value"))

        newnode = Node(data)
        if self.start == None:
               self.start = newnode
       else:

        temp=self.start

        while temp.next != None:

                temp=temp.next

        temp.next=newnode

        

    def insertmid(self):

        data=int(input("enter value"))

        newnode = Node(data)

        pos=int(input("enter position"))

        c=self.count()
         if self.start == None:
               self.start = newnode
       else:

          if pos>1 and pos<=c:

              temp=self.start

              prev=temp

              i=1

              while i<pos:

                 prev=temp

                 temp=temp.next

                 i=i+1

          prev.next=newnode

          newnode.next=temp

              

                 

    def count(self):

        nc=0

        temp=self.start

        while temp!=None:

           nc=nc+1

           temp=temp.next

        print("number of nodes :%d" %nc)

        return nc

    def deletemid(self):

      count=1

      if self.start==None:

         print("empty")

      else:

         position=int(input("enter position"))

         c=self.count()

         if position>c:

            print("check position")

         if position>1 and position<c:

            temp=prev=self.start

            while count<position:

               prev=temp

               temp=temp.next

               count=count+1

            prev.next=temp.next

            del temp

            print("node deleted")

         else:

            print("check position")

        

    def deleteend(self):

        global prev

        if self.start == None:

            print('empty')

        else:

            temp=self.start

            prev=self.start

            while temp.next != None:

                prev=temp

                temp=temp.next

            

            prev.next=None

            del temp

            

        

    def insertbegin(self):

        data=int(input("enter value"))

        newnode = Node(data)
        if self.start == None:
               self.start = newnode
       else:

        temp=self.start

        newnode.next=temp

        self.start=newnode

        

        

    def deletebegin(self):

        global prev

        if self.start == None:

            print('empty')

        else:

            temp=self.start

            newstart=self.start.next

            del temp

            self.start=newstart

                   

    def display(self):

      print("elements in single linked list are:")

      if self.start == None:

            print("empty")

      else:

         temp=self.start

         print ("%d" %(temp.data))

         while temp.next != None:

            temp=temp.next

            print ("%d" %(temp.data))

def menu():

    print("1.createlist\n2.insertbegin\n3.insertend\n4.insertmid")

    print("5.deletebegin\n6.deleteend\n7.deletemid\n8.count\n9.display\n10.exit")

def stop():

    print("you are about to terminate the program")

    exit(0)        

s=Sll()

def default():

    print("check your input")

menu()

while True:

    menu= {

    1: s.createlist,

    2: s.insertbegin,

    3: s.insertend,

    4: s.insertmid,

    5: s.deletebegin,

    6: s.deleteend,

    7: s.deletemid,

    8: s.count,

    9: s.display,

    10: stop}

    option = int(input("Please enter your choice"))

    menu.get(option,default)()

Output:

Python 3.4.0 (v3.4.0:04f714765c13, Mar 16 2014, 19:24:06) [MSC v.1600 32 bit (Intel)] on win32

Type "copyright", "credits" or "license()" for more information.

>>> ================================ RESTART ================================

>>> 

1.createlist

2.insertbegin

3.insertend

4.insertmid

5.deletebegin

6.deleteend

7.deletemid

8.count

9.display

10.exit

Please enter your choice1

enter no of nodes3

enter value1

enter value2

enter value3

Please enter your choice9

elements in single linked list are:

1

2

3

Please enter your choice2

enter value4

Please enter your choice9

elements in single linked list are:

4

1

2

3

Please enter your choice3

enter value5

Please enter your choice9

elements in single linked list are:

4

1

2

3

5

Please enter your choice8

number of nodes :5

Please enter your choice5

Please enter your choice9

elements in single linked list are:

1

2

3

5

Please enter your choice6

Please enter your choice9

elements in single linked list are:

1

2

3

Please enter your choice7

enter position2

number of nodes :3

node deleted

Please enter your choice9

elements in single linked list are:

1

3

Please enter your choice10

Now my new Blog on Fundamentals of Python can be found at https://fundamentalsofpython.blogspot.com/2020/02/list-manipulations.html