Python The assignment is to write functions for maintaining an ordered linked li
ID: 3574454 • Letter: P
Question
Python
The assignment is to write functions for maintaining an ordered linked list. For an example of using links, see my file bintree.py. In this assignment, we’ll have a Node class that has two fields, “data” and “next”. We’ll have a variable “root” that points to the first node in the list.
Write code for the following tasks.
(1) Write a function to add a node at the beginning of the list.
(2) Write a function to print the data field of each node from beginning to end. (Now you should be able to see what’s happening.)
(3) Suppose we want to keep the list in alphabetical order by the data fields. Write a function to add a name to the list in it’s correct position to preserve the order. This requires a little thought. Draw pictures before trying to write code.
(4) Write a function to remove an item from the list, preserving the order.
Explanation / Answer
class Node(object):
def __init__(self, data=None, next_node=None):
self.data = data
self.next_node = next_node
def get_data(self):
return self.data
def get_next(self):
return self.next_node
def set_next(self, new_next):
self.next_node = new_next
class LinkedList(object):
def __init__(self, head=None):
self.head = head
def insert(self, data):
new_node = Node(data)
new_node.set_next(self.head)
self.head = new_node
def size(self):
current = self.head
count = 0
while current:
count += 1
current = current.get_next()
return count
def print(self):
current = self.head
while current:
print self.data ,
current = current.get_next()
def search(self, data):
current = self.head
found = False
while current and found is False:
if current.get_data() == data:
found = True
else:
current = current.get_next()
if current is None:
raise ValueError("Data not in list")
return current
def sort(self):
return sorted(self.head, key=lambda node: node.data)
def delete(self, data):
current = self.head
previous = None
found = False
while current and found is False:
if current.get_data() == data:
found = True
else:
previous = current
current = current.get_next()
if current is None:
raise ValueError("Data not in list")
if previous is None:
self.head = current.get_next()
else:
previous.set_next(current.get_next())
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.