# Find and delete an item from a singly linked list in Python

Given a Singly Linked-List, implement a method to delete the node that contains the same data as the input data.

Example: delete(1->2->3->4,3) ==> 1->2->4

class SinglyLinkedList:
#constructor
def __init__(self):

#method for deleting a node having a certain data
#method for deleting a node having a certain data
def delete(self,data):
return None
else:
prev = None
while cur.data != data and cur.next is not None:
prev = cur
cur = cur.next

# when found
if cur.data == data:
if cur.next is None:
else:
else:
if cur.next is None:
prev.next = None
else:
prev.next = cur.next
else:
return None


A few general things:

• Use """Doc strings.""" for documentation not # comments
• Put a space after each comma
• Prefer less indentation. For example, if you have an if blah: return None, then you don't need an else after it, because if the function didn't return then blah must've been false
• PEP8 prefers snake_case for methods and variables. setHead should be set_head, although I'm a bit dubious that you should be exposing this to the user. The head should be a private implementation detail. You should expose methods to allow the user to modify the list instead.
• Additionally, for parity with builtin collection types, I'd take an optional iterable as the first argument to your constructor. If provided, you populate your collection with the values from it.
• I prefer value to data again for parity with python builtins

You use cur == self.head. Depending on how equality is implemented for your nodes this may or may not work. In this situation, I think you are lucky to avoid this edge case due to delete removing the first thing, but in general this is dangerous. To test if two things are the exact same object use is. Use == for equality. (1, 2) == (1, 2) but (1, 2) is not (1, 2).

Specifically relating to delete:

• I'd rename it to remove for parity with the method on the builtin list
• I'd have it raise a ValueError when the value isn't in the list (again for parity with the method on the builtin list)
• Despite what @vnp suggests, I wouldn't return the value deleted again for parity with remove on the builtin list. It doesn't really make much sense to return the value since you know it already (you passed it into the method). This is what list.remove does.
• Since many operations on the linked list require finding a node with a given value and the previous node (ex. in, find, insert_before), I'd extract find value or raise ValueError into a helper. This will cut down on the complexity of your delete operation (you now just have to stitch the hole in the list)
• You have some duplicated logic for setting self.head/prev.next. No matter whether cur.next is None or not you set self.head/prev.next to cur.next. But, I'd solve this another way:
• One trick commonly employed to make the linked lists a bit less unwieldy is always having an empty node at the head (with no data). This means that you never have to special case patching the head pointer.

Combining this all:

class Node:
def __init__(self, value, next):
self.value = value
self.next = next

def __init__(self, iterable=None):
"""New list initialized from optional iterable's items."""

# Not implemented here, but like list.append,
# should take ...args and append each. In this
# way you can do O(n) appends instead of O(n^2)
self.append(iterable)

def remove(self, value):
"""Removes value from the list or raises ValueError."""
previous_node, matched_node = self._find_value(value)
previous_node.next = matched_node.next

def _find_value(self, value):

while current is not None:
if current.value == value:
return previous, current

previous, current = current, current.next

raise ValueError(f'value not in list')


If an item is not found, the method returns None. I don't see what it returns on a successful deletion. Usually it is convenient to return the deleted item's data.

Handling of actual deletion

            if cur == self.head:
if cur.next is None:
else:
else:
if cur.next is None:
prev.next = None
else:
prev.next = cur.next


seems convoluted. self.head becomes cur.next regardless of whether cur.next is None or not. Similarly, prev.next becomes cur.next no matter what.

Testing for self.head is None is not a preferred pythonic way. Consider

    cur = self.head
prev = None
try:
while cur.data != data:
prev = cur
cur = cur.next
except:
return None


Notice that at this point you know for sure that cur.data == data, and the if cur.data == data test is redundant.

Putting it all together,

    cur = self.head
prev = None
try:
while cur.data != data:
prev = cur
cur = cur.next
except:
return None