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.

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.