Using recursion to remove a value from a linked list

Question

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.

Blckknght · Accepted Answer · 2013-11-09 22:06:40Z

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

Joran Beasley · Accepted Answer · 2013-11-09 22:03:35Z

1

you need to start with your base cases

the value is at the head of the list
the value is at the end of the list
the value is in the middle of the list
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

the value is at the head of the list
the value is not in the list
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

edited Nov 9, 2013 at 22:03

answered Nov 9, 2013 at 21:58

Joran Beasley

114k13 gold badges168 silver badges187 bronze badges

2 Comments

Blckknght Over a year ago

Using a global head node is probably not a useful thing to do, surely.

Joran Beasley Over a year ago

there now it doesnt ... and node.next is the one that actually is deleted, however for all intensive purposes it is node

user2859193 · Accepted Answer · 2013-11-09 22:17:32Z

0

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

edited Nov 9, 2013 at 22:17

answered Nov 9, 2013 at 22:12

user2859193

4343 silver badges11 bronze badges

Comments

Jennifer Zhao · Accepted Answer · 2018-01-08 05:19:02Z

0

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

answered Jan 8, 2018 at 5:19

Jennifer Zhao

1

Collectives™ on Stack Overflow

Using recursion to remove a value from a linked list

4 Answers 4

Comments

2 Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

Comments

2 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related