Chapter 5: The Linked List

Example 1, page no. 95

In [3]:
import sys

class node:
    def __init__(self, data=0, link=None):
        self.data = data
        self.link = link

start = None

def create_list(data):
    global start
    tmp = node(data)
    q = node()
    if(start==None):
        start = tmp
    else:
        q = start
    while(q.link != None):
        q = q.link
    q.link = tmp
    
def AddAtBeg(data):
    global start
    tmp = node(data)
    if(start == None):
        start = tmp
    else:
        tmp.link = start
        start = tmp
        
def AddAfter(data, pos):
    global start
    q = start
    for i in range(pos-1):
        q = q.link
        if(q == None):
            print "\n\n There are less than %d elements" %pos
            return
    tmp = node(data)
    tmp.link = q.link
    q.link = tmp
    
def Del(data):
    global start
    if (start.data == data):
        tmp = start
        start = start.link
        return
    q = start
    while(q.link.link != None):
        if(q.link.data == data):
            tmp = q.link
            q.link = tmp.link
            return
        q = q.link
    if(q.link.data == data):
        tmp = q.link;
        q.link = None
        return
    print "\n\nElement %d not found" %data

def Display():
    global start
    if(start == None):
        print "\n\nList is empty"
        return
    q=start
    print "\n\nList is : "
    while(q != None):
        print q.data,
        q = q.link

def Count():
    global start
    q = start
    cnt = 0
    while(q != None):
        q = q.link
        cnt+=1
    print "Number of elements are %d\n" %cnt

def Rev():
    global start
    if(start.link==None):
        return
    p1 = start
    p2 = p1.link
    p3 = p2.link
    p1.link = None
    p2.link = p1
    while(p3 != None):
        p1=p2
        p2=p3
        p3=p3.link
        p2.link=p1
    start=p2

def Search(data):
    global start
    ptr = start
    pos = 1
    while(ptr!=None):
        if (ptr.data == data):
            print "\n\nItem %d found at position %d" %(data, pos)
            return
        ptr = ptr.link
        pos+=1
    if (ptr == None):
        print "\n\nItem %d not found in list" %data

while(1):
    print "\n1.Create List"
    print "2.Add at beginning"
    print "3.Add after"
    print "4.Delete"
    print "5.Display"
    print "6.Count"
    print "7.Reverse"
    print "8.Search"
    print "9.Quit"
    print "Enter your choice: ",
    choice =int(raw_input())
    if choice == 1:
        print "\n\nHow many nodes you want:"
        n = int(raw_input())
        for i in range(n):
            print "Enter the element: "
            data = int(raw_input())
            create_list(data)
    elif choice == 2:
        print "\n\nEnter the element : "
        data = int(raw_input())
        AddAtBeg(data)
    elif choice == 3:
        print "\n\nEnter the element : "
        data = int(raw_input())
        print "\nEnter the position after which this element is inserted:"
        pos = int(raw_input())
        AddAfter(data,pos)
    elif choice == 4:
        if (start == None):
            print "\n\nList is empty"
            continue
        print "\n\nEnter the element for deletion:"
        data = int(raw_input())
        Del(data)
    elif choice == 5:
        Display()
    elif choice == 6:
        Count()
    elif choice == 7:
        Rev()
    elif choice == 8:
        print "\n\nEnter the element to be searched:"
        data = int(raw_input())
        Search(data)
    elif choice == 9:
        sys.exit()
    else:
        print "\n\nWrong choice"
 
1.Create List
2.Add at beginning
3.Add after
4.Delete
5.Display
6.Count
7.Reverse
8.Search
9.Quit
Enter your choice: 1
 

How many nodes you want:
3
Enter the element: 
10
Enter the element: 
15
Enter the element: 
20

1.Create List
2.Add at beginning
3.Add after
4.Delete
5.Display
6.Count
7.Reverse
8.Search
9.Quit
Enter your choice: 5
 

List is : 
10 15 20 
1.Create List
2.Add at beginning
3.Add after
4.Delete
5.Display
6.Count
7.Reverse
8.Search
9.Quit
Enter your choice: 6
 Number of elements are 3


1.Create List
2.Add at beginning
3.Add after
4.Delete
5.Display
6.Count
7.Reverse
8.Search
9.Quit
Enter your choice: 9
An exception has occurred, use %tb to see the full traceback.

