My home work needs me to pop the last item from the linked list and for some reason, some test cases works but some did not and I don't know why.
class Node:
def __init__(self, init_data):
self.data = init_data
self.next = None
def get_data(self):
return self.data
def get_next(self):
return self.next
def set_data(self, new_data):
self.data = new_data
def set_next(self, new_next):
self.next = new_next
def __str__(self):
return str(self.data)
class LinkedList:
def __init__(self):
self.head = None
def add(self, item):
new_node = Node(item)
new_node.set_next(self.head)
self.head = new_node
def __str__(self):
result = "("
node = self.head
if node != None:
result += str(node.data)
node = node.next
while node:
result += ", " + str(node.data)
node = node.next
result += ")"
return result
def remove_from_tail(self):
if self.head is None:
return None
prev = None
cur = self.head
while cur.next is not None:
prev = cur
cur = cur.next
if prev:
prev.next = None
return cur
#test case one is incorrect
my_list = LinkedList()
my_list.add(400)
print(my_list.remove_from_tail())
my_list.add(300)
print(my_list.remove_from_tail())
my_list.add(200)
print(my_list.remove_from_tail())
my_list.add(100)
print(my_list.remove_from_tail())
#should be 400 300 200 100 but instead I got 400 400 300 200
#test case two works fine
fruit = LinkedList()
fruit.add('cherry')
fruit.add('banana')
fruit.add('apple')
last_one = fruit.remove_from_tail()
print('Removed:', last_one)#got"Removed: cherry"
print(fruit)#(apple, banana)
I don't know what is the reason for test case one to fail when cur = self.head
and self.head
should point to 300 after 400 is removed. So when I return cur it shouldn't print out two 400. Any help would be appreciated.
Your code is fine, the problem is that you are calling remove_from_tail
after every add, but what you want to do is call add
till you add all elements, and then call remove_from_tail
one by one, which works fine
my_list = LinkedList()
my_list.add(400)
my_list.add(300)
my_list.add(200)
my_list.add(100)
print(my_list.remove_from_tail())
print(my_list.remove_from_tail())
print(my_list.remove_from_tail())
print(my_list.remove_from_tail())
This outputs
400
300
200
100
Also your add
function is a little odd, generally we fix the head and for every new element, traverse to the end of the list and append it, but in your add
you are updating every element on head
and updating head.
Whereas your remove_from_tail
assumes that the head is fixed and we are traversing till the end and then updating, which actually happens
So after you run add 4 times, the list is
head
100 -> 200 -> 300 -> 400
And as you expect, the tail is removed accordingly,from 400
to 100
Also in your remove_from_tail
function, you need to take care of the case where only one element remains in the list, and you want to remove it, once you add that your original test case works too
def remove_from_tail(self):
#If linked list is empty return None
if self.head is None:
return None
#If only one element in list, return that element and set head to None
elif self.head.next is None:
cur = self.head
self.head = None
return cur
#Otherwise iterate through the list
prev = None
cur = self.head
while cur.next is not None:
prev = cur
cur = cur.next
if prev:
prev.next = None
return cur
The original test case then prints
400
300
200
100
as well