# Chapter 5: The Linked List¶

## Example 1, page no. 95¶

In [3]:
import sys

class node:
self.data = data

start = None

def create_list(data):
global start
tmp = node(data)
q = node()
if(start==None):
start = tmp
else:
q = start

global start
tmp = node(data)
if(start == None):
start = tmp
else:
start = tmp

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

def Del(data):
global start
if (start.data == data):
tmp = start
return
q = start
return
return

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,

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

def Rev():
global start
return
p1 = start
while(p3 != None):
p1=p2
p2=p3
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
pos+=1
if (ptr == None):

while(1):
print "\n1.Create List"
print "4.Delete"
print "5.Display"
print "6.Count"
print "7.Reverse"
print "8.Search"
print "9.Quit"
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())
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())
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
4.Delete
5.Display
6.Count
7.Reverse
8.Search
9.Quit

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

1.Create List
4.Delete
5.Display
6.Count
7.Reverse
8.Search
9.Quit

List is :
10 15 20
1.Create List
4.Delete
5.Display
6.Count
7.Reverse
8.Search
9.Quit
Number of elements are 3

1.Create List
4.Delete
5.Display
6.Count
7.Reverse
8.Search
9.Quit

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:
self.data = data

start = None

def create_list(self,data):
global start
tmp = node(data)
q = node()
if(start==None):
start = tmp
else:
q = start

global start
tmp = node(data)
if(start == None):
start = tmp
else:
start = tmp

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

def Del(self,data):
global start
if (start.data == data):
tmp = start
return
q = start
return
return

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,

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

def Rev(self):
global start
return
p1 = start
while(p3 != None):
p1=p2
p2=p3
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
pos+=1
if (ptr == None):

while(1):
print "\n1.Create List"
print "4.Delete"
print "5.Display"
print "6.Count"
print "7.Reverse"
print "8.Search"
print "9.Quit"
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())
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())
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
4.Delete
5.Display
6.Count
7.Reverse
8.Search
9.Quit

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

1.Create List
4.Delete
5.Display
6.Count
7.Reverse
8.Search
9.Quit

List is :
5 10 15
1.Create List
4.Delete
5.Display
6.Count
7.Reverse
8.Search
9.Quit
Number of elements are 3

1.Create List
4.Delete
5.Display
6.Count
7.Reverse
8.Search
9.Quit

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:
self.data = None

start = None

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

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

def display(top):
if(top == None):
print "Stack is empty..."
else:
print "Stack elements: "
print top.data,

Top = node()
while(1):
print "\n1.PUSH"
print "2.POP"
print "3.DISPLAY"
print "4.EXIT"
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 element to be pushed: 5

1.PUSH
2.POP
3.DISPLAY
4.EXIT
Enter element to be pushed: 10

1.PUSH
2.POP
3.DISPLAY
4.EXIT
Stack elements:
10 5
1.PUSH
2.POP
3.DISPLAY
4.EXIT

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:
self.data = None

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

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

def display(self, top):
if(top == None):
print "Stack is empty..."
else:
print "Stack elements: "
print top.data,

Top = node()
while(1):
print "\n1.PUSH"
print "2.POP"
print "3.DISPLAY"
print "4.EXIT"
choice = int(raw_input())
if choice == 1:
elif choice == 2:
elif choice == 3:
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 element to be pushed: 5

1.PUSH
2.POP
3.DISPLAY
4.EXIT
Enter element to be pushed: 10

1.PUSH
2.POP
3.DISPLAY
4.EXIT
Stack elements:
10 5 None
1.PUSH
2.POP
3.DISPLAY
4.EXIT

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:
self.data = None

def push(rear):
new_node = node()
print "Enter the no. to be pushed: ",
new_node.data = int(raw_input())
if (rear != None):
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:
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,
print fr.data,

rear = None
front = None
while(1):
print "\n1.PUSH"
print "2.POP"
print "3.TRAVERSE"
print "4.EXIT"
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 the no. to be pushed: 5

1.PUSH
2.POP
3.TRAVERSE
4.EXIT
Enter the no. to be pushed: 10

1.PUSH
2.POP
3.TRAVERSE
4.EXIT
The element(s) is/are:
5 10
1.PUSH
2.POP
3.TRAVERSE
4.EXIT

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:
self.data = None

def push(self, rear):
new_node = node()
print "Enter the no. to be pushed: ",
new_node.data = int(raw_input())
if (rear != None):
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:
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,
print fr.data,

rear = None
front = None
while(1):
print "\n1.PUSH"
print "2.POP"
print "3.TRAVERSE"
print "4.EXIT"
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 the no. to be pushed: 5

1.PUSH
2.POP
3.TRAVERSE
4.EXIT
Enter the no. to be pushed: 10

1.PUSH
2.POP
3.TRAVERSE
4.EXIT
The element(s) is/are:
5 10
1.PUSH
2.POP
3.TRAVERSE
4.EXIT
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

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

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:
if(p1.expo > p2.expo):
tmp.coef=p1.coef
tmp.expo=p1.expo
else:
if(p2.expo > p1.expo):
tmp.coef = p2.coef
tmp.expo = p2.expo
else:
if(p1.expo == p2.expo):
tmp.coef=p1.coef + p2.coef
tmp.expo=p1.expo
while(p1!=None):
tmp.coef = p1.coef
tmp.expo = p1.expo
if (p3_start==None):
p3_start=tmp
p3=p3_start
else:
while(p2!=None):
tmp.coef = p2.coef
tmp.expo = p2.expo
if (p3_start==None):
p3_start = tmp
p3 = p3_start
else:
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)
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)
print "\nPolynomial 1 is: "
display(p1_start)
print "Polynomial 2 is: "
display(p2_start)
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) +


(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

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

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

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 "4.Delete"
print "5.Display"
print "6.Count"
print "7.Reverse"
print "8.exit"
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())
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())
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
4.Delete
5.Display
6.Count
7.Reverse
8.exit

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

1.Create List
4.Delete
5.Display
6.Count
7.Reverse
8.exit

List is :

15
1.Create List
4.Delete
5.Display
6.Count
7.Reverse
8.exit

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:
self.info = info

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

global last
tmp = node()
tmp.info = num

global last
q = node()
tmp = node()
for i in range(0, pos-1):
print "There are less than ", pos, " elements"
return
tmp.info = num
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
if(q.info == num):
tmp = q
return
print num, " deleted"
last = q
return

def display(self):
global last
q = node()
if(last == None):
print "List is empty"
return
print "List is:"
while(q != last):
print q.info,
print last.info

while(1):
print "\n1.Create List"
print "4.Delete"
print "5.Display"
print "6.Quit"
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())
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())
elif choice == 4:
co.my_del()
elif choice == 5:
co.display()
elif choice == 6:
sys.exit()
else:
print "Wrong choice"


1.Create List
4.Delete
5.Display
6.Quit
1
How many nodes you want:3

Enter the element:5

Enter the element:10

Enter the element:15

1.Create List
4.Delete
5.Display
6.Quit
5
List is:
5 10 15

1.Create List
4.Delete
5.Display
6.Quit
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:
self.priority = priority
self.info = info

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

def my_del(front):
tmp = node()
if(front == None):
print "Queue Underflow"
else:
tmp = front;
print "Deleted item is ", tmp.info
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)

front = None
while(1):
print "\n1.Insert"
print "2.Delete"
print "3.Display"
print "4.Quit"
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

An exception has occurred, use %tb to see the full traceback.

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