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()

• Peilonrayz: Isn't this a followup question? Also why arn't you using standard Python interfaces? And implementing my 'bug' would help reduce some logic, did you try to implement it?
• greybeard: @Peilonrayz: depends: This seems to extend single linked list with replace(item, replacement) to double linkage. You can refine your bug deriving LinkedList from Node (or a common base, SimSet style).
• Peilonrayz: @greybeard Extending it and posting a follow-up IMO is still a follow-up... My point was that it looks like they've stuck with a WET way of doing things, without a prompt why.

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()) + ')-]'

• greybeard: For a so-so attempt to stay DRY implementing pre/append() see revision 3.