CODEWITHSUNDEEP
pythonlistlinked-list
user2933041
user2933041

Reputation: 31

Using recursion to remove a value from a linked list

my task is to remove the first occurring value from a linked list. The value is inputted by the user. Then, I also have to return a boolean value indicating whether the item was removed (True) or if the value is not in the linked list, return False. This is what I have so far.

def remove(lst, value):
    lst.head = removeRec(lst.head, value)

def removeRec(node, value):
    if isinstance(node, EmptyNode):
        print("Cannot remove value from an empty list")
    elif node.data == value:
        return node.next
    elif:
        node.next = removeRec(node.next, value)
        return node
    else:
        return False

The problem with this is that it doesn't return True if the item was removed. How would I implement that? Also, how would I implement a similar function iteratively. Thanks guys.

Upvotes: 0

Views: 3192

Answers (4)

Jennifer Zhao
Jennifer Zhao

Reputation: 1

in case there is duplicate in the linkedlist

def removeLinkedList(node, value):
    if not node:
        return node
    elif node.val == value:
        return removeLinkedList(node.next,value)
    else:
        node.next = removeLinkedList(node.next, value)
        return node

Upvotes: 0

user2859193
user2859193

Reputation: 434

I would do it like:

def remove(lst, value):
    remove.ret = False

    def removeRec(node, value):
        if isinstance(node, EmptyNode):
            print("Cannot remove value from an empty list")
        elif node.data == value:
            remove.ret = True
            return node.next
        else:
            node.next = removeRec(node.next, value)
            return node

    lst.head = removeRec(lst.head, value)
    return remove.ret

Upvotes: 0

Blckknght
Blckknght

Reputation: 104762

The "Pythonic" way to report that you've failed to achieve what you were asked to do is to raise an exception. This makes your code fairly simple:

def removeRec(node, value):
    if isinstance(node, EmptyNode):
        raise ValueError("Cannot remove value from an empty list")
    elif node.data == value:
        return node.next
    else:
        node.next = removeRec(node.next, value)
        return node

This would work with your existing remove function, leaving it to the caller to handle the exception in the calling code. However, if you wanted the remove function to return a Boolean value indicating success or failure, you could catch the exception there:

def remove(lst, value):
    try:
        lst.head = removeRec(lst.head, value)
        return True # only reached if no exception was raised by the recursion
    except ValueError:
        return False

If you're dead set against using exceptions for some reason (such as being in a class where they've not been taught yet), you could encode the failure of the removal in the return value from the recursive calls, but then you need to do extra checking for it, to avoid damaging your list:

def removeRec(node, value):
    if isinstance(node, EmptyNode):
        print("Cannot remove value from an empty list")
        return None    # your code did this implicitly, I'm being explicit
    elif node.data == value:
        return node.next
    else:
        rec_result = removeRec(node.next, value)
        if rec_result is None:
            return rec_result
        else:
            node.next = rec_result
            return node

You then can do the same check from the recursive case in the non-recursive function, and turn the result value into a boolean:

def remove(lst, value):
    rec_result = removeRec(lst.head, value)
    if rec_result is None:
        return False
    else:
        lst.head = rec_result
        return True

Upvotes: 2

Joran Beasley
Joran Beasley

Reputation: 114038

you need to start with your base cases

  1. the value is at the head of the list
  2. the value is at the end of the list
  3. the value is in the middle of the list
  4. the value is not in the list

now because of the nature of most lists you can treat the end value the same as if it was in the middle of the list

so really we have

  1. the value is at the head of the list
  2. the value is not in the list
  3. all other cases

as our base cases, now that you understand your base cases you can write your function

def removeRec(node,value):
   if node.value == value: #only time this will happen is if the node is at the head
      node.value = node.next.value
      node.next = node.next.next
      #you cannot simply say node= node.next since then it will not propagate to the actual list
      return True # found and removed value
   if node.next == None: #case where value is not in the list
      return False #unable to remove
   if node.next.value == value:
       node.next = node.next.next 
       return True #successfully removed
   return removeRec(node.next,value)#recursively continue searching

since nodes are mutable objects the list will just be updated ... it does not return a new list

Upvotes: 1

Related Questions