SystemExit
To exit: use 'exit', 'quit', or Ctrl-D.

Example 2. page no. 101

In [4]:
import sys

class node:
    def __init__(self, data=0, link=None):
        self.data = data
        self.link = link

start = None

class LinkedList():

    def create_list(self,data):
        global start
        tmp = node(data)
        q = node()
        if(start==None):
            start = tmp
        else:
            q = start
        while(q.link != None):
            q = q.link
        q.link = tmp
    
    
    def AddAtBeg(self,data):
        global start
        tmp = node(data)
        if(start == None):
            start = tmp
        else:
            tmp.link = start
            start = tmp
        

    def AddAfter(self,data, pos):
        global start
        q = start
        for i in range(pos-1):
            q = q.link
            if(q == None):
                print "\n\n There are less than %d elements" %pos
                return
        tmp = node(data)
        tmp.link = q.link
        q.link = tmp
    

    def Del(self,data):
        global start
        if (start.data == data):
            tmp = start
            start = start.link
            return
        q = start
        while(q.link.link != None):
            if(q.link.data == data):
                tmp = q.link
                q.link = tmp.link
                return
            q = q.link
        if(q.link.data == data):
            tmp = q.link;
            q.link = None
            return
        print "\n\nElement %d not found" %data    


    def Display(self):
        global start
        if(start == None):
            print "\n\nList is empty"
            return
        q=start
        print "\n\nList is : "
        while(q != None):
            print q.data,
            q = q.link
    
    def Count(self):
        global start
        q = start
        cnt = 0
        while(q != None):
            q = q.link
            cnt+=1
        print "Number of elements are %d\n" %cnt
    
    
    def Rev(self):
        global start
        if(start.link==None):
            return
        p1 = start
        p2 = p1.link
        p3 = p2.link
        p1.link = None
        p2.link = p1
        while(p3 != None):
            p1=p2
            p2=p3
            p3=p3.link
            p2.link=p1
        start=p2
    

    def Search(self,data):
        global start
        ptr = start
        pos = 1
        while(ptr!=None):
            if (ptr.data == data):
                print "\n\nItem %d found at position %d" %(data, pos)
                return
            ptr = ptr.link
            pos+=1
        if (ptr == None):
            print "\n\nItem %d not found in list" %data
    

l_list = LinkedList()

while(1):
    print "\n1.Create List"
    print "2.Add at beginning"
    print "3.Add after"
    print "4.Delete"
    print "5.Display"
    print "6.Count"
    print "7.Reverse"
    print "8.Search"
    print "9.Quit"
    print "Enter your choice: ",
    choice =int(raw_input())
    if choice == 1:
        print "\n\nHow many nodes you want:"
        n = int(raw_input())
        for i in range(n):
            print "Enter the element: "
            data = int(raw_input())
            l_list.create_list(data)
    elif choice == 2:
        print "\n\nEnter the element : "
        data = int(raw_input())
        l_list.AddAtBeg(data)
    elif choice == 3:
        print "\n\nEnter the element : "
        data = int(raw_input())
        print "\nEnter the position after which this element is inserted:"
        pos = int(raw_input())
        l_list.AddAfter(data,pos)
    elif choice == 4:
        if (start == None):
            print "\n\nList is empty"
            continue
        print "\n\nEnter the element for deletion:"
        data = int(raw_input())
        l_list.Del(data)
    elif choice == 5:
        l_list.Display()
    elif choice == 6:
        l_list.Count()
    elif choice == 7:
        l_list.Rev()
    elif choice == 8:
        print "\n\nEnter the element to be searched:"
        data = int(raw_input())
        l_list.Search(data)
    elif choice == 9:
        sys.exit()
    else:
        print "\n\nWrong choice"
 
1.Create List
2.Add at beginning
3.Add after
4.Delete
5.Display
6.Count
7.Reverse
8.Search
9.Quit
Enter your choice: 1
 

How many nodes you want:
3
Enter the element: 
5
Enter the element: 
10
Enter the element: 
15

1.Create List
2.Add at beginning
3.Add after
4.Delete
5.Display
6.Count
7.Reverse
8.Search
9.Quit
Enter your choice: 5
 

