# Python Linked List implementation

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
"""

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)

def size(self):
"""
Returns the current size of the list. O(n), linear time
"""
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.
"""
found = False
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.
"""
previous = None
found = False
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:
# 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
"""
toPrint = []
while current != None:
toPrint.append(current.value)
current = current.next
return str(toPrint)

• What do you mean by "more reliable"? – jonrsharpe Mar 4 '17 at 14:33
• Fewer possible bugs. – MadPhysicist Mar 4 '17 at 16:41
• 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. – Graipher Mar 5 '17 at 12:33
• Sure. No problem. – MadPhysicist Mar 5 '17 at 12:37

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

• 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. – MadPhysicist Mar 4 '17 at 22:50
• Is this a valid example? shutupandship.com/2012/01/… – MadPhysicist Mar 4 '17 at 22:51

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.
"""
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.

• 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? – MadPhysicist Mar 5 '17 at 11:57
• Also, could you take a look at my implementation of iter() and next() that I added as an edit to the original post? – MadPhysicist Mar 5 '17 at 12:02
• @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. – Graipher Mar 5 '17 at 12:39
• @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). – Graipher Mar 5 '17 at 12:41
• @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 – Graipher Mar 6 '17 at 8:14