Python Linked List implementation

Question

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) 

Answer 1

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)?

Answer 2

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.