List is : 
5 10 15 
1.Create List
2.Add at beginning
3.Add after
4.Delete
5.Display
6.Count
7.Reverse
8.Search
9.Quit
Enter your choice: 6
 Number of elements are 3


1.Create List
2.Add at beginning
3.Add after
4.Delete
5.Display
6.Count
7.Reverse
8.Search
9.Quit
Enter your choice: 9
An exception has occurred, use %tb to see the full traceback.

SystemExit
To exit: use 'exit', 'quit', or Ctrl-D.

Example 3, page no. 109

In [1]:
import sys

class node:
    def __init__(self, link=None):
        self.data = None
        self.link = link
        
start = None


def push(top):
    new = node()
    print "Enter element to be pushed: ",
    pushed_item = int(raw_input())
    new.data = pushed_item
    new.link = top
    top = new
    return top

def pop(top):
    tmp = node()
    if(top == None):
        print "Stack is empty..."  
    else:
        tmp = top
        print "Popped item is: ", tmp.data
        top = top.link
        tmp.link = None
    return top

def display(top):
    if(top == None):
        print "Stack is empty..."
    else:
        print "Stack elements: "
        while(top.link != None):
            print top.data,
            top = top.link
            
Top = node()
while(1):
    print "\n1.PUSH"
    print "2.POP"
    print "3.DISPLAY"
    print "4.EXIT"
    print "Enter your choice: ",
    choice = int(raw_input())
    if choice == 1:
        Top = push(Top)
    elif choice == 2:
        Top=pop(Top)
    elif choice == 3:
        display(Top)
    elif choice == 4:
        sys.exit()    
    else:
        print "Wrong choice"
        print "\nDo you want to continue (Y/y) = "
        ch = raw_input()
        if ch == 'Y' or ch == 'y':
            continue
        else:
            sys.exit()
1.PUSH
2.POP
3.DISPLAY
4.EXIT
Enter your choice: 1
 Enter element to be pushed: 5
 
1.PUSH
2.POP
3.DISPLAY
4.EXIT
Enter your choice: 1
 Enter element to be pushed: 10
 
1.PUSH
2.POP
3.DISPLAY
4.EXIT
Enter your choice: 3
 Stack elements: 
10 5 
1.PUSH
2.POP
3.DISPLAY
4.EXIT
Enter your choice: 4
An exception has occurred, use %tb to see the full traceback.

SystemExit
To exit: use 'exit', 'quit', or Ctrl-D.

Example 4, page no. 111

In [6]:
import sys

class node:
    def __init__(self, link=None):
        self.data = None
        self.link = link


class linkList:
    def push(self, top):
        new = node()
        print "Enter element to be pushed: ",
        pushed_item = int(raw_input())
        new.data = pushed_item
        new.link = top
        top = new
        return top

    def pop(self, top):
        tmp = node()
        if(top == None):
            print "Stack is empty..."  
        else:
            tmp = top
            print "Popped item is: ", tmp.data
            top = top.link
            tmp.link = None
        return top

    def display(self, top):
        if(top == None):
            print "Stack is empty..."
        else:
            print "Stack elements: "
            while(top.link != None):
                print top.data,
                top = top.link
            
Top = node()
link_list = linkList()
while(1):
    print "\n1.PUSH"
    print "2.POP"
    print "3.DISPLAY"
    print "4.EXIT"
    print "Enter your choice: ",
    choice = int(raw_input())
    if choice == 1:
        Top = link_list.push(Top)
    elif choice == 2:
        Top = link_list.pop(Top)
    elif choice == 3:
        link_list.display(Top)
    elif choice == 4:
        sys.exit()    
    else:
        print "Wrong choice"
        print "\nDo you want to continue (Y/y) = "
        ch = raw_input()
        if ch == 'Y' or ch == 'y':
            continue
        else:
            sys.exit()
 
1.PUSH
2.POP
3.DISPLAY
4.EXIT
Enter your choice: 1
 Enter element to be pushed: 5
 
1.PUSH
2.POP
3.DISPLAY
4.EXIT
Enter your choice: 1
 Enter element to be pushed: 10
 
1.PUSH
2.POP
3.DISPLAY
4.EXIT
Enter your choice: 3
 Stack elements: 
