Doubly-linked list implementation in Python with unit-tests

Question

I am soliciting some feedback on my doubly-linked list implementation. In particular, I am looking for your take on my unit-tests and their coverage of the code itself. That is, I developed this class using the test-driven development approach and am wondering how it turned out. In addition, I would welcome any suggestions on making the code more readable and/or efficient (eliminate redundancies, etc).

class DLinkedList(object):
    _size = 0
    class Node(object):
        def __init__(self, _value, _previous, _next):
            self.value = _value
            self.next = _next
            self.previous = _previous

        def __eq__(self, other):
            return (self.value == other.value) and (self.next == other.next) and (self.previous == other.previous)


    def __init__(self):
        self.head = None
        self.tail = None
        self._size = 0        

    def __len__(self):
        if self.head:
            return self._size
        else:
            return 0

    def __str__(self):
        current = self.head
        to_print = []
        while current:
            to_print.append(current.value)
            current = current.next
        return str(to_print)   


    def insert(self, _value, _position=0, _previous = None, _next = None):
        if _value is None:
            raise ValueError('Cannot add None item to a list')
        if _position < 0:
            raise ValueError('Cannot add to negative position in the list')
        if _position == 0:
            if self.head:
                new_node = self.Node(_value, None, self.head)
                old_node = self.head
                self.head = new_node
                old_node.previous = new_node
                self._size = self._size + 1
            else:
                new_node = self.Node(_value, None, None)
                self.tail = new_node
                self.head = new_node
                self._size = self._size + 1
            return new_node
        else:
            current = self.head
            count = 0
            while current and ((count+1)<=_position):
                #found the position to insert into or reached last item
                # if last item, insert at the end
                if (count + 1 == _position) or (count + 1 == self._size):
                    self.node = self.Node(_value, current, current.next)
                    if current.next:
                        current.next.previous = self.node
                    current.next = self.node
                    self._size = self._size + 1
                    return self.node
                else:
                    current = current.next
                    count += 1
    def search(self, _value):
        if _value is None:
            raise ValueError('Cannot search for a value=None item to a list')

        current = self.head
        found = False
        while current and not found:
            if current.value == _value:
                found = True
            else:    
                current = current.next
        return current

    def delete(self, _value):
        current = self.head
        previous = None
        found = False
        while current and not found:
            if current.value == _value:
                found = True
                self._size = self._size - 1
            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:
            self.head = current.next
        # item from inside of the list is being deleted    
        else:
            previous.next = current.next

        return current

Unit-tests:

