1. Extend the LList class by implementing some of the other methods that the bui
ID: 3756423 • Letter: 1
Question
1. Extend the LList class by implementing some of the other methods that the built-in Python list supports: __min__, __max__, index, count, and remove.
# ListNode.py
class ListNode:
def __init__(self, item = None, link = None):
'''creates a ListNode with the specified data value and link
post: creates a ListNode with the specified data value and link'''
self.item = item
self.link = link
# LList.py
from ListNode import ListNode
class LList:
#------------------------------------------------------------
def __init__(self, seq=()):
"""create an LList
post: creates a list containing items in seq"""
if seq == ():
# No items to put in, create an empty list
self.head = None
else:
# Create a node for the first item
self.head = ListNode(seq[0], None)
# Add remaining items keeping track of last node added
last = self.head
for item in seq[1:]:
last.link = ListNode(item, None)
last = last.link
self.size = len(seq)
#------------------------------------------------------------
def __len__(self):
'''post: returns number of items in the list'''
return self.size
#------------------------------------------------------------
def _find(self, position):
'''private method that returns node that is at location position
in the list (0 is first item, size-1 is last item)
pre: 0 <= position < self.size
post: returns the ListNode at the specified position in the
list'''
assert 0 <= position < self.size
node = self.head
# move forward until we reach the specified node
for i in range(position):
node = node.link
return node
#------------------------------------------------------------
def append(self, x):
'''appends x onto end of the list
post: x is appended onto the end of the list'''
# create a new node containing x
newNode = ListNode(x)
# link it into the end of the list
if self.head is not None:
# non-empty list
node = self._find(self.size - 1)
node.link = newNode
else:
# empty list
# set self.head to new node
self.head = newNode
self.size += 1
#------------------------------------------------------------
def __getitem__(self, position):
'''return data item at location position
pre: 0 <= position < size
post: returns data item at the specified position'''
node = self._find(position)
return node.item
#------------------------------------------------------------
def __setitem__(self, position, value):
'''set data item at location position to value
pre: 0 <= position < self.size
post: sets the data item at the specified position to value'''
node = self._find(position)
node.item = value
#------------------------------------------------------------
def __delitem__(self, position):
'''delete item at location position from the list
pre: 0 <= position < self.size
post: the item at the specified position is removed from
the list'''
assert 0 <= position < self.size
self._delete(position)
#------------------------------------------------------------
def _delete(self, position):
#private method to delete item at location position from the list
# pre: 0 <= position < self.size
# post: the item at the specified position is removed from the list
# and the item is returned (for use with pop)
if position == 0:
# save item from the initial node
item = self.head.item
# change self.head to point "over" the deleted node
self.head = self.head.link
else:
# find the node immediately before the one to delete
prev_node = self._find(position - 1)
# save the item from node to delete
item = prev_node.link.item
# change predecessor to point "over" the deleted node
prev_node.link = prev_node.link.link
self.size -= 1
return item
#------------------------------------------------------------
def pop(self, i=None):
'''returns and removes at position i from list; the default is to
return and remove the last item
pre: self.size > 0 and ((i is None or (0 <= i < self.size))
post: if i is None, the last item in the list is removed
and returned; otherwise the item at position i is removed
and returned'''
assert self.size > 0 and (i is None or (0 <= i < self.size))
# default is to delete last item
# i could be zero so need to compare to None
if i is None:
i = self.size - 1
return self._delete(i)
#------------------------------------------------------------
def insert(self, i, x):
'''inserts x at position i in the list
pre: 0 <= i <= self.size
post: x is inserted into the list at position i and
old elements from position i..oldsize-1 are at positions
i+1..newsize-1'''
assert 0 <= i <= self.size
if i == 0:
# insert before position 0 requires updating self.head
self.head = ListNode(x, self.head)
else:
# find item that node is to be insert after
node = self._find(i - 1)
node.link = ListNode(x, node.link)
self.size += 1
#------------------------------------------------------------
def __copy__(self):
'''post: returns a new LList object that is a shallow copy of self'''
a = LList()
node = self.head
while node is not None:
a.append(node.item)
node = node.link
return a
#------------------------------------------------------------
## def __iter__(self):
## # generator version works in both Python2 and Python3
## node = self.head
## while node is not None:
## yield node.item
## node = node.link
#------------------------------------------------------------
def __iter__(self):
return LListIterator(self.head)
#------------------------------------------------------------
class LListIterator:
#------------------------------------------------------------
def __init__(self, head):
self.currnode = head
#------------------------------------------------------------
# Python2 version
def next(self):
if self.currnode is None:
raise StopIteration
else:
item = self.currnode.item
self.currnode = self.currnode.link
return item
#------------------------------------------------------------
# Python3 version
def __next__(self):
if self.currnode is None:
raise StopIteration
else:
item = self.currnode.item
self.currnode = self.currnode.link
return item
Explanation / Answer
def __min__(self): node = self.head result = None # move forward until we reach the specified node while node: if not result or result > node.item: result = node.item node = node.link return result def __max__(self): node = self.head result = None # move forward until we reach the specified node while node: if not result or resultRelated Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.