基於python實現雙向連結串列

class Node:

    def __init__(self, key, value):
        """
        初始化方法
        :param key:
        :param value:
        """
        self.key = key
        self.value = value
        self.prev = None
        self.next = None

    def __str__(self):
        val = '{%s: %s}' % (self.key, self.value)
        return val

    def __repr__(self):
        val = '{%s: %s}' % (self.key, self.value)
        return val

class DoubleLinkedList:

    def __init__(self, capacity=0xffffffff):
        """
        雙向連結串列
        :param capacity: 連結串列容量 初始化為int的最大值2^32-1
        :return:
        """
        self.capacity = capacity
        self.size = 0
        self.head = None
        self.tail = None

    def __add_head(self, node):
        """
        向連結串列頭部新增節點
            頭部節點不存在 新新增節點為頭部和尾部節點
            頭部節點已存在 新新增的節點為新的頭部節點
        :param node: 要新增的節點
        :return: 已新增的節點
        """
        # 頭部節點為空
        if not self.head:
            self.head = node
            self.tail = node
            self.head.next = None
            self.tail.prev = None
        # 頭部節點不為空
        else:
            node.next = self.head
            self.head.prev = node
            self.head = node
            self.head.prev = None
        self.size += 1

        return node

    def __add_tail(self, node):
        """
        向連結串列尾部新增節點
            尾部節點不存在 新新增的節點為頭部和尾部節點
            尾部節點已存在 新新增的節點為新的尾部節點
        :param node: 新增的節點
        :return: 已新增的節點
        """
        # 尾部節點為空
        if not self.tail:
            self.tail = node
            self.head = node
            self.head.next = None
            self.tail.prev = None
        # 尾部節點不為空
        else:
            node.prev = self.tail
            self.tail.next = node
            self.tail = node
            self.tail.next = None
        self.size += 1

        return node

    def __remove_head(self):
        """
        刪除頭部節點
            頭部節點不存在 返回None
            頭部節點已存在 判斷連結串列節點數量 刪除頭部節點
        :return: 頭部節點
        """
        # 頭部節點不存在
        if not self.head:
            return None

        # 連結串列至少存在兩個節點
        head = self.head
        if head.next:
            head.next.prev = None
            self.head = head.next
        # 只存在頭部節點
        else:
            self.head = self.tail = None
        self.size -= 1

        return head

    def __remove_tail(self):
        """
        刪除尾部節點
            尾部節點不存在 返回None
            尾部節點已存在 判斷連結串列節點數量 刪除尾部節點
        :return: 尾部節點
        """
        # 尾部節點不存在
        if not self.tail:
            return None

        # 連結串列至少存在兩個節點
        tail = self.tail
        if tail.prev:
            tail.prev.next = None
            self.tail = tail.prev
        # 只存在尾部節點
        else:
            self.head = self.tail = None
        self.size -= 1

        return tail

    def __remove(self, node):
        """
        刪除任意節點
            被刪除的節點不存在 預設刪除尾部節點
            刪除頭部節點
            刪除尾部節點
            刪除其他節點
        :param node: 被刪除的節點
        :return: 被刪除的節點
        """
        # 被刪除的節點不存在
        if not node:
            node = self.tail

        # 刪除的是頭部節點
        if node == self.head:
            self.__remove_head()
        # 刪除的是尾部節點
        elif node == self.tail:
            self.__remove_tail()
        # 刪除的既不是頭部也不是尾部節點
        else:
            node.next.prev = node.prev
            node.prev.next = node.next
            self.size -= 1

        return node

    def pop(self):
        """
        彈出頭部節點
        :return: 頭部節點
        """
        return self.__remove_head()

    def append(self, node):
        """
        新增尾部節點
        :param node: 待追加的節點
        :return: 尾部節點
        """
        return self.__add_tail(node)

    def append_front(self, node):
        """
        新增頭部節點
        :param node: 待新增的節點
        :return: 已新增的節點
        """
        return self.__add_head(node)

    def remove(self, node=None):
        """
        刪除任意節點
        :param node: 待刪除的節點
        :return: 已刪除的節點
        """
        return self.__remove(node)

    def print(self):
        """
        列印當前連結串列
        :return:
        """
        node = self.head
        line = ''
        while node:
            line += '%s' % node
            node = node.next
            if node:
                line += '=>'
        print(line)

if __name__ == '__main__':
    double_linked_list = DoubleLinkedList(10)
    nodes = []
    # 構建十個節點的雙向列表
    for i in range(10):
        node_item = Node(i, i)
        nodes.append(node_item)

    double_linked_list.append(nodes[0])
    double_linked_list.print()
    double_linked_list.append(nodes[1])
    double_linked_list.print()
    double_linked_list.pop()
    double_linked_list.print()
    double_linked_list.append_front(nodes[2])
    double_linked_list.print()
    double_linked_list.append(nodes[3])
    double_linked_list.print()
    double_linked_list.remove(nodes[3])
    double_linked_list.print()
    double_linked_list.remove()
    double_linked_list.print()