m2skills

add one ll python

Jan 28th, 2018
356
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 2.62 KB | None | 0 0
  1. # program to add one to a number represented by Linked List
  2.  
  3. class LinkedList:
  4.     def __init__(self):
  5.         self.head = None
  6.  
  7.     # returns True is LinkedList is Empty
  8.     def isEmpty(self):
  9.         if self.head is None:
  10.             return True
  11.         else:
  12.             return False
  13.  
  14.     # method adds elements to the left of the Linked List
  15.     def addToStart(self, data):
  16.         # create a temporary node
  17.         tempNode = Node(data)
  18.         tempNode.setLink(self.head)
  19.         self.head = tempNode
  20.         del tempNode
  21.  
  22.     # method adds elements to the right of the Linked List
  23.     def addToEnd(self, data):
  24.         start = self.head
  25.         tempNode = Node(data)
  26.         while start.getNextNode():
  27.             start = start.getNextNode()
  28.         start.setLink(tempNode)
  29.         del tempNode
  30.         return True
  31.  
  32.     # method displays Linked List
  33.     def display(self):
  34.         start = self.head
  35.         if start is None:
  36.             print("Empty List!!!")
  37.             return False
  38.  
  39.         while start:
  40.             print(str(start.getData()), end=" ")
  41.             start = start.link
  42.             if start:
  43.                 print("-->", end=" ")
  44.         print()
  45.  
  46.     # method reverses the LinkedList
  47.     def reverse(self):
  48.         start = self.head
  49.         tempNode = None
  50.         previousNode = None
  51.  
  52.         while start:
  53.             tempNode = start.getNextNode()
  54.             start.setLink(previousNode)
  55.             previousNode = start
  56.             start = tempNode
  57.  
  58.         self.head = previousNode
  59.         return True
  60.  
  61.     def addOne(self):
  62.         self.reverse()
  63.         self.addingOneUtil()
  64.         self.reverse()
  65.  
  66.     # adding one to linked list
  67.     def addingOneUtil(self):
  68.         carry = 1
  69.         Sum = 0
  70.  
  71.         start = self.head
  72.         while start is not None and carry != 0:
  73.             Sum = start.getData() + carry
  74.             start.updateData(Sum % 10)
  75.             carry = int(Sum / 10)
  76.             start = start.getNextNode()
  77.  
  78.         if carry != 0:
  79.             self.addToEnd(carry)
  80.  
  81.         return
  82.  
  83.        
  84. # node class
  85. class Node:
  86.     # default value of data and link is none if no data is passed
  87.     def __init__(self, data=None, link=None):
  88.         self.data = data
  89.         self.link = link
  90.  
  91.     # method to update the data feild of Node
  92.     def updateData(self, data):
  93.         self.data = data
  94.  
  95.     # method to set Link feild the Node
  96.     def setLink(self, node):
  97.         self.link = node
  98.  
  99.     # method returns data feild of the Node
  100.     def getData(self):
  101.         return self.data
  102.  
  103.     # method returns address of the next Node
  104.     def getNextNode(self):
  105.         return self.link
  106.  
  107.  
  108. # main method
  109. print("Program to add one to a number represented by Linked List")
  110. # creating LinkedList
  111. myList = LinkedList()
  112. myList.addToStart(9)
  113. myList.addToEnd(9)
  114. myList.addToEnd(9)
  115. myList.addToEnd(9)
  116. myList.addToEnd(9)
  117. myList.addToEnd(9)
  118. myList.addToEnd(9)
  119. myList.addToEnd(9)
  120. myList.addToEnd(9)
  121. print("The number is : ")
  122. myList.display()
  123. print("The number after adding one is : ")
  124. myList.addOne()
  125. myList.display()
Add Comment
Please, Sign In to add comment