2
\$\begingroup\$

I am looking for some comments on an implementation of a singly-linked list in Python. What could I do to make it more reliable and readable?

class LinkedList(object):
    class Node(object):
        """
        Inner class of LinkedList. Contains a blueprint for a node of the LinkedList
        """
        def __init__(self, v, n=None):
            """
            Initializes a List node with payload v and link n
            """
            self.value=v
            self.next=n

    def __init__(self):
        """
        Initializes a LinkedList and sets list head to None
        """
        self.head=None

    def insert(self, v):
        """
        Adds an item with payload v to beginning of the list
        in O(1) time 
        """
        Node = self.Node(v, self.head)
        self.head = Node

    def size(self):
        """
        Returns the current size of the list. O(n), linear time
        """
        current = self.head
        count = 0
        while current:
            count += 1
            current = current.next
        return count

    def search(self, v):
        """
        Searches the list for a node with payload v. Returns the node object or None if not found. Time complexity is O(n) in worst case.
        """
        current = self.head
        found = False
        while current and not found:
            if current.value == v:
                found = True
            else:
                current = current.next
        if not current:
            return None
        return current

    def delete(self, v):
        """
        Searches the list for a node with payload v. Returns the node object or None if not found. Time complexity is O(n) in worst case.
        """
        current = self.head
        previous = None
        found = False
        while current and not found:
            if current.value == v:
                found = True
            else:
                previous = current
                current = current.next
        # nothing found, return None
        if not current:
            return None
        # the case where first item is being deleted
        if not previous:
            self.head = current.next
        # item from inside of the list is being deleted    
        else:
            previous.next = current.next

        return current

    def __str__(self):
        """
        Prints the current list in the form of a Python list            
        """
        current = self.head
        toPrint = []
        while current != None:
            toPrint.append(current.value)
            current = current.next
        return str(toPrint) 
\$\endgroup\$
  • \$\begingroup\$ What do you mean by "more reliable"? \$\endgroup\$ – jonrsharpe Mar 4 '17 at 14:33
  • \$\begingroup\$ Fewer possible bugs. \$\endgroup\$ – MadPhysicist Mar 4 '17 at 16:41
  • \$\begingroup\$ I rolled back your edits, because once you have answers changing the question code is not possible, in order to avoid invalidating existing answers. Have a look at What you may and may not do after receiving answers. You can always ask a follow-up question with the updated code. \$\endgroup\$ – Graipher Mar 5 '17 at 12:33
  • \$\begingroup\$ Sure. No problem. \$\endgroup\$ – MadPhysicist Mar 5 '17 at 12:37
6
\$\begingroup\$

If readability is a concern, why use single-character variable names? Replace them with something a bit more meaningful: v -> value, n -> next_, etc.


If you followed Python's data model your class could be used more easily and conventionally. For example, implementing size as a method seems a bit odd - if you called it __len__, then it would behave correctly with len and in a boolean context. Looking at the documentation for other, similar data structures can help with picking sensible names (I would expect an insert to take an index, for example, like the other sequences); in your case, maybe start with the deque's interface.

If you follow the conventional implementation, any of the following should work in a predictable way:

  • if thing in linked_list:
  • for thing in linked_list:
  • list(linked_list) (which would really simplify your __str__ implementation)
  • if linked_list:

You could also leverage Python's abstract base classes; if you inherit from Sequence and implement the required methods, for example, you get some additional behaviour for free.


In general you're following the style guide, but Node as a temporary variable name sticks out. It shadows the class you just instantiated and naming a variable in CamelCase is not the convention, it should be snake_case. In fact, it's entirely pointless; why not just self.node = Node(v, self.head)?

\$\endgroup\$
  • \$\begingroup\$ Do you know if I need to create a separate class to implement an iterator? That is, I am trying to implement for thing in linked_list: functionality. \$\endgroup\$ – MadPhysicist Mar 4 '17 at 22:50
  • \$\begingroup\$ Is this a valid example? shutupandship.com/2012/01/… \$\endgroup\$ – MadPhysicist Mar 4 '17 at 22:51
3
\$\begingroup\$

To make @jonrsharpe's suggestion more specific, this is one way to implement __iter__, without having to add another iterator class. It also gives you the __str__ method for free.

def __iter__(self):
    """
    Iterate over the linked list.
    """
    current = self.head
    while current is not None:
        yield current.value
        current = current.next

def __str__(self):
    """
    Prints the current list in the form of a Python list
    """
    return str(list(self))

Here is an example of its usage:

>>> l = LinkedList()
>>> l.insert(1)
>>> l.insert(2)
>>> for x in l:
...     print x
... 
2
1
>>> list(l)
[2, 1]
>>> print(l)
[2, 1]

Note that I used is not None instead of != None, read the answers here, if you want to know why.

\$\endgroup\$
  • \$\begingroup\$ Would such __str__ method print a string version of memory addresses to the Nodes? If so, how is this useful to someone using such method? \$\endgroup\$ – MadPhysicist Mar 5 '17 at 11:57
  • \$\begingroup\$ Also, could you take a look at my implementation of iter() and next() that I added as an edit to the original post? \$\endgroup\$ – MadPhysicist Mar 5 '17 at 12:02
  • \$\begingroup\$ @MadPhysicist Regarding question 1, I don't understand your question. For l = LinkedList; l.insert(1); l.insert(2) list(l) == [2, 1] and print(l) will just print [2, 1]. This works because the __iter__ method is yielding the values, not the Node objects. \$\endgroup\$ – Graipher Mar 5 '17 at 12:39
  • \$\begingroup\$ @MadPhysicist Regarding question 2, have a look at the comment on the question. Once you receive answers you must not change your code in your question anymore. You can, however, ask a new question with the updated code (and link to the new one here and to this question in the new question). \$\endgroup\$ – Graipher Mar 5 '17 at 12:41
  • 1
    \$\begingroup\$ @MadPhysicist Just put it somewhere in the question body, like, this is a continued discussion from link, since I incorporated some advice gotten there. Or something similar \$\endgroup\$ – Graipher Mar 6 '17 at 8:14

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.