CODEWITHSUNDEEP
pythonlinked-listnodes
yowhatsup123
yowhatsup123

Reputation: 287

pop method LinkedList Class

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

Upvotes: 0

Views: 613

Answers (2)

S4eed3sm
S4eed3sm

Reputation: 1478

Just track popnode.next when become None and at the same time store previous item, when popnode.next become None, Just put next of prev None, and return data of popnode.next:

def pop(self):  # Problem here
    if self.head is None:
        return None
    elif self.head.next == None:
        d = self.head.data
        self.head = None
        return d
    else:
        popnode = self.head
        prev = popnode
        while popnode.next:
            prev = popnode
            popnode = popnode.next
        prev.next = None
        return popnode.data

The output of:

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("Removed item:", a_list.pop())
print(a_list)

Will be:

Head --> 3--> 2--> 1
Removed item: 1
Removed item: 2
Removed item: 3
Head  None

Upvotes: 1

Max
Max

Reputation: 678

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)

Upvotes: 2

Related Questions