Linked List Delete Element Problem
Implement a method, remove_first which takes a linked list as a parameter and removes the first element. Make sure to check all possible cases for the possible sizes of the linked list. Use assert statement(s).
def remove_first(s):
''' Removes the first node in the given list
>>> remove_first(link(4,link(3, link(2, link(1, 'empty')))))
[3, [2, [1, 'empty']]]
>>> remove_first(link(1, 'empty'))
'empty'
'''
"*** YOUR CODE HERE ***"
Implement a method, remove_last which takes a linked list as a parameter and removes the last element. Make sure to check all possible cases for the possible sizes of the linked list. Use assert statement(s).
def remove_last(s):
''' Removes the last node in the given list
>>> remove_last(link(4,link(3, link(2, link(1, 'empty')))))
[4, [3, [2, 'empty']]]
>>> remove_last(link(1, 'empty'))
'empty'
'''
"*** YOUR CODE HERE ***"
Implement delete_at which takes a linked-list, and a deletion index and returns the reconstructed list with the element at the given location removed.
def delete_at(s, idx):
'''Delete element in a given list at provided index.
Please fill in the provided assert statements and do not
modify the printed msg.
>>> lst = link(3, link(2, link(1, empty)))
>>> delete_at(lst, 0)
[2, [1, 'empty']]
>>> delete_at(lst, 2)
[3, [2, 'empty']]
'''
"*** YOUR CODE HERE ***"
IMPORTANT Information:
empty = 'empty'
def is_link(s):
"""s is a linked list if it is empty or a (first, rest) pair."""
return s == empty or (len(s) == 2 and is_link(s[1]))
def link(first, rest):
"""Construct a linked list from its first element and the rest."""
assert is_link(rest), "rest must be a linked list."
return [first, rest]
def first(s):
"""Return the first element of a linked list s."""
assert is_link(s), "first only applies to linked lists."
assert s != empty, "empty linked list has no first element."
return s[0]
def rest(s):
"""Return the rest of the elements of a linked list s."""
assert is_link(s), "rest only applies to linked lists."
assert s != empty, "empty linked list has no rest."
return s[1]
# define length
def len_link(s):
"""Return the length of linked list s."""
length = 0
while s != empty:
s, length = rest(s), length + 1
return length
# getitem
def getitem(s, i):
"""Return the element at index i of linked list s."""
while i > 0:
s, i = rest(s), i - 1
return first(s)