10 5 None 
1.PUSH
2.POP
3.DISPLAY
4.EXIT
Enter your choice: 4
An exception has occurred, use %tb to see the full traceback.

SystemExit
To exit: use 'exit', 'quit', or Ctrl-D.

Example 5, page no. 116

In [7]:
import sys

class node:
    def __init__(self, link=None):
        self.data = None
        self.link = link

def push(rear):
    new_node = node()
    print "Enter the no. to be pushed: ",
    new_node.data = int(raw_input())
    new_node.link = None
    if (rear != None):
        rear.link = new_node
    rear = new_node
    return rear

def pop(f, r):
    if f == None:
        print "The Queue is empty"
    else:
        print "The poped element is: ", f.data
        if f != r:
            f = f.link
        else:
            f = None
    return f

def traverse(fr, re):
    if fr == None:
        print "The Queue is empty"
    else:
        print "The element(s) is/are: "
        while fr != re:
            print fr.data,
            fr = fr.link
        print fr.data,

rear = None
front = None
while(1):
    print "\n1.PUSH"
    print "2.POP"
    print "3.TRAVERSE"
    print "4.EXIT"
    print "Enter your choice: ",
    choice = int(raw_input())
    if choice == 1:
        rear = push(rear)
        if front == None:
            front = rear
    elif choice == 2:
        front = pop(front, rear)
        if front == None:
            rear = None
    elif choice == 3:
        traverse(front, rear)
    elif choice == 4:
        sys.exit()    
    else:
        print "Wrong choice"
        print "\nDo you want to continue (Y/y) = "
        ch = raw_input()
        if ch == 'Y' or ch == 'y':
            continue
        else:
            sys.exit()
 
1.PUSH
2.POP
3.TRAVERSE
4.EXIT
Enter your choice: 1
 Enter the no. to be pushed: 5
 
1.PUSH
2.POP
3.TRAVERSE
4.EXIT
Enter your choice: 1
 Enter the no. to be pushed: 10
 
1.PUSH
2.POP
3.TRAVERSE
4.EXIT
Enter your choice: 3
 The element(s) is/are: 
5 10 
1.PUSH
2.POP
3.TRAVERSE
4.EXIT
Enter your choice: 4
An exception has occurred, use %tb to see the full traceback.

SystemExit
To exit: use 'exit', 'quit', or Ctrl-D.

Example 6, page no. 119

In [8]:
import sys

class node:
    def __init__(self, link=None):
        self.data = None
        self.link = link

class linkList:
    def push(self, rear):
        new_node = node()
        print "Enter the no. to be pushed: ",
        new_node.data = int(raw_input())
        new_node.link = None
        if (rear != None):
            rear.link = new_node
        rear = new_node
        return rear

    def pop(self, f, r):
        if f == None:
            print "The Queue is empty"
        else:
            print "The poped element is: ", f.data
            if f != r:
                f = f.link
            else:
                f = None
        return f

    def traverse(self, fr, re):
        if fr == None:
            print "The Queue is empty"
        else:
            print "The element(s) is/are: "
            while fr != re:
                print fr.data,
                fr = fr.link
            print fr.data,
    
rear = None
front = None
l = linkList()
while(1):
    print "\n1.PUSH"
    print "2.POP"
    print "3.TRAVERSE"
    print "4.EXIT"
    print "Enter your choice: ",
    choice = int(raw_input())
    if choice == 1:
        rear = l.push(rear)
        if front == None:
            front = rear
    elif choice == 2:
        front = l.pop(front, rear)
        if front == None:
            rear = None
    elif choice == 3:
        l.traverse(front, rear)
    elif choice == 4:
        sys.exit()    
    else:
        print "Wrong choice"
        print "\nDo you want to continue (Y/y) = "
        ch = raw_input()
        if ch == 'Y' or ch == 'y':
            continue
        else:
            sys.exit()
 
1.PUSH
2.POP
3.TRAVERSE
4.EXIT
Enter your choice: 1
 Enter the no. to be pushed: 5
 
1.PUSH
2.POP
3.TRAVERSE
4.EXIT
Enter your choice: 1
 Enter the no. to be pushed: 10
 
1.PUSH
2.POP
3.TRAVERSE
4.EXIT
Enter your choice: 3
 The element(s) is/are: 
