LinkedList implementation in Python

Question

I am currently reading through an algorithm book and trying to implement everything as I go. I am also learning python at the same time. This is my implementation of a simple linked-list. I am mainly concerned with whether the code looks "looks python like" any tips on how I can refactor would be greatly appreciated.

class Linked(object):
 # init
 def __init__(self):
 self.head = None
 self.tail = None
 def add(self, data):
 temp = Node(data, None, None)
 if (self.head is None):
 self.head = temp
 self.tail = temp
 else:
 self.tail.setAfter(temp)
 temp.setBefore(self.tail)
 self.tail = temp
 def find(self, data):
 if (self.head is None):
 return "Empty List"
 else:
 current = self.head
 while (current is not None):
 if (current.element() is data):
 return current
 current = current.next()
 return "Element not in List"
 def remove(self, data):
 if (self.head is None):
 return "Empty List"
 elif(self.find(data).element() is data):
 temp = self.find(data)
 if (temp is self.head and temp is self.tail):
 self.head = None
 self.tail = None
 elif (temp is self.head):
 self.head = temp.next()
 self.head.setBefore(None)
 return
 elif (temp is self.tail):
 temp.before.setAfter(None)
 return
 else:
 temp.before.setAfter(temp.after)
 temp.after.setBefore(temp.before)
 def iterator(self):
 if (self.head is None):
 return "Empty List"
 else:
 current = self.head
 while (current is not None):
 print(current.element())
 current = current.next()
class Node(object):
 # init
 def __init__(self, data=None, before=None, after=None):
 self.data = data
 self.before = before
 self.after = after
 def element(self):
 return self.data
 def setBefore(self, before):
 self.before = before
 def setAfter(self, after):
 self.after = after
 def next(self):
 return self.after

Answer 1

You could make your life a lot easier if you used the fact that Python allows you to give custom classes built-in behavior. This allows you to define classes for which e.g. a + b is defined or, as in this case for x in obj.

The way Python allows this is via so called dunder (short for double-underscore) or magic methods. These are special method names which get invoked under certain circumstances.

If you ask Python to iterate over an object obj, it calls the method obj.__iter__ (or at least tries to). If you write a + b it first calls a.__add__(b) and if that does not work b.__radd__(a).

A linked list is predestined to have this method:

class Linked(object):
 def __init__(self):
 self.head = None
 self.tail = None
 def add(self, data):
 temp = Node(data, None, None)
 if self.head is None:
 self.head = self.tail = temp
 else:
 self.tail.next = temp
 temp.prev = self.tail
 self.tail = temp
 def __iter__(self):
 current = self.head
 while current is not None:
 yield current.data
 current = current.next
 raise StopIteration

Together with a greatly simplified Node class:

class Node(object):
 def __init__(self, data, prev=None, next=None):
 self.data = data
 self.prev = prev
 self.next = next
 def __repr__(self):
 return repr(self.data)

This already allows simple things like iterating:

l = Linked()
l.add(1)
l.add(3)
print(list(l))
# [1, 3]
for x in l:
 print(x)
# 1
# 3

The other methods can then take advantage of the fact that it is easy to iterate over the object:

class Linked(object):
 def __init__(self, data=None):
 self.head = None
 self.tail = None
 if data is not None:
 for x in data:
 self.append(x)
 def append(self, data):
 if self.head is None:
 self.head = self.tail = Node(data)
 else:
 node = Node(data, self.tail)
 self.tail.next = node
 self.tail = node
 def __iter__(self):
 current = self.head
 while current is not None:
 yield current
 current = current.next
 def find(self, data):
 for x in self:
 if x.data == data:
 return x
 return None
 def __len__(self):
 return sum(1 for _ in self)
 def __repr__(self):
 return repr(list(self))
 def remove(self, data):
 x = self.find(data)
 if x is None:
 return
 if x is self.head:
 if x is self.tail:
 self.head = self.tail = None
 else:
 self.head = x.next
 self.head.prev = None
 elif x is self.tail:
 x.prev.next = None
 else:
 x.prev.next = x.next
 x.next.prev = x.prev

Here I modified the __iter__ method to yield the nodes, not just the data, removed the manual raising of StopIteration (it is not needed and actually deprecated in Python 3), added a __len__ and __repr__ method for convenience (the latter gets called when you call repr(obj) or when you just enter the variable name in an interactive session), renamed add to append (to mirror the normal list interface), added an optional argument to the constructor to ease initializing a linked list from an iterable and used the optional arguments of Node to make the append method slightly easier to read.

Also note that your class is actually a doubly-linked list, since each node has a pointer to the previous and the next node.

• k4iru: Okay, so I did some reading up on dunder methods. Just to clarify, Since I pass object as a parameter when I define my classes they both inherit the methods from object. You then overrode those methods in __iter__, __len__, and __repr__. Is that correct?
• Graipher: @k4iru No, not really. The inheritance from object does not have anything to do with it. This also works with old-style classes in Python 2, which do not inherit from object. It is just a feature of Python that it looks for these method names. Also note that in Python 3 all classes inherit from object (they are new-style classes) so you don't need to actually do it explicitly (but it is ok for backwards compatibility).
• k4iru: I see, so Python just has a list of built in dunder methods. Thank you!

Answer 2

You should avoid the extra parens. Returning strings in cases where the list is empty is pretty odd, too. iterator() doesn't work like I'd expect it to. element() seems like a weird name for a getter, and I think it'd be more idiomatic to not have a getter. I'd try to get find and remove to use the iterator.