linkedlist.py

#!/usr/bin/env python
# -*- coding: utf-8 -*-

from node import Node

class LinkedList:
    def __init__(self, iterable=None):
        last = None
        if iterable:
            for item in reversed(iterable):
                newnode = Node(item, last)
                last = newnode

        self.head = last

    def __eq__(self, other):
        for v1, v2 in zip(self, other):
            if v1 != v2:
                return False
        return True

    def __len__(self):
        c = 0
        n = self.head

        while n:
            c += 1
            n = n.next

        return c

    def __repr__(self):
        return str(self)

    def __str__(self):
        s = ''
        for item in self:
            if not s:
                s += repr(item)
            else:
                s += ' -> ' + repr(item)

        return s

    def __iter__(self):
        n = self.head
        while n:
            t = n.data
            n = n.next
            yield t

    def __getitem__(self, idx):
        assert len(self) > idx
        assert 0 <= idx
        c = 0
        n = self.head

        while n:
            if c == idx:
                return n.data
            c += 1
            n = n.next

    def __delitem__(self, idx):
        assert len(self) > idx
        assert 0 <= idx

        if idx == 0:
            self.head = self.head.next
            return

        p = self.head
        n = self.head.next

        idx -= 1

        while idx:
            idx -= 1
            p = n
            n = n.next

        p.next = n.next
        del n

    def __setitem__(self, idx, value):
        assert len(self) > idx
        assert 0 <= idx
        c = 0
        n = self.head

        while n:
            if c == idx:
                n.data = value

            c += 1
            n = n.next

    def append(self, value):
        newnode = Node(value)

        if self.head:
            n = self.head

            while n:
                if n.next:
                    n = n.next
                else:
                    n.next = newnode
                    return
        else:
            self.head = newnode

    def insert(self, idx, value):
        assert len(self) > idx
        assert 0 <= idx

        if len(self) - 1 == idx:
            self.append(value)
            return

        newnode = Node(value)

        if self.head:
            if idx:
                p = self.head
                n = self.head.next

                while idx:
                    idx -= 1
                    p = n
                    n = n.next

                newnode.next = p.next
                p.next = newnode
            else:
                newnode.next = self.head
                self.head = newnode

        else:
            self.head = newnode


#    def remove_dups(self):
#        seen = set()
#        offset = 0
#        for idx, data in enumerate(self):
#            if data in seen:
#                del self[idx - offset]
#                offset += 1
#            else:
#                seen.add(data)
#
    def remove_dups(self):
        # does not use a buffer
        offset = 0
        for curr, data in enumerate(self):
            for run, rundat in enumerate(self):
                if run == curr - offset:
                    break
                elif data == rundat:
                    del self[curr - offset]
                    offset += 1
                    break


#    def nth_to_last(self, n):
#        for i, val in enumerate(reversed(self)):
#            if n == i:
#                return val

    def nth_to_last(self, n):
        length = len(self)

        idx = length - n - 1
        assert length > idx
        assert 0 <= idx

        c = 0
        n = self.head

        while n:
            if c == idx:
                return n.data
            c += 1
            n = n.next

    # book soln
    def nth_to_last(self, n):
        length = len(self)
        idx = length - n - 1
        assert length > idx
        assert 0 <= idx

        p1 = self.head
        p2 = self.head
        for i in range(n):
            p2 = p2.next

        while p2.next:
            p1 = p1.next
            p2 = p2.next

        return p1.data

    def delete_by_node(self, node):
        n = node
        p = n

        while n.next:
            n.data = n.next.data
            p = n
            n = n.next

        # remove end node
        p.next = None

    def find_loop(self):
        seen = set()
        n = self.head

        while n:
            if n in seen:
                return n
            seen.add(n)
            n = n.next


def add_ll(first, second):
    new = LinkedList()
    carry = 0
    for v1, v2 in zip(first, second):
        val = v1 + v2 + carry
        carry = 0
        while val > 9:
            carry += 1
            val -= 10

        new.append(val)
    return new

node.py

#!/usr/bin/env python
# -*- coding: utf-8 -*-


class Node:
    def __init__(self, value, next=None, prev=None):
        self.data = value
        self.next = next
        self.prev = prev

test_linkedlist.py

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import unittest
import linkedlist as ll

