Answers for "python ddl implementation"

python ddl implementation

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


class DLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None
        self.probe = None
        self.items = 0

    def __repr__(self):
        nodes = []
        cur_node = self.head
        while cur_node:
            if cur_node is self.head:
                nodes.append(f"[Head: {cur_node.data}]")
            elif cur_node.next is None:
                nodes.append(f"[Tail: {cur_node.data}]")
            else:
                nodes.append(f"[{cur_node.data}]")

            cur_node = cur_node.next
        return '->'.join(nodes)

    def rev_traversal(self):
        nodes = []
        cur_node = self.tail
        while cur_node:
            if cur_node is self.head:
                nodes.append(f"[Head: {cur_node.data}]")
            elif cur_node.next is None:
                nodes.append(f"[Tail: {cur_node.data}]")
            else:
                nodes.append(f"[{cur_node.data}]")

            cur_node = cur_node.prev
        return '->'.join(nodes)

    def add_value(self, value):
        new_node = DListNode(value)
        if self.head is None:
            self.head = new_node
            self.tail = self.head
            self.items += 1
        elif value < self.head.data:
            new_node.next = self.head
            self.head.prev = new_node
            self.head = new_node
            self.items += 1
        elif value > self.tail.data:
            new_node.prev = self.tail
            self.tail.next = new_node
            self.tail = new_node
            self.items += 1
        else:
            node = self.head
            while node is not None and node.data < value:
                node = node.next
            new_node.next = node
            new_node.prev = node.prev
            node.prev.next = new_node
            node.prev = new_node

    def search(self, target):
        if self.head is None:
            return False
        elif self.probe is None:
            self.probe = self.head
        if target < self.probe.data:
            while self.probe is not None and target <= self.probe.data:
                if target == self.probe.data:
                    return True
                else:
                    self.probe = self.probe.prev
        else:
            while self.probe is not None and target >= self.probe.data:
                if target == self.probe.data:
                    return True
                else:
                    self.probe = self.probe.next
        return False

    def insert(self, index, value):
        assert not index > self.items, "index out of range"
        if index == 0:
            new_node = DListNode(value)
            new_node.next = self.head
            self.head.prev = new_node
            self.head = new_node
            self.items += 1
        else:
            new_node = DListNode(value)
            cur_node = self.head
            for x in range(index-1):
                cur_node = cur_node.next

            new_node.next = cur_node.next
            cur_node.next.prev = new_node
            cur_node.next = new_node
            new_node.prev = cur_node

    def remove_at(self, index):
        assert index < self.items, "index out of range"
        if self.items > 1 and index == 0:
            self.head.next.prev = None
            self.head = self.head.next
            self.items -= 1

        elif self.items == 1 and index == 0:
            self.head = None
            self.tail = None
            self.items -= 1
        elif index == self.items - 1:
            self.tail = self.tail.prev
            self.tail.next = None
            self.items -= 1
        else:
            pred_node = None
            cur_node = self.head
            for x in range(index):
                pred_node = cur_node
                cur_node = cur_node.next

            pred_node.next = cur_node.next
            cur_node.next.prev = pred_node
            self.items -= 1

    def append(self, value):
        new_node = DListNode(value)
        cur_node = self.head
        if cur_node is None:
            self.head = new_node
            self.tail = self.head
            self.items += 1
        else:
            while cur_node.next is not None:
                cur_node = cur_node.next
            cur_node.next = new_node
            new_node.prev = cur_node
            self.items += 1

    def prepend(self, value):
        new_node = DListNode(value)
        new_node.next = self.head
        self.head.prev = new_node
        self.head = new_node
        self.items += 1