Python linked list

Question

This is my first attempt at making a singly linked-list class. Would this sort of implementation be sufficient for interviewing quality?

class Node(object):
 def __init__(self, data, next_node = None):
 self.data = data
 self.next = next_node
 def __repr__(self):
 return str(self.data)
class LinkedList(object):
 def __init__(self):
 self.head = None
 def prepend(self, data):
 new_head = Node(data)
 new_head.next = self.head
 self.head = new_head
 def append(self, data):
 new_node = Node(data)
 if self.head == None:
 self.head = new_node
 else:
 iter_node = self.head
 while iter_node.next:
 iter_node = iter_node.next
 iter_node.next = new_node
 def insert(self, position, data):
 if position == 0 or not self.head:
 self.prepend(data)
 else:
 node_to_insert = Node(data)
 iter_node = self.head
 pos = position
 while pos>1 and iter_node.next:
 iter_node = iter_node.next
 pos-=1
 node_to_insert.next = iter_node.next
 iter_node.next = node_to_insert
 def delete(self, position):
 if not self.head:
 pass
 elif position == 0:
 self.head = self.head.next
 else:
 iter_node = self.head
 pos = position
 while pos>1 and iter_node.next:
 iter_node = iter_node.next
 pos-=1
 if iter_node.next:
 iter_node.next = iter_node.next.next
 def reverse(self):
 if self.head:
 prev = None
 current = self.head
 while current:
 future = current.next
 current.next = prev
 prev = current
 current = future
 self.head = prev
 def __repr__(self):
 output_string = ""
 iter_node = self.head
 while iter_node:
 output_string += str(iter_node) + ", "
 iter_node = iter_node.next
 return "[" + output_string[:-2] + "]"
 def __getitem__(self, position):
 if not self.head:
 return None
 else:
 iter_node = self.head
 pos = position
 while pos>0 and iter_node.next:
 iter_node = iter_node.next
 pos-=1
 return iter_node.data
 def __eq__(self, other_list):
 iter_node_A = self.head
 iter_node_B = other_list.head
 while iter_node_A and iter_node_B:
 if iter_node_A.data != iter_node_B.data:
 return False
 iter_node_A = iter_node_A.next
 iter_node_B = iter_node_B.next
 if not iter_node_A and not iter_node_B:
 return True
 else:
 return False
 def __iter__(self):
 iter_node = self.head
 while iter_node:
 yield iter_node
 iter_node = iter_node.next

Answer 1

Confession: I've never actually written a linked list. At a cursory glance, this implementation looks fine, but I don't know any of the common mistakes. Would be good for somebody who knows more about them (perhaps even an actual interviewer) to give it the stamp of approval.

Working from top-to-bottom:

• There are no docstrings or comments anywhere in this code. I'm aware that's not always possible in an interview situation – but since you're writing this in advance, you can probably do it (after the fact, if nothing else).

  It makes the code easier to read, review and maintain. It's also a good way to expose code that doesn't really make sense.

• The __repr__ of a class is usually a string that could be eval’d to get an equivalent object. What you’ve written for Node is more like what I’d expect for __str__. More like:

  def __repr__(self):
   return '%s(data=%r, next_node=%r)' % (self.__class__.__name__,
   self.data,
   self.next)
  

• In the prepend method of LinkedList, you're not taking advantage of the constructor API you've defined for Node. You could write it more compactly as:

  def prepend(self, data):
   new_head = Node(data, next_node=self.head)
   self.head = new_head
  

  (削除) There's also a typo – the new_head2 variable isn't defined. Perhaps you meant self.head = new_head? (削除ここまで) In which case this becomes a one liner:

  def prepend(self, data):
   self.head = Node(data, next_node=self.head)
  

• In general, there's a lot of similar-looking code that strides back and forth through your linked lists. Lots of iter_nodes and positions and the like. Would be good to cut that down.

  Remembering that I know nothing about linked lists, I think it might be helpful to define a __len__ method on your LinkedList class. Combined with __getitem__, this could simplify your insert() and delete() methods.

  Something like:

  def insert(self, position, data):
   # This is incomplete -- you'll need to handle KeyErrors and
   # the like. To mimic the insert() method on __builtin__.list,
   # if position > len(self), just stick it at the end.
   prev_node = self[position]
   next_node = self[position + 1]
   new_node = Node(data, next_node=next_node)
   prev_node.next = new_node
  

  This then drastically simplifies the code for prepend() and append():

  def prepend(self, data):
   self.insert(position=0, data=data)
  def append(self, data):
   # Probably want to check I haven't introduced an off-by-one
   # error here.
   self.insert(position=len(self), data=data)
  

