I have implemented the LinkedList class: I need to implement the pop() which takes no parameter. The method removes and returns the item at the end of the linked list. If the list is empty it returns None and does nothing.
class LinkedList:
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)
new_node.set_next(self.head)
self.head = new_node
self.count += 1
def search(self, item):
current = self.head
while current != None:
if current.get_data() == item:
return True
else:
current = current.get_next()
return False
def remove(self, item):
found = False
current = self.head
previous = None
while current != None and not found:
if current.get_data() == item:
found = True
else:
previous = current
current = current.get_next()
if found:
if previous == None:
self.head = current.get_next()
else:
previous.set_next(current.get_next())
self.count -= 1
else:
raise ValueError("remove(" + str(item) + "). " + str(item) + " is not in list")
def clear(self):
self.head = None
self.count = 0
def __str__(self):
temp = self.head
if(temp != None):
output ="Head"
while (temp != None):
output = output+" --> "+str(temp.data)
temp = temp.next
return output
else:
return "Head --> None"
def append(self, item):
new_node = Node(item)
if self.head is None:
self.head = new_node
return
last = self.head
while(last.next):
last = last.next
last.next = new_node
def pop(self): #Problem here
if self.head is None:
return None
else:
popnode = self.head
self.head = self.head.next
popnode.next = None
return popnode.data
Test:
a_list = LinkedList()
a_list.add(1)
a_list.add(2)
a_list.add(3)
print(a_list)
print("Removed item:",a_list.pop())
print("Removed item:",a_list.pop())
print(a_list)
Expected Output:
Head --> 3 --> 2 --> 1
Removed item: 1
Removed item: 2
Head --> 3
Recd Output:
Head --> 3 --> 2 --> 1
Removed item: 3
Removed item: 2
Head --> 1
Test:
a_list = LinkedList()
a_list.append(1)
a_list.append(2)
a_list.append(3)
print(a_list)
print("Removed item:",a_list.pop())
print("Removed item:",a_list.pop())
print(a_list)
Expected output:
Head --> 1 --> 2 --> 3
Removed item: 3
Removed item: 2
Head --> 1
Recd output:
Head --> 1 --> 2 --> 3
Removed item: 1
Removed item: 2
Head --> 3
Here's a simplified pop() method which does what you require -
def pop(self): #Problem here
# Empty LinkedList
if self.head is None:
return None
# There is a single node in the LinkedList = head, read data and delete it
if self.head.next is None:
data = self.head.data
self.head = None
return data
# there are 2 or more nodes in the LinkedList
secondlast = self.head
while (secondlast.next.next):
secondlast = secondlast.next
# found the second last node
# read the data of the last node and then delete it, by setting secondlast.next = None
data = secondlast.next.data
secondlast.next = None
return data
another approach using a temporary dummy node to simplify case when there is a single node in the LinkedList-
def pop(self): #Problem here
# Empty linkedlist
if self.head is None:
return None
# create a dummy secondlast node
secondlast = Node(-1)
secondlast.next = self.head
while (secondlast.next.next):
secondlast = secondlast.next
data = secondlast.next.data
secondlast.next = None
return data
In your LinkedList, both append() and pop() methods are O(n), since you need to traverse through whole LinkedList to do those operations. Consider adding a new property self.tail(or self.secondlast) to the LinkedList which keeps track of the last node in the LinkedList. It would help in simplifying the code and making both append() and pop() operations O(1)