In this exercise you will need to alter the implementations of the add(), remove

Question

In this exercise you will need to alter the implementations of the add(), remove() and search() functions so that they run recursively. I have begun the process for you as follows:

Note that the assumptions we made for our implementation of the ordered list in lectures still hold true for the recursive implementation here. When you add an item you can assume that it is not already present in the list. When you remove an item you can assume that the item is present in the list.

Resources:

-------------------------

Classes:

Code to be completed:

Test Code:

def add (self,item) new nodeNode (item) currseli. h pre None self.add recursive (new node, curr,prev) head def search (self,item): curr-self. head return self.search recursive (item, curr) def remove (self,item): curr-self. head preNone self.remove recursive (item, curr,prev) You will need to implement the add_recursive (), search_recursive(), and remove_recursive) functions, which as their names suggest, must be recursive functions. No marks will be given for non-recursive implementations I have provided a file for you to use to test your ordered linked list implementation - A2Q1.py. You should get the same output regardless of whether you use the ordered linked list implementation discussed in class or the recursive implementation you complete for this assignment. An example of it running is shown below A2Q1py-CAUsers dazh001)Google Teaching CS1052017 Python 3.5.1 Shell File Edit Shell Debug Options Window Python 3.5.1 (v3.5.1:37a07 D64)1 on win32 Type "copyright", "credits Drive Work Window File Edit Format Run from OrderedList import OrderedList import random o list = orderedst() for i in range (10) RESTART: C: Usersdazh001 rand-num = random. randrange (0,10) while o list.search (rand num): nments A2 A2Q1.py After insertion: 0 1 2 3 4 5 6 7 8 9 After deletion: rand num = random.randrange (0,10) o list.add (rand num) print("After insertion:" for item in o list print) for i in range (10) print (item,end-" ") rand-num = randon.randrange (0,10) while not (o 1ist.search (rand num)): rand-num randon.randrange (0,10) o list.remove (rand num) print("After deletion:") for item in o list: print (item,end-"") print)

Explanation / Answer

from Node import Node
from LinkedListIterator import LinkedListIterator

class OrderedList:
def __init__(self):
self.__head = None
self.__count = 0

def is_empty(self):
return self.__count == 0
  
def size(self):
return self.__count

def add(self, item):
new_node = Node(item)
curr = self.__head
prev = None
self.add_recursive(new_node, curr, prev)

def add_recursive(self, new_node, curr, prev):
if self.is_empty():
self.__head = new_node
self.__count += 1
return
if curr != None and curr.get_data() < new_node.get_data():
prev = curr
curr = curr.get_next()
self.add_recursive(new_node, curr, prev)
elif prev == None:
self.__head = new_node
self.__count += 1
self.__head.set_next(curr)
else:
self.__count += 1
prev.set_next(new_node)
new_node.set_next(cur)
def search(self, item):
curr = self.__head
return self.search_recursive(item, curr)

def search_recursive(self, item, curr):
if curr == None:
return False
if curr.get_data() == item:
return True
self.search_recursive(item, curr.geet_next())

def remove(self, item):
curr = self.__head
prev = None
self.remove_recursive(item, curr, prev)

def remove_recursive(self, item, curr, prev):
if curr == None:
return
if curr.get_data() == item:
if prev == None:
self.__head == None
self.__count = 0
else:
prev.set_next(curr.get_next())
self.__count -= 1
else:
self.remove_recursive(item, curr.get_next(), cur)

def __itr__(self):
return LinkedListIterator(self.__head)

# copy pastable code link: https://paste.ee/p/QjcI8

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.