• If nothing else, it seems like you could make more use of your __iter__ method, which comes right at the end and almost seems like an afterthought. That could be really useful. Some examples:

  def __eq__(self, other): # other is the standard arg here
   if len(self) != len(other):
   return False
   for node_s, node_o in zip(self, other):
   if node_s != node_o:
   return False
   return True
  

• I would have your __getitem__ method raise an IndexError if I search off the end of the list, or before I've put in any data. This is a better fit with the semantics of the builtin list. And again, you can rewrite it to take advantage of __iter__:

  def __getitem__(self, position):
   if not self.head or len(self) < position:
   raise IndexError
   for idx, node in self:
   if idx == position:
   return node
  

  Note also that I'm returning the Node instance, not just the data from that node.

• Include an example. Again, caveat that I haven't done this sort of interview much, so don't know if this is even possible, but a little snippet showing how this list is supposed to be used would be helpful.

  It shows off the API, how you think the class should be used, and it's a good way to spot blatantly silly interfaces.

  It also helps if there's a bug in your code – such as the next_head2 typo – because I can see where you were aiming.

And a few quick nitpicks:

• Don't put spaces around default arguments, for example in the __init__ for your Node object.

• Single line between methods on the same class, for example in LinkedList.

• Compare to None with if foo is [not] None, for example in the append method of LinkedList.

• BenC: I suggest that insert just does next_node = prev_node.next instead of a second call to __getitem__, since random access is O(n).
• user92681: I am confused. You mention a "new_head2" typo I made, but I never use a new_head2 variable anywhere
• alexwlchan: @user92681: whelp, must have been a typo I inserted myself. My bad for not double-checking the code I was reviewing against the original. I'll amend the post.
• SuperBiasedMan: You had written \__init__ a lot, was the backslash meant to escape the formatting? While that is necessary normally, eg for __init__, code formatted text escapes all that formatting anyway. (also you need two backslashes for the two underscores, ie: \_\_init__)
• alexwlchan: @SuperBiasedMan Yes, it was formatting. I prefer function names without code formatting, although it’s not a strong preference – somebody changed it and didn’t remove the backslashes. And a single backslash is sufficient to escape the entire expression, at least with SE’s Markdown parser.

Answer 2

Adding on to alexwlchan's notes:

PEP8 suggests surrounding operators with a space, so pos -= 1 rather than pos-=1.

You've implemented __iter__, so LinkedList.__repr__ can be a one-liner:

def __repr__(self):
 return "[%s]" % ", ".join(map(str, self))

although it's really more of a __str__, an informal, readable stringification.

There are also a lot of very similar loops that could be abstracted internally.

Answer 3

@alexwichan Suggested a fine implementation of __eq__

def __eq__(self, other): # other is the standard arg here
 if len(self) != len(other):
 return False
 for node_s, node_o in zip(self, other):
 if node_s != node_o:
 return False
 return True

From there I note that:

• len is a pessimization because it iterates over the two lists once more when there is no real need.

• He wants all of the nodes should be equal, but he is not writing that.

Based on this thoughts, my version of __eq__ is:

def __eq__(self, other):
 return all(self_node == other_node 
 for self_node, other_node in zip(self, other))

I think it is both more readable and more efficient.

A just slightly different version is:

def __eq__(self, other):
 return all(a == b for a, b in zip(self, other))

Because in such small functions long names may be considered just confusing.

Pick any of the two.

---

@Mathias Ettinger Gave a fine fix for a bug in my answer: [1], [1, 2] where considered equal, using itertools.zip_longest fixes the problem. Still note that a Linked List ending with Nones is equal to a shorter linked list, that is:

• [1, 3, 5] == [1, 3, 5, None, None]

This may or may not be acceptable, anyhow remember to document it.

• BenC: If you don't check the lengths, or do an equivalent check while iterating, then all(a == b for a, b in zip([1], [1, 2])) is true. I agree that len should be optimized though.
• 301_Moved_Permanently: itertools.zip_longest should be better to substitute the len check.