DoublyLinkedList python implementation and unit testing

Question

I wanted to ask for code review for DoublyLinkedList. Especially my insert, find, replace, at_index

I have the following python implementation that handles most of the cases: And I also include my unit testing. I ran against the unit test, and it passed all 12 tests.

class Node(object):

    def __init__(self, data):
        """Initialize this node with the given data"""
        self.data = data
        self.next = None
        self.last = None

    def __repr__(self):
        """Return a string rxepresentation of this node"""
        return 'Node({})'.format(repr(self.data))


class DoublyLinkedList(object):

    def __init__(self, iterable=None):
        """Initialize this linked list; append the given items, if any"""
        self.head = None
        self.tail = None
        self.count = 0

        if iterable:
            for item in iterable:
                self.append(item)

    def __str__(self):
        """Return a formatted string representation of this linked list"""
        items = ['({})'.format(repr(item)) for item in self.items()]
        return '[{}]'.format(' -> '.join(items))

    def __repr__(self):
        """Return a string representation of this linked list"""
        return 'DoublyLinkedList({})'.format(repr(self.items()))

    def items(self):
        """Return a list of adll items in this linked list"""
        result = []
        current = self.head
        while current is not None:
            result.append(current.data)
            current = current.next
        return result

    def is_empty(self):
        """Return True if this linked list is empty, or False"""
        return self.head is None

    def length(self):
        """Return the length of this linked list by traversing its nodes"""
        return self.count

    def append(self, item): 
        """Insert the given item at the tail of this linked list"""
        new_node = Node(item)  
        self.count += 1  

        if self.head is None:  
            self.head = new_node  
        else:
            self.tail.next = new_node  
            new_node.last = self.tail

        self.tail = new_node  

    def prepend(self, item): 
        """Insert the given item at the head of this linked list"""
        new_node = Node(item)   
        self.count += 1  

        if self.head is None:  
            self.head = new_node  
            self.tail = self.head  
        else:  
            new_node.next = self.head  
            self.head = new_node  

    def delete(self, item):  
        """Delete the given item from this linked list, or raise ValueError"""
        last = None
        current_node = self.head

        while current_node is not None:  
            # The current node is the ones we are looking for
            if current_node.data == item:  
                # Our tail is our current node
                if self.tail == current_node:  
                    self.tail = last  

                if last is None:  
                    # If we are the head. We set the new head to the next value.
                    self.head = current_node.next  
                else:
                    # We aint the head so we set the last nodes head to the next node 
                    last.next = current_node.next  

                    if current_node.next is not None:
                        current_node.next.last = last

                self.count -= 1  
                return  # Stop checking. Don't return an error

            last = current_node  
            current_node = current_node.next  

        raise ValueError

    def size(self):
        """ Gets the size of the Linked List
        AVERAGE: O(1)
        """
        return self.count

    def _at_index(self, index):
        """ Helper method used to get the node at an index


        """
        next_node = self.head

        while index > -1 or next_node is not None:
            if index == 0:
                return next_node

            next_node = next_node.next
            index -= 1

        return None

    def at_index(self, index):
        """ Gets data at an index


        """
        at_index = self._at_index(index)

        if at_index is None:
            return None

        return at_index.data

    def insert(self, index, data):
        """ Inserts data at a specific index
        """
        if index == 0:
            self.prepend(data)
            return

        at_index = self._at_index(index - 1)

        if at_index is None:
            raise IndexError

        if at_index.next is None:
            self.append(data)
            return

        new_node = Node(data)

        if at_index.next is not None:
            at_index.next.last = new_node

        new_node.next = at_index.next
        at_index.next = new_node

        new_node.last = at_index

    def find(self, quality):  
        """Return an item from this linked list satisfying the given quality"""
        current = self.head  

        while current is not None: 
            if quality(current.data):  # We no know
                return current.data  

            current = current.next  

    def reverse(self):
        next_node = self.head.next

        previous_node = self.head

        self.tail = previous_node

        self.head.next = None

        while next_node is not None:
            current_node = next_node
            next_node = current_node.next
            previous_node.last = current_node
            current_node.next = previous_node
            previous_node = current_node
        self.head = previous_node
        self.head.last = None

    def _find(self, data):
        """ Finds a node with data or returns None if we can't find a node """
        current = self.head

        while current is not None:
            if current.data == data:
                return current

            current = current.next

    def replace(self, old_data, new_data):
        """ Replaces data with new data """
        old_node = self._find(old_data)

        if old_node is None:
            raise ValueError

        old_node.data = new_data



