doubly_linked_list.py

"""Implement doubly-linked list in Python."""


class Node:
    """Node implementation for doubly-linked list."""

    def __init__(self, v=None, next=None, prev=None):
        """Construct a node."""
        self.value = v
        self.next = next
        self.prev = prev


class DoublyLinkedList:
    """Implementation of doubly-linked list."""

    def __init__(self, head=None, tail=None, length=0):
        """Construct a doubly-linked list."""
        self.head = head
        self.tail = tail
        self.length = length

    def is_empty(self):
        """Return True if the list is empty; False otherwise."""
        return self.length == 0

    def prepend(self, v):
        """Prepend given value to the linked list."""
        new_cell = Node(v, self.head, None)

        # prepend when the list is empty
        if self.is_empty():
            self.head = new_cell
            self.tail = new_cell
            self.length = 1
            return self

        # prepend when the list is not empty
        self.head.prev = new_cell
        self.head = new_cell
        self.length = self.length + 1
        return self

    def seek_from_end(self, i):
        """Return value at index i from the end of the list."""
        

class TestDoublyLinkedList(object):
    """Test doubly-linked list."""

    def test_creation(self):
        """Test __init()__ functionality."""
        n = Node(5)
        ll = DoublyLinkedList(n, length=1)
        assert ll.length == 1
        ll.prepend(6)
        ll.prepend(19)
        ll.prepend(121)
        assert ll.length == 4
        ll2 = DoublyLinkedList()
        assert ll2 is not None
        assert ll2.length == 0
        assert ll2.head is None
        assert ll2.tail is None
        ll2.prepend(8)
        assert ll2.head is not None
        assert ll2.tail is not None
        assert ll2.length == 1
        assert ll2.head.value == 8
        assert ll2.tail.value == 8
        assert ll2.head.next is None
        assert ll2.tail.next is None
        assert ll2.head.prev is None
        assert ll2.tail.prev is None
        ll2.prepend(9)
        assert ll2.length == 2
        assert ll2.head.value == 9
        assert ll2.tail.value == 8
        assert ll2.head.next is not None
        assert ll2.tail.next is None
        assert ll2.head.prev is None
        assert ll2.tail.prev is not None
        assert ll2.head.next.value == 8
        assert ll2.tail.prev.value == 9