CODEWITHSUNDEEP
pythondata-structureslinked-list
laleydecamote
laleydecamote

Reputation: 95

Deleting the first element of a linked list--is my simpler solution correct, or does the deleted node still occupy memory?

Taking a google/udacity course on data structures, but unfortunately there are some pretty big gaps in explanation at times. I am tasked with deleting the first node in a linked list. (Python)

In my solution, the head is simply replaced by the next node in the list if there is one, or else the head is set to None. But what happens to the node that was previously occupying the head? Does it just disappear, or does it still occupy some slice of memory? In my linked list class, my delete_first() method looks like this:

    def delete_first(self):
        if self.head.nextNode:
            self.head = self.head.nextNode
        else: 
            self.head = None

However, in the online class I'm taking, the solution they provided is as follows, but they unfortunately do not explain why it looks like this(especially returning the deleted element):

    def delete_first(self):
        if self.head:
            deleted_element = self.head
            temp = deleted_element.next
            self.head = temp
            return deleted_element
        else:
            return None

or alternatively:

def delete_first(self):
    deleted = self.head
    if self.head:
        self.head = self.head.next
        deleted.next = None
    return deleted

Upvotes: 1

Views: 253

Answers (1)

trincot
trincot

Reputation: 350866

Your code is fine, except that it assumes the list is not empty. You should protect your code against that situation. For the rest it can be simplified to this:

def delete_first(self):
    if self.head:  # Protect against the case where the list is empty
        self.head = self.head.nextNode

The other code examples you have given only look different because they wanted to return the deleted node. This may be useful in some circumstances, but more often not. It really depends on the needs of the algorithm that is using a linked list.

In your code -- where you don't return the removed node -- the garbage collector will take care of releasing the associated memory, on the condition that your code does not somewhere still have a reference to that removed node.

Upvotes: 1

Related Questions