def test_DoublyLinkedList():
    dll = DoublyLinkedList()
    print(dll)
    print('Appending items:')
    dll.append('A')
    print(dll)
    dll.append('B')
    print(dll)
    dll.append('C')
    print(dll)
    print('head: {}'.format(dll.head))
    print('tail: {}'.format(dll.tail))
    print('size: {}'.format(dll.size))
    print('length: {}'.format(dll.length()))

    print('Deleting items:')
    dll.delete('B')
    print(dll)
    dll.delete('C')
    print(dll)
    dll.delete('A')
    print(dll)
    print('head: {}'.format(dll.head))
    print('tail: {}'.format(dll.tail))
    print('size: {}'.format(dll.size))
    print('length: {}'.format(dll.length()))

    print("testing: DoublyLinkedList replace ___________________")
    dll = DoublyLinkedList(['A', 'B', 'C'])
    dll.replace('A', 'D')
    print(dll)

    dll = DoublyLinkedList(['A', 'B', 'C'])
    print(dll)
    print("testing: insert_at_index ___________________")
    print('size: {}'.format(dll.size))
    dll.insert(0, 'AA')
    print(dll)
    print("testing: insert_at_index 0, 'AA'___________________")
    dll.insert(2, 'BB')
    print("testing: insert_at_index 2, 'BB'___________________")
    print(dll)

if __name__ == '__main__':
    test_DoublyLinkedList()




#!python

import DoublyLinkedList, Node
import unittest


class NodeTest(unittest.TestCase):

    def test_init(self):
        data = 'ABC'
        node = Node(data)
        assert node.data is data
        assert node.next is None


