Sorted unidirectional list with add, delete and find

Question

I am aware of the fact that a sorted unidirectional list has only very few use cases, but nevertheless, this python code feels fairly long for Python code. How can I improve it?

class List:
 def __init__(self, list):
 self.first = list
 def __repr__(self):
 element = self.first
 elementsList = ''
 while (element != None):
 elementsList += str(element) + '\n'
 element = element.next
 return elementsList
 """Searches for names in list, starts at 0, returns predecessor as object if possible, returns -1 if not found"""
 def search(self, name):
 if self.first.name == name:
 return 0
 else: return self.search_rec(self.first, name, 1)
 """Recursive workhorse for search"""
 def search_rec(self, item, name, i):
 if item.next != None:
 if item.next.name == name:
 return i, item.name
 else:
 return self.search_rec(item.next, name, i+1)
 else: return -1
class Element:
 """Class to implement elements of the list"""
 """Append item to list or create one"""
 def __init__(self, name, listPos=None):
 if listPos != None:
 listPos = listPos.parent.first
 self.parent = listPos.parent
 previous = None
 while (listPos.name < name and listPos.next != None):
 previous, listPos = listPos, listPos.next
 if previous != None:
 previous.next, self.next = self, listPos
 else: self.parent.first = self
 else:
 self.parent = List(self)
 self.name = name
 self.next = listPos
 def __del__(self):
 print(repr(self) + ' dies now...')
 def delete(self):
 if (self == self.parent.first): self.parent.first = self.next
 else:
 listPos = self.parent.first
 while (listPos.next != self):
 listPos = listPos.next
 if listPos.next.next != None: listPos.next = listPos.next.next
 else: listPos.next = None
 def __repr__(self):
 return '[%s]' % self.name
 def __str__(self):
 if self.next != None:
 next = 'Next element: ' + self.next.name
 else:
 next = '*end of the list*'
 return repr(self) + '\n' + next
x = Element('test')
a = Element('d', x)
y = Element('c', x)
z = Element('a', x)
print(x.parent)
a.delete()
print(a.parent)
print(x.parent.search('c'))

Answer 1

For starters, you should read PEP 8, the Python style guide. A few things that jump out from your code:

• Variable names should be lowercase_with_underscores, not dromedaryCase.
• Docstrings go inside the function body, not above the header.
• Always put newlines after if, elif and else for multi-line statements. You do it inconsistently, which makes your code quite hard to follow.

Following these guidelines will make your code easier for other Python programmers to read.

Here are some brief, general comments on your code:

• Pick better variable names. In the init function for the List class, you’ve got the variable name list. Pick something more meaningful (such as unidirectional_list, or whatever is appropriate).

  Although List and Element aren't keywords, they are sufficiently generic that I’d suggest picking different ones.

• Difference between __str__ and __repr__. The goal of __repr__ is to generate a string which can be eval()'d to return an equivalent object; the goal of __str__ is to return a human-readable interpretation.

  The __repr__ method in List looks like it should really be __str__, and the __repr__ method for Element returns a singleton rather than something I can eval() to get another instance of the Element class.

  See a question about this on Stack Overflow for more details.

• Use a list comprehension in the __repr__/__str__ for List. Since we know that element.first is a Python list (although it’s not obvious from the attribute name; I’d suggest changing it), we can rewrite this using a list comprehension, then use join to construct the string. This is better than repeatedly appending to a string.

  So you'd have something like:

  def __str__(self):
   return '\n'.join(str(e) for e in self.first)
  

  which is a lot cleaner.

• Be explicit about comparisons to None. Maybe it’s just me, but I think x is not None is better than x != None.

• Don't put examples/tests in the body of the script. At the bottom of the code are a few examples, which are helpful when I'm trying to review the code, but not in general use. Right now, if you import the file, all of those bits run and litter your output.

  Either wrap them in an if __name__ == '__main__' block (see this Stack Overflow question for details), or consider using a dedicated library for tests. Then these examples will be executed if the file is run directly, but skipped if you import it in a larger file.