1
\$\begingroup\$

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):
        self.head = None

    #method for setting the head of the Linked List
    def setHead(self,head):
        self.head = head

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

            # when found
            if cur.data == data:
                # if head
                if cur == self.head:
                    if cur.next is None:
                        self.head = None
                    else:
                        self.head = cur.next
                else:
                    if cur.next is None:
                        prev.next = None
                    else:
                        prev.next = cur.next
            else:
                return None        
\$\endgroup\$
2
\$\begingroup\$

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

A warning about equality:

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:
    """Node in SinglyLinkedList."""
    def __init__(self, value, next):
        self.value = value
        self.next = next

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

        # 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):
        previous, current = self._head, self._head.next

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

            previous, current = current, current.next

        raise ValueError(f'value not in list')
\$\endgroup\$
1
\$\begingroup\$

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:
                    self.head = None
                else:
                    self.head = cur.next
            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


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

    return cur.data
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.