class LinkedListTest(unittest.TestCase):

    def test_init(self):
        dll = DoublyLinkedList()
        assert dll.head is None
        assert dll.tail is None

    def test_init_with_list(self):
        dll = DoublyLinkedList(['A', 'B', 'C'])
        assert dll.head.data == 'A'
        assert dll.tail.data == 'C'

    def test_items(self):
        dll = DoublyLinkedList()
        assert dll.items() == []
        dll.append('A')
        assert dll.items() == ['A']
        dll.append('B')
        assert dll.items() == ['A', 'B']
        dll.append('C')
        assert dll.items() == ['A', 'B', 'C']


    def test_append(self):
        dll = DoublyLinkedList()
        dll.append('A')
        assert dll.head.data == 'A'
        assert dll.tail.data == 'A'
        dll.append('B')
        assert dll.head.data == 'A'
        assert dll.tail.data == 'B'
        dll.append('C')
        assert dll.head.data == 'A'
        assert dll.tail.data == 'C'

    def test_prepend(self):
        dll = DoublyLinkedList()
        dll.prepend('C')
        assert dll.head.data == 'C'
        assert dll.tail.data == 'C'
        dll.prepend('B')
        assert dll.head.data == 'B'
        assert dll.tail.data == 'C'
        dll.prepend('A')
        assert dll.head.data == 'A'
        assert dll.tail.data == 'C'

    def test_delete(self):
        dll = DoublyLinkedList()
        dll.append('A')
        dll.append('B')
        dll.append('C')
        dll.delete('A')
        assert dll.head.data == 'B'
        assert dll.tail.data == 'C'
        dll.delete('C')
        assert dll.head.data == 'B'
        assert dll.tail.data == 'B'
        dll.delete('B')
        assert dll.head is None
        assert dll.tail is None
        with self.assertRaises(ValueError):
            dll.delete('D')

    def test_find(self):
        dll = DoublyLinkedList()
        dll.append('A')
        dll.append('B')
        dll.append('C')
        assert dll.find(lambda item: item == 'B') == 'B'
        assert dll.find(lambda item: item < 'B') == 'A'
        assert dll.find(lambda item: item > 'B') == 'C'
        assert dll.find(lambda item: item == 'D') is None

    def test_reverse_three(self):
        dll = DoublyLinkedList()
        dll.append('1')
        dll.append('2')
        dll.append('3')
        assert dll.items() == ['1', '2', '3']
        dll.reverse()
        assert dll.items() == ['3', '2', '1']

    def test_reverse_two(self):
        dll = DoublyLinkedList()
        dll.append('1')
        dll.append('2')
        assert dll.items() == ['1', '2']
        dll.reverse()
        assert dll.items() == ['2', '1']

    def test_reverse_one(self):
        dll = DoublyLinkedList()
        dll.append('1')
        assert dll.items() == ['1']
        dll.reverse()
        assert dll.items() == ['1']

    def test_size(self):
        dll = DoublyLinkedList()
        assert dll.size() == 0
        dll.append('4')
        dll.append('3')
        assert dll.size() == 2
        dll.delete('4')
        assert dll.size() == 1
        dll.delete('3')
        assert dll.size() == 0

    def test_at_index(self):
        dll = DoublyLinkedList()
        dll.append('4')
        dll.append('3')
        assert dll.at_index(-1) is None
        assert dll.at_index(0) == '4'
        assert dll.at_index(1) == '3'
        assert dll.at_index(2) is None
        dll.delete('4')
        assert dll.at_index(0) == '3'

    def test_insert(self):
        dll = DoublyLinkedList()
        dll.append('4')
        dll.append('3')
        dll.insert(0, '2')
        assert dll.items() == ['2', '4', '3']
        dll.insert(3, '9')
        assert dll.items() == ['2', '4', '3', '9']
        dll.insert(2, '8')
        assert dll.items() == ['2', '4', '8', '3', '9']

    def test_last(self):
        dll = DoublyLinkedList()
        dll.append('4')
        dll.append('3')
        assert dll._at_index(0).last is None
        assert dll._at_index(1).last.data == '4'
        dll.insert(1, '7')
        assert dll._at_index(2).last.data == '7'
        assert dll._at_index(1).last.data == '4'
        dll.delete('3')
        assert dll._at_index(1).last.data == '4'

    def test_replace(self):
        dll = DoublyLinkedList()
        dll.append('4')
        dll.append('3')
        dll.append('2')
        assert dll.items() == ['4', '3', '2']
        dll.replace('3', '9')
        assert dll.items() == ['4', '9', '2']
        dll.replace('4', '5')
        assert dll.items() == ['5', '9', '2']
        dll.replace('2', '1')
        assert dll.items() == ['5', '9', '1']
        with self.assertRaises(ValueError):
            dll.replace('99999', '1')


if __name__ == '__main__':
    unittest.main()

Answer 1

Strategy

To support (coding and) code review (especially when asking for alternatives), state (in the code) the goal pursued during coding. (Double linkage/last serves no purpose I can see.)

If not literally re-inventing a support on solid surfaces combining low longitudinal friction with good lateral guide, use/implement an existing "protocol"/"interface" - mutable sequence comes to mind seeing the methods you present; something like test_MutableSequence() may fall into your lap.

Explicitly specify everything protocol but not standard using docstrings. Sketch tests: If you don't know what to test, you don't know what to implement.

Tactics

• specify what is to happen with parameter values without "natural" meaning, e.g., index smaller zero or not smaller count.
• (as @Peilonrayz demanded:) Don’t Repeat Yourself
• provide docstrings for classes (and modules), too
• check comments and, arguably more important, docstrings for correctness
• when a second error passes unit testing after thinking unit tests complete, revise unit tests

Observations about the code, [especially] insert, find, replace, at_index:

• insert fails to update count
• find, replace: replace (& _find) might use find. With quality satisfied with more than one node's data, both are underspecified.
• _at_index: if count/2 < index < count, walk backwards
  (it may be useful to allow indices from -count (even with at_index or generally) - cf. slicing)
• delete looks non-adapted from a singly-linked list implementation (no need for last)
  current.next.last should be set depending on current == tail
  should use find()
• insert fails to set old_head.last
• reverse: how about transmuting to an instance of ListLinkedDoubly, with roles of next and last exchanged(&head/tail, if sticking with no sentinel node (@Peilonrayz, again))
  As presented, reverse() is a costly operation - reversed() returns an iterator
• __str__: return '[]' if 0 == self.count \
          else '[-(' + ')<=>('.join(self.items()) + ')-]'