第一模块：5-3双向链表的原理与实践2
讲师姓名：咚咚呛
第二模块：课程内容（内容概述）代码实现：
链表节点——存放Key-Value数据
双向链表——从头部增加节点；从尾部增加节点；
删除任意节点；增加任意节点；
取出头部节点；取出尾部节点。

"""双向链表的实现"""


class Node:
    """双向链表节点"""
    def __init__(self, key, val, next=None, prev=None):
        self.key = key
        self.val = val
        self.next = next  # 下一个节点
        self.prev = prev  # 上一个节点
    
    def __str__(self):
        val = '{%d: %d}' % (self.key, self.val)
        return val


class DoubleLinkList:
    """双向链表
    def __init__（self, capacity=0xffff):
        self.capacity = capacity
        self.head = None
        self.tail = None
        self.size = 0  # 链表大小
    
    def __add_head(self, node):
        """私有方法，向头部添加新节点"""
        if not self.head:
            self.head = node
            self.tail = node
            self.head.next = None
            self.head.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):
        """私有方法，向尾部添加新节点"""
        if not sefl.tail:
            self.tail = node
            self.head = node
            self.tail.next = None
            self.tail.prev = None
        else:
            sefl.tail.next = node
            node.prev = self.tail
            self.tail = node
            self.tail.next = None
        self.size = 1
        return node
        
    def __del_tail(self):
        """私有方法，删除尾部节点"""
        if not self.tail:
            return
        node = self.tail
        if node.prev:
            self.tail = node.prev
            self.tail.next = None
        else:
            self.tail = self.head = None
        self.size -= 1
        return node
    
    def __del_head(self):
        """私有方法，删除头部节点"""
        if not self.head:
            return
        node = self.head
        if node.next:
            self.next = node.next
            self.head.prev = None
        else:
            self.tail = self.head = None
        self.size -= 1
        return node
    
    def __remove(self, node):
        """私有方法，移除任意节点"""
        # 如果node为None，默认删除尾部节点
        if not node:
            node = self.tail
        if node == self.tail:
            self.__del_tail()
        elif node == self.head:
            self.__del_head()
        else:
            node.prev.next = node.next
            node.next.prev = node.prev
            self.size -= 1
        return node
    
    def pop(self):
        """弹出结尾元素"""
        return self.__del_head()
    
    def append(self, node):
        """向结尾添加节点"""
        return self.__add_tail(node)
        
    def append_front(self.node):
        """向头部添加节点"""
        return sefl.__add_head(node)
        
    def remove(sefl, node=None):
        """删除任意节点"""
        return sefl.__remove(node)
        
    def print(self):
        """打印链表内容"""
        p = self.head
        line = ''
        while p:
            line += '%s' % p
            p = p.next
            if p:
                line += "=>"
        print(line)