class TestDLinkedList(unittest.TestCase):
    d_linked_list = None

    def setUp(self):
        self.d_linked_list = DLinkedList()

    def test_init(self):
        self.assertEqual(self.d_linked_list.head, None, "Initial HEAD should be None")
        self.assertEqual(self.d_linked_list.tail, None, "Initial TAIL should be None")
        self.assertEqual(len(self.d_linked_list), 0, "Initial length should be zero")

    def test_insert_exceptions(self):
        self.assertRaises(ValueError, self.d_linked_list.insert, None, 0)
        self.assertRaises(ValueError, self.d_linked_list.insert, 1, -1)
    def test_search_exceptions(self):
        self.assertRaises(ValueError, self.d_linked_list.search, None)

    def test_insert_beginning(self):
        node1 = self.d_linked_list.insert(1,0)
        self.assertEqual(node1, self.d_linked_list.Node(1, None, None), "Inserting 1 into empty list should return node with value=1")
        self.assertEqual(self.d_linked_list.head, node1, "After inserting an element into the list, the HEAD != None")
        self.assertEqual(self.d_linked_list.tail, node1, "After inserting an element into the list, the TAIL != None")

        node2 = self.d_linked_list.insert(2,0)

        self.assertEqual(node2.value, self.d_linked_list.Node(2, None, None).value, "Inserting 2 into list at zeroth position should return the node itself")
        self.assertEqual(self.d_linked_list.head.value, node2.value, "After inserting second element into the list, the HEAD should point to that element")
        self.assertEqual(self.d_linked_list.tail.value, node1.value, "After inserting second element into the list, the TAIL should point to the first element inserted")
        self.assertEqual(self.d_linked_list.head.next.value, node1.value, "After inserting second element into the list, the first.next should point to the first inserted element")
        self.assertEqual(self.d_linked_list.tail.previous.value, node2.value, "After inserting second element into the list, the TAIL.previous should point to the newly inserted element")

        node3 = self.d_linked_list.insert(3,0)
        self.assertEqual(node3.value, self.d_linked_list.Node(3, None, None).value, "Inserting 3 into list at zeroth position should return the node itself")
        self.assertEqual(self.d_linked_list.head.value, node3.value, "After inserting second element into the list, the HEAD should point to that element")
        self.assertEqual(self.d_linked_list.tail.value, node1.value, "After inserting third element into the list, the TAIL should point to the first element inserted")
        self.assertEqual(self.d_linked_list.head.next.value, node2.value, "After inserting third element into the list, the first.next should point to the second inserted element")
        self.assertEqual(self.d_linked_list.tail.previous.value, node2.value, "After inserting third element into the list, the TAIL.previous should point to the secondly inserted element")

    def test_insert_position(self):
        self.assertEqual(str(self.d_linked_list), '[]', "List should be printed as [] when empty")
        node1 = self.d_linked_list.insert(1,0)
        self.assertEqual(node1, self.d_linked_list.Node(1, None, None), "Inserting 1 into empty list should return node with value=1")
        self.assertEqual(str(self.d_linked_list), '[1]', "List should be printed as [1] when node with value 1 is inserted")
        node2 = self.d_linked_list.insert(2,0)
        self.assertEqual(str(self.d_linked_list), '[2, 1]', "List should be printed as [2,1] when nodes with values 1 and 2 are inserted")
        node3 = self.d_linked_list.insert(3,1)
        self.assertEqual(str(self.d_linked_list), '[2, 3, 1]', "List should be printed as [2, 3, 1] when node with value 3 is inserted into position=1")
        node4 = self.d_linked_list.insert(4,3)
        self.assertEqual(str(self.d_linked_list), '[2, 3, 1, 4]', "List should be printed as [2, 3, 1, 4] when node with value 4 is inserted into position=3")

    def test_search(self):
       self.assertEqual(self.d_linked_list.search(1), None,'When searching an empty list for ANY item, the search should return None')
       node1 = self.d_linked_list.insert(1,0)
       self.assertEqual(self.d_linked_list.search(1), node1,'When searching the [1] list for 1, the search should return Node=1')
       node2 = self.d_linked_list.insert(2,0)
       self.assertEqual(self.d_linked_list.search(2).value, node2.value,'When searching the [2,1] list for 2, the search should return Node=2')
       node3 = self.d_linked_list.insert(3,1)
       self.assertEqual(self.d_linked_list.search(3).value, node3.value,'When searching the [2,3,1] list for 3, the search should return Node=3')
       node3 = self.d_linked_list.insert(4,3)
       self.assertEqual(self.d_linked_list.search(4).value, node3.value,'When searching the [2,3,1,4] list for 4, the search should return Node=4')

    def test_delete(self):
        self.assertEqual(self.d_linked_list.delete(1), None,'When trying to delete ANY item from empty list, the search should return None')
        node1 = self.d_linked_list.insert(1,0)
        self.assertEqual(self.d_linked_list.delete(1), node1,'When searching the [1] list for 1, the search should return Node=1')
        node2 = self.d_linked_list.insert(2,0)
        node3 = self.d_linked_list.insert(3,0)
        self.assertEqual(str(self.d_linked_list), '[3, 2]', "List should be printed as [3, 2] after node.value=3 is inserted into position=0")
        self.assertEqual(len(self.d_linked_list), 2, "List should be length=2 after inserting two elements")
        self.assertEqual(self.d_linked_list.delete(2), node2,'When deleting 1 from the list, the search should return Node=1')
        self.assertEqual(str(self.d_linked_list), '[3]', "List should be printed as [3] after node.value=2 is deleted")
        node4 = self.d_linked_list.insert(4,0)
        self.assertEqual(str(self.d_linked_list), '[4, 3]', "List should be printed as [4, 3] after node.value=4 is inserted into position=0")
        self.assertEqual(self.d_linked_list.delete(3), node3,'When deleting 3 from the list, the search should return Node=3')
        self.assertEqual(self.d_linked_list.delete(4), node4,'When deleting 4 from the list, the search should return Node=4')
        self.assertEqual(str(self.d_linked_list), '[]', "List should be printed as [] all elements are deleted from it")

    def test_len(self):
        self.assertEqual(len(self.d_linked_list), 0, "Empty list is of length zero")
        node1 = self.d_linked_list.insert(1,0)
        self.assertEqual(len(self.d_linked_list), 1, "List with one element is of length=1")
        node2 = self.d_linked_list.insert(2,0)
        self.assertEqual(len(self.d_linked_list), 2, "List with two elements is of length=2")
        node3 = self.d_linked_list.insert(3,0)
        self.assertEqual(len(self.d_linked_list), 3, "List with three elements is of length=3")
        node4 = self.d_linked_list.insert(4,2)
        self.assertEqual(len(self.d_linked_list), 4, "List with four elements is of length=4")

    def test_list(self):
        self.assertEqual(str(self.d_linked_list), '[]', "List should be printed as [] when empty")
        node1 = self.d_linked_list.Node(1, None, None)
        self.d_linked_list.insert(1)
        self.assertEqual(str(self.d_linked_list), '[1]', "List should be printed as [1] after node.value=1 is inserted")
        node2 = self.d_linked_list.insert(2,0)
        self.assertEqual(str(self.d_linked_list), '[2, 1]', "List should be printed as [2, 1] after node.value=2 is inserted into position=0")
        node3 = self.d_linked_list.insert(3,1)
        self.assertEqual(str(self.d_linked_list), '[2, 3, 1]', "List should be printed as [2, 3, 1] after node.value=3 is inserted into position=1")
        node4 = self.d_linked_list.insert(4,3)
        self.assertEqual(str(self.d_linked_list), '[2, 3, 1, 4]', "List should be printed as [2, 3, 1, 4] after node.value=4 is inserted into position=3")
        node5 = self.d_linked_list.insert(5,10)
        self.assertEqual(str(self.d_linked_list), '[2, 3, 1, 4, 5]', "List should be printed as [2, 3, 1, 4, 5] after node.value=5 is inserted into position>length(list)")