class TestLinkedList(unittest.TestCase):
    def test_init(self):
        l = ll.LinkedList()

        self.assertEqual(l.head, None)

        l = ll.LinkedList([1])
        l = ll.LinkedList([1, 2])

        self.assertEqual(l.head.data, 1)
        self.assertEqual(l.head.next.data, 2)

    def test_append(self):
        l = ll.LinkedList()

        l.append("data!")
        self.assertEqual(l.head.data, "data!")

        l.append(2)
        self.assertEqual(l.head.next.data, 2)

    def test_len(self):
        l = ll.LinkedList()
        l.append("data!")
        self.assertEqual(len(l), 1)
        l.append(2)
        self.assertEqual(len(l), 2)
        l.append(2)
        self.assertEqual(len(l), 3)

    def test_len(self):
        l = ll.LinkedList()
        l.append("data!")
        l.append(2)
        l.append(5.0)
        l.append(3)
        l.append(5.1)
        self.assertEqual(len(l), 5)
        self.assertEqual(l[0], "data!")
        self.assertEqual(l[1], 2)
        self.assertEqual(l[2], 5.0)
        self.assertEqual(l[3], 3)
        self.assertEqual(l[4], 5.1)

        del l[1]
        self.assertEqual(len(l), 4)
        self.assertEqual(l[0], "data!")
        self.assertEqual(l[1], 5.0)
        self.assertEqual(l[2], 3)
        self.assertEqual(l[3], 5.1)

        del l[3]
        self.assertEqual(len(l), 3)
        self.assertEqual(l[0], "data!")
        self.assertEqual(l[1], 5.0)
        self.assertEqual(l[2], 3)
        self.assertEqual(l.head.next.next.next, None)

        del l[0]
        self.assertEqual(len(l), 2)
        self.assertEqual(l[0], 5.0)
        self.assertEqual(l[1], 3)

    def test_get(self):
        l = ll.LinkedList()
        l.append("data!")
        l.append(2)
        l.append(2)

        self.assertEqual(l[0], "data!")
        self.assertEqual(l[1], 2)
        self.assertEqual(l[2], 2)


    def test_set(self):
        l = ll.LinkedList()
        l.append("data!")
        l.append(2)
        l.append(2)

        l[0] = "butts"
        self.assertEqual(l[0], "butts")
        self.assertEqual(l[1], 2)
        self.assertEqual(l[2], 2)

        l[2] = "hiya"
        self.assertEqual(l[0], "butts")
        self.assertEqual(l[1], 2)
        self.assertEqual(l[2], "hiya")

    def test_insert(self):
        l = ll.LinkedList()
        l.append("data!")
        l.append(2)
        l.append(2)
        l.insert(0, "hi")

        self.assertEqual(l.head.data, "hi")

    def test_iter(self):
        l = ll.LinkedList()
        l.append("data!")
        l.append(2)
        l.append(2)
        l.insert(0, "hi")


        self.assertSequenceEqual(l, ["hi", "data!", 2, 2])


    def test_remove_dups(self):
        l = ll.LinkedList()
        l.append("data!")
        l.append(2)
        l.append("hi")
        l.append("data!")
        l.append(2)
        l.append("hi")

        l.remove_dups()
        self.assertEqual(l[0], "data!")
        self.assertEqual(l[1], 2)
        self.assertEqual(l[2], "hi")
        self.assertEqual(len(l), 3)

        l = ll.LinkedList()
        l.append("data!")
        l.append("data!")
        l.append(2)
        l.append(2)
        l.append("hi")
        l.append("hi")

        l.remove_dups()
        self.assertEqual(l[0], "data!")
        self.assertEqual(l[1], 2)
        self.assertEqual(l[2], "hi")
        self.assertEqual(len(l), 3)


    def test_nth_to_last(self):
        l = ll.LinkedList()
        l.append(1)
        l.append(2)
        l.append(3)
        l.append(4)
        l.append(5)

        for i in range(5):
            self.assertEqual(l.nth_to_last(i), 5 - i, str(i))

    def test_delete_middle_node(self):
        l = ll.LinkedList()
        l.append(1)
        l.append(2)
        l.append(3)
        l.append(4)
        l.append(5)

        n = l.head.next.next
        l.delete_by_node(n)
        self.assertSequenceEqual(l, [1,2,4,5])

    def test_add_ll(self):
        a = ll.LinkedList([3,1,5])
        b = ll.LinkedList([5,9,2])
        c = ll.LinkedList([8,0,8])

        r = ll.add_ll(a, b)
        self.assertEqual(len(c), len(r))
        self.assertSequenceEqual(list(c), list(r))
        self.assertEqual(c, r)

    def test_find_circular(self):
        l = ll.LinkedList(['a', 'b', 'c' , 'd', 'e'])

        a = l.head
        b = a.next
        c = b.next
        d = c.next
        e = d.next

        # corruption hueheuheu

        e.next = c
        # dont use len(l) now :)

        self.assertIs(c, l.find_loop())

test_node.py

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import unittest
from node import Node

class TestNode(unittest.TestCase):
    def test_init(self):
        a = Node("hi")
        self.assertEqual(a.data, "hi")
        self.assertEqual(a.next, None)

        b = Node("hello", a)
        self.assertEqual(b.data, "hello")
        self.assertEqual(b.next.data, "hi")
        self.assertEqual(b.next.next, None)

        c = Node("hayyyy", b, a)
        self.assertEqual(c.prev.data, "hi")
        self.assertEqual(c.data, "hayyyy")
        self.assertEqual(c.next.data, "hello")