5 10 
1.PUSH
2.POP
3.TRAVERSE
4.EXIT
Enter your choice: 5
 Wrong choice

Do you want to continue (Y/y) = 
n
An exception has occurred, use %tb to see the full traceback.

SystemExit
To exit: use 'exit', 'quit', or Ctrl-D.

Example 8, page no. 127

In [9]:
class node:
    
    def __init__(self):
        self.coef = 0.0
        self.expo = 0
        self.link = None

def insert(start, co, ex):
    ptr = node()
    tmp = node()
    tmp.coef = co
    tmp.expo = ex
    if(start==None or ex>start.expo):
        tmp.link=start
        start = tmp
    else:
        ptr=start
        while(ptr.link != None and ptr.link.expo > ex):
            ptr = ptr.link
            tmp.link = ptr.link
            ptr.link = tmp
            if(ptr.link==None):
                tmp.link = None
    return start

def poly_add(p1, p2):
    p3 = node()
    tmp = node()
    p3_start = None
    if(p1 == None and p2 == None):
        return p3_start
    while(p1 != None and p2 != None):
        if(p3_start == None):
            p3_start = tmp
            p3 = p3_start
        else:
            p3.link = tmp
            p3 = p3.link
        if(p1.expo > p2.expo):
            tmp.coef=p1.coef
            tmp.expo=p1.expo
            p1 = p1.link
        else:
            if(p2.expo > p1.expo):
                tmp.coef = p2.coef
                tmp.expo = p2.expo
                p2 = p2.link
            else:
                if(p1.expo == p2.expo):
                    tmp.coef=p1.coef + p2.coef
                    tmp.expo=p1.expo
                    p1=p1.link
                    p2=p2.link
    while(p1!=None):
        tmp.coef = p1.coef
        tmp.expo = p1.expo
        if (p3_start==None):
            p3_start=tmp
            p3=p3_start
        else:
            p3.link=tmp
            p3=p3.link
        p1=p1.link
    while(p2!=None):
        tmp.coef = p2.coef
        tmp.expo = p2.expo
        if (p3_start==None):
            p3_start = tmp
            p3 = p3_start
        else:
            p3.link = tmp
            p3 = p3.link
        p2 = p2.link
    p3.link = None
    return p3_start

def enter(start):
    print "How many terms u want to enter: "
    n = int(raw_input())
    for i in range(n):
        print "Enter coeficient for term %d:" %i
        co = float(raw_input())
        print "Enter exponent for term %d:" %i
        ex = int(raw_input())
        start = insert(start,co,ex);
    return start

def display(ptr):
    if (ptr==None):
        print "Empty..."
        return
    while(ptr!=None):
        print "(%.1fx^%d) + " %(ptr.coef, ptr.expo)
        ptr = ptr.link
    print "\b\b \n"

p1_start=None
p2_start=None
p3_start=None
print "\nPolynomial 1 : "
p1_start = enter(p1_start)
print "\nPolynomial 2 :"
p2_start = enter(p2_start)
p3_start = poly_add(p1_start, p2_start)
print "\nPolynomial 1 is: "
display(p1_start)
print "Polynomial 2 is: "
display(p2_start)
print "\nAdded polynomial is: "
display (p3_start)
Polynomial 1 : 
How many terms u want to enter: 
2
Enter coeficient for term 0:
2
Enter exponent for term 0:
3
Enter coeficient for term 1:
4
Enter exponent for term 1:
5

Polynomial 2 :
How many terms u want to enter: 
2
Enter coeficient for term 0:
1
Enter exponent for term 0:
2
Enter coeficient for term 1:
3
Enter exponent for term 1:
4

Polynomial 1 is: 
(4.0x^5) + 
(2.0x^3) + 
 

Polynomial 2 is: 
(3.0x^4) + 
(1.0x^2) + 
 


Added polynomial is: 
(1.0x^2) + 
 

Example 9, page no. 134

In [12]:
import sys

class node:
    def __init__(self, info=0, next=None, prev=None):
        self.info = info
        self.next = next
        self.prev = prev

start = node()

