2
\$\begingroup\$

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()
\$\endgroup\$
  • \$\begingroup\$ 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? \$\endgroup\$ – Peilonrayz Nov 9 '17 at 9:19
  • \$\begingroup\$ @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). \$\endgroup\$ – greybeard Jan 24 '18 at 21:45
  • \$\begingroup\$ @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. \$\endgroup\$ – Peilonrayz Jan 24 '18 at 21:51
2
\$\begingroup\$

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()) + ')-]'
\$\endgroup\$
  • \$\begingroup\$ For a so-so attempt to stay DRY implementing pre/append() see revision 3. \$\endgroup\$ – greybeard Jan 25 '18 at 14:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.