jan 2 Coding for Interviews challenge

linkedlist.py

class LinkedList(object):
    def __init__(self):
        self.head = None
        self.tail = None
        self.count = 0

    def prettyprint(self):
        """iterate and print from head to taill"""
        node = self.head
        while node:
            print node.data
            node = node.nextnode

    def add_node(self, data):
        """add a node with the given object in its data field"""
        node = ListNode(data)
        if self.head:
            self.head.prevnode = node
            node.nextnode = self.head
        self.head = node
        return node

    def delete_value(self, data):
        """delete a node by data lookup"""
        self.delete_node(self.find_value(data))

    def remove_third_from_last(self):
        """Question 1 with challenge"""
        node = self.head
        while node.nextnode.nextnode.nextnode:
            node = node.nextnode
        self.delete_node(node)

    def delete_node(self, node):
        """deletes node and returns the next"""
        if not node:
            return

        nnext = node.nextnode

        if self.count is 1:
            self.head = self.tail = None
            return

        if node is self.head:
            self.head = node.nextnode
        else:
            node.prevnode.nextnode = node.nextnode

        if node is self.tail:
            self.tail = node.prevnode
        else:
            node.nextnode.prevnode = node.prevnode

        return nnext

    def deduplicate(self):
        """question 2 with challenge"""
        node = self.head
        while node:
            value = node.data
            innerloopnode = self.head
            while innerloopnode:
                if value == innerloopnode.data and innerloopnode is not node:
                    innerloopnode = self.delete_node(innerloopnode)
                else:
                    innerloopnode = innerloopnode.nextnode
            node = node.nextnode

    def find_value(self, data):
        """find and return a node by data, None if not present"""
        cur = self.head
        while cur:
            if cur.data == data:
                return cur
            cur = cur.nextnode

    def contains_loop(self):
        """Question 3: maintain a linked list of visited nodes
        if any current node has been visited before, a loop is found"""
        metalist = LinkedList()  # just for fun, use this very class
        node = self.head
        while node:
            metalist.add_node(node)
            metanode = metalist.head
            while metanode:
                if metanode.data is node:
                    return True
            node = node.nextnode
        return False


class ListNode(object):
    def __init__(self, data):
        self.data = data
        self.nextnode = None
        self.prevnode = None

linkedlist.txt

Linked Lists
============

A linked list is a simple list data structure in which elements are only
accessible sequentially. The list is composed of nodes, each of which contains
a pointer to the node succeeding it in the list. If a pointer to the
preceeding node is included, it is known as a doubly-linked list.

The list structure itself contains pointers to the head and tail (first and
last elements), as well as functions for insterting, removing, and finding
nodes by identity or value.

An important consideration when implementing a linked list is the inclusion of
a sentinel node. This is a node at the end of the list containing some known
special value that signifies the list's termination. This can simplify code
that iterates over the entire list. It is also important to consider special
cases for insertion and deletion at the head or tail of the list, and to avoid
cycles.

tests.py

import unittest
import random

from linkedlist import LinkedList


class TestLinkedList(unittest.TestCase):
    def setUp(self):
        self.linkedlist = LinkedList()
        for i in range(1, 1000):
            self.linkedlist.add_node(i)

    def test_delete(self):
        val = random.randint(1, 1000)
        elem = self.linkedlist.find_value(val)
        if elem:
            self.linkedlist.delete_value(val)
            self.assertTrue(self.linkedlist.find_value(val) is None)

    def test_contains_loop(self):
        looplist = LinkedList()
        looplist.add_node(1)
        looplist.add_node(2)
        looplist.add_node(3).nextnode
        looplist.find_value(1).nextnode = looplist.find_value(3)
        self.assertTrue(looplist.contains_loop())


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