def create_list(num):
    global start
    tmp = node()
    tmp.info = num
    q = node()
    if(start.next == None):
        tmp.prev = None
        start.prev = tmp
        start = tmp
    else:
        q = start
    while(q.next != None):
        q = q.next
        q.next = tmp
        tmp.prev = q

def addatbeg(num):
    global start
    tmp = node()
    tmp.info = num
    tmp.next = start
    start.prev = tmp
    start = tmp

def addafter(num, pos):
    global start
    q=start
    for i in range(0,pos-1):
        q=q.next
        if(q==None):
            print "\nThere are less than %d elements\n" %pos
            return
    tmp = node()
    tmp.info = num
    q.next.prev = tmp
    tmp.next = q.next
    tmp.prev = q
    q.next = tmp

def my_del(num):
    global start
    if(start.info==num):
        tmp = start
        start = start.next
        start.prev = None
        return
    q = start;
    while(q.next.next != None):
        if(q.next.info==num):
            tmp=q.next
            q.next=tmp.next
            tmp.next.prev = q
            return
    q = q.next
    if (q.next.info==num):
        tmp = q.next
        q.next = None
        return
    print "\nElement %d not found\n" %num

def display():
    global start
    if(start==None):
        print "\nList is empty\n"
        return
    q = start
    print "\nList is :\n"
    while(q!=None):
        print q.info,
        q = q.next

def count():
    global start
    q=start
    cnt=0
    while(q!=None):
        q=q.next
        cnt+=1
    print "\nNumber of elements are \n", cnt

def rev():
    global start
    p1=start
    p2=p1.next
    p1.next=None
    p1.prev=p2
    while(p2!=None):
        p2.prev=p2.next
        p2.next=p1
        p1=p2
        p2=p2.prev
    start=p1

while(1):
    print "\n1.Create List"
    print "2.Add at begining"
    print "3.Add after"
    print "4.Delete"
    print "5.Display"
    print "6.Count"
    print "7.Reverse"
    print "8.exit"
    print "Enter your choice: ",
    choice = int(raw_input())
    if choice == 1:
        print "\nHow many nodes you want: ",
        n = int(raw_input())
        for i in range(n):
            print "Enter the element: ",
            m = int(raw_input())
            create_list(m)
    elif choice == 2:
        print "\nEnter the element: ",
        m = int(raw_input())
        addatbeg(m)
    elif choice == 3:
        print "\nEnter the element: ",
        m = int(raw_input())
        print "Enter the position after which this element is inserted: ",
        po = int(raw_input())
        addafter(m,po)
    elif choice == 4:
        print "\nEnter the element for deletion: ",
        m = int(raw_input())
        my_del(m);
    elif choice == 5:
        display()
    elif choice == 6:
        count()
    elif choice == 7:
        rev()
    elif choice == 8:
        sys.exit()
    else:
        print "\nWrong choice\n"
 
1.Create List
2.Add at begining
3.Add after
4.Delete
5.Display
6.Count
7.Reverse
8.exit
Enter your choice: 1
 
How many nodes you want: 3
 Enter the element: 5
 Enter the element: 10
 Enter the element: 15
 
1.Create List
2.Add at begining
3.Add after
4.Delete
5.Display
6.Count
7.Reverse
8.exit
Enter your choice: 5
 
List is :

15 
1.Create List
2.Add at begining
3.Add after
4.Delete
5.Display
6.Count
7.Reverse
8.exit
Enter your choice: 8
An exception has occurred, use %tb to see the full traceback.

SystemExit
To exit: use 'exit', 'quit', or Ctrl-D.

Example 10, page no. 141

In [13]:
import sys

class node:
    def __init__(self, info=None, link=None):
        self.info = info
        self.link = link