Answer 1

Here are some high-level "round 1" notes to make the code cleaner and more Pythonic:

• since you are implementing a "doubly linked list", name the class DoublyLinkedList instead of a more questionable DLinkedList

• I don't see much point in nesting the Node class inside the linked list, define it separately (and, you know, "Flat is better than nested"):

  class Node(object):
      # ...
  
  
  class DoublyLinkedList(object):
      # ...
  

  This would also lead to using Node in place of self.Node (and you would also need to use node variable name in place of Node in the insert() method)

• there is not need to define _size on the class level - leave it defined in the class constructor:

  class DoublyLinkedList(object):
      _size = 0  # <-- REMOVE THIS LINE
  

• do not put underscore prefix in front of method arguments names - this kind of notation is reserved for "private" attributes (not enforced by the language though)

• I would also remove the _ from the _size variable - I don't see why would you "hide" it from your linked list's public API

• you can also use the size += 1 and size -= 1 shortcuts instead of size = size + 1 and size = size - 1

• you can omit the parenthesis around the if conditions. For instance, you may replace:

  def __eq__(self, other):
      return (self.value == other.value) and (self.next == other.next) and (self.previous == other.previous)
  

  with:

  def __eq__(self, other):
      return self.value == other.value and \
             self.next == other.next and \ 
             self.previous == other.previous
  

Some other thoughts:

• check out attrs package that is quite handy and helps to avoid a lot of classes/properties/attributes boilerplate
• ideally, the tests should give a clear idea on how the code under test is used, give a good sense of the available API and it's usage. The tests you currently have are not quite readable, try to make the test methods smaller aiming to "one assertion per test method" rule (which itself is extreme, but good to keep in mind), making more descriptive test method names

• what if we improve the linked list "pretty-printing" and, instead of calling str() on a list, we'll use <--> separator. Something like:

  def __str__(self):
      current = self.head
  
      to_print = []
      while current:
          to_print.append(current.value)
          current = current.next
  
      return "(HEAD) {items} (TAIL)".format(items=" <--> ".join(map(str, to_print)))
  

  would result into this printed linked list version:

  In [1]: dll = DoublyLinkedList()
  
  In [2]: dll.insert(1, 0)
     ...: dll.insert(3, 0)
     ...: dll.insert(5, 0)
  
  In [3]: print(dll)
  (HEAD) 5 <--> 3 <--> 1 (TAIL)
  

• I think there is a separation of concerns issue. It feels like the Node instead of the linked list itself should decide where the value passed to it's constructor is an allowed one. Consider moving the value "is None" check to the Node class.