Python Linked List

python_linked_list.py

class SingleNode():
    def __init__(self, data=None, next=None):
        self.data = data
        self.next = next

    def __repr__(self):
        return repr(self.data)


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

    def __repr__(self):
        return repr(self.data)


class SingleLinkedList():

    def __init__(self):
        self.head = None

    def append(self, data):
        if self.head == None:
            self.head = SingleNode(data)
        else:
            curr = self.head
            while curr.next:
                curr = curr.next
            curr.next = SingleNode(data)

    def prepend(self, data):
        self.head = SingleNode(data, next=self.head)

    def remove_duplicates(self):
        values = []
        curr = self.head

        if curr:
            values.append(curr.data)

        while curr.next:
            if curr.next.data in values:
                # Remove
                curr.next = curr.next.next
            else:
                values.append(curr.next.data)
                curr = curr.next

    def find(self, data):
        curr = self.head
        while curr:
            if curr.data == data:
                return curr
            curr = curr.next

        return None

    def remove(self, data):
        curr = self.head

        if curr and curr.data == data:
            self.head = curr.next

        while curr.next:
            if curr.next.data == data:
                curr.next = curr.next.next
            curr = curr.next

    def reverse(self):
        new = None
        curr = self.head

        while curr:
            new = SingleNode(curr.data, next=new)
            curr = curr.next

        self.head = new

    def __repr__(self):
        data = []
        curr = self.head

        while curr:
            data.append(curr.data)
            curr = curr.next
        return "[" + ", ".join(data) + "]"


class DoubleLinkedList():

    def __init__(self):
        self.head = None

    def find(self, data):
        curr = self.head

        while curr:
            if curr.data == data:
                return curr
            curr = curr.next
        return None

    def prepend(self, data):
        if not self.head:
            self.head = DoubleNode(data)
        else:
            self.head.prev = DoubleNode(data, prev=None, next=self.head)
            self.head = self.head.prev

    def append(self, data):
        if not self.head:
            self.head = DoubleNode(data)
        else:
            curr = self.head
            while curr.next:
                curr = curr.next
            curr.next = DoubleNode(data, prev=curr, next=None)

    def remove(self, data):
        curr = self.head

        if curr and curr.data == data:
            curr.next.prev = None
            self.head = curr.next
        else:
            while curr.next:
                if curr.next.data == data:
                    curr.next = curr.next.next
                    curr.next.prev = curr
                curr = curr.next

    def reverse(self):
        new = None

        curr = self.head

        while curr:
            if not new:
                new = DoubleNode(curr.data, prev=None, next=new)
            else:
                new.prev = DoubleNode(curr.data, prev=None, next=new)
                new = new.prev
            curr = curr.next

        self.head = new

    def __repr__(self):
        data = []
        curr = self.head

        while curr:
            text = ""
            if curr.prev:
                text += str(curr.prev.data)
            else:
                text += "NULL"

            text += " <- (" + curr.data + ") -> "

            if curr.next:
                text += str(curr.next.data)
            else:
                text += "NULL"

            data.append(text)
            curr = curr.next

        return "[" + ", ".join(data) + "]"


if __name__ == '__main__':
    linked_list = SingleLinkedList()
    linked_list.append("C")
    linked_list.append("D")
    linked_list.append("E")
    linked_list.append("F")
    linked_list.prepend("B")
    linked_list.prepend("A")

    assert str(linked_list) == "[A, B, C, D, E, F]"

    linked_list.prepend("A")
    linked_list.prepend("C")
    linked_list.remove_duplicates()

    assert str(linked_list) == "[C, A, B, D, E, F]"

    linked_list.remove("C")
    linked_list.remove("E")

    assert str(linked_list) == "[A, B, D, F]"
    assert str(linked_list.find("B").data) == 'B'
    assert str(linked_list.find("F").data) == 'F'
    assert str(linked_list.find("A").data) == 'A'
    assert linked_list.find("J") == None

    linked_list.reverse()
    assert str(linked_list) == "[F, D, B, A]"
    linked_list.reverse()
    assert str(linked_list) == "[A, B, D, F]"

    linked_list = DoubleLinkedList()
    linked_list.append("C")
    linked_list.append("D")
    linked_list.append("E")
    linked_list.append("F")
    linked_list.prepend("B")
    linked_list.prepend("A")
    assert str(linked_list) == "[NULL <- (A) -> B, A <- (B) -> C, B <- (C) -> D, C <- (D) -> E, D <- (E) -> F, E <- (F) -> NULL]"

    linked_list.remove("E")
    linked_list.remove("A")

    assert str(linked_list) == "[NULL <- (B) -> C, B <- (C) -> D, C <- (D) -> F, D <- (F) -> NULL]"

    assert str(linked_list.find("B").data) == 'B'
    assert str(linked_list.find("F").data) == 'F'
    assert linked_list.find("J") == None

    linked_list.reverse()
    assert str(linked_list) == "[NULL <- (F) -> D, F <- (D) -> C, D <- (C) -> B, C <- (B) -> NULL]"

    linked_list.reverse()
    assert str(linked_list) == "[NULL <- (B) -> C, B <- (C) -> D, C <- (D) -> F, D <- (F) -> NULL]"