last = None
class Circular_Linked:
    def create_list(self, num):
        global last
        q = node()
        tmp = node()
        tmp.info = num
        if (last == None):
            last = tmp
            tmp.link = last
        else:
            tmp.link = last.link
            last.link = tmp
            last = tmp

    def addatbeg(self, num):
        global last
        tmp = node()
        tmp.info = num
        tmp.link = last.link
        last.link = tmp

    def addafter(self, num, pos):
        global last
        q = node()
        tmp = node()
        q = last.link
        for i in range(0, pos-1):
            q = q.link
            if (q == last.link):
                print "There are less than ", pos, " elements"
                return
        tmp.link = q.link
        tmp.info = num
        q.link = tmp
        if(q==last):
            last=tmp

    def my_del(self):
        global last
        if(last == None):
            print "List underflow"
            return
        print "Enter the number for deletion:"
        num = int(raw_input())
        q = node()
        tmp = node()
        if( last.link == last and last.info == num):
            tmp = last
            last = None
            return
        q = last.link
        if(q.info == num):
            tmp = q
            last.link = q.link
            return
        while(q.link != last):
            if(q.link.info == num):
                tmp = q.link
                q.link = tmp.link
                print num, " deleted"
            q = q.link
        if(q.link.info == num):
            tmp = q.link
            q.link = last.link
            last = q
            return
        print "Element ",num," not found"

    def display(self):
        global last
        q = node()
        if(last == None):
            print "List is empty"
            return
        q = last.link
        print "List is:"
        while(q != last):
            print q.info,
            q = q.link
        print last.info
        
co = Circular_Linked()
while(1):
    print "\n1.Create List"
    print "2.Add at begining"
    print "3.Add after"
    print "4.Delete"
    print "5.Display"
    print "6.Quit"
    print "Enter your choice:"
    choice = int(raw_input())
    if choice == 1:
        print "How many nodes you want:",
        n = int(raw_input())
        for i in range(n):
            print "\nEnter the element:",
            m = int(raw_input())
            co.create_list(m)
    elif choice == 2:
        print "\nEnter the element:",
        m = int(raw_input())
        co.addatbeg(m)
    elif choice == 3:
        print "\nEnter the element:",
        m = int(raw_input())
        print "\nEnter the position after which this element is inserted:",
        po = int(raw_input())
        co.addafter(m,po)
    elif choice == 4:
        co.my_del()
    elif choice == 5:
        co.display()
    elif choice == 6:
        sys.exit()
    else:
        print "Wrong choice"
 
1.Create List
2.Add at begining
3.Add after
4.Delete
5.Display
6.Quit
Enter your choice:
1
How many nodes you want:3
 
Enter the element:5
 
Enter the element:10
 
Enter the element:15
 
1.Create List
2.Add at begining
3.Add after
4.Delete
5.Display
6.Quit
Enter your choice:
5
List is:
5 10 15

1.Create List
2.Add at begining
3.Add after
4.Delete
5.Display
6.Quit
Enter your choice:
6
An exception has occurred, use %tb to see the full traceback.

SystemExit
To exit: use 'exit', 'quit', or Ctrl-D.

Example 11, page no. 148

In [1]:
import sys

class node:
    def __init__(self, priority=None, info=None, link=None):
        self.priority = priority
        self.info = info
        self.link = link

def insert(front):
    tmp = node()
    q = node()
    print "Input the item value to be added in the queue:"
    added_item = int(raw_input())
    print "Enter its priority:"
    item_priority = int(raw_input())
    tmp.info = added_item
    tmp.priority = item_priority
    if(front == None or item_priority < front.priority):
        tmp.link = front
        front = tmp
    else:
        q = front
        while(q.link != None and q.link.priority <= item_priority):
            q = q.link
            tmp.link = q.link
            q.link = tmp
    return front

def my_del(front):
    tmp = node()
    if(front == None):
        print "Queue Underflow"
    else:
        tmp = front;
        print "Deleted item is ", tmp.info
        front = front.link
    return front

def display(front):
    ptr = node()
    ptr = front;
    if(front == None):
        print "Queue is empty"
    else:
        print "Queue is: "
        print "Priority Item "
        while(ptr != None):
            print "%5d %5d " %(ptr.priority,ptr.info)
            ptr = ptr.link

front = None
while(1):
    print "\n1.Insert"
    print "2.Delete"
    print "3.Display"
    print "4.Quit"
    print "Enter your choice",
    choice = int(raw_input())
    if choice == 1:
        front = insert(front);
    elif choice == 2:
        front = my_del(front);
    elif choice == 3:
        display(front)
    elif choice == 4:
        sys.exit()
    else:
        print "Wrong choice"
1.Insert
2.Delete
3.Display
4.Quit
Enter your choice4
An exception has occurred, use %tb to see the full traceback.

SystemExit
To exit: use 'exit', 'quit', or Ctrl-D.