'''

 双向链表包含第一个和最后一个的链接元素。

 每个链接都有一个数据字段和两个称为next和prev的链接字段。

 每个链接都使用其下一个链接与其下一个链接链接。

 每个链接都使用其上一个链接与之前的链接链接。

 最后一个链接将链接作为空来标记列表的结尾。

 '''

 # 创建节点

 class Node():

     def __init__(self, data):

         self.data = data

         self.next = None

         self.prev = None

 # 创建双链表

 class doubly_linked_list():

     def __init__(self):

         self.head = None

     # 遍历链表

     def listprint(self, node):

         while node:

             print(node.data)

             # last = node

             node = node.next

     # 在头部添加新节点

     def push(self, NewVal):

         NewNode = Node(NewVal)

         NewNode.next = self.head

         if self.head:

             self.head.prev = NewNode

         self.head = NewNode

     # 在中间任意位置插入节点

     def insert(self, prev_node, NewVal):

         if prev_node is None:

             return

         NewNode = Node(NewVal)

         NewNode.next = prev_node.next

         prev_node.next = NewNode

         NewNode.prev = prev_node

         if NewNode.next:

             NewNode.next.prev = NewNode

     # 在最后追加节点

     def append(self, NewVal):

         NewNode = Node(NewVal)

         NewNode.next = None

         if self.head is None:

             NewNode.prev = None

             self.head = NewNode

             return

         last = self.head

         while last.next:

             last = last.next

         last.next = NewNode

         NewNode.prev = last

         return

 dllist = doubly_linked_list()

 dllist.push(12)

 dllist.push(8)

 dllist.append(20)

 dllist.push(6)

 dllist.insert(dllist.head.next, 10)

 dllist.append(30)

 dllist.listprint(dllist.head)

 # 结果 6 8 10 12 20 30

 # 根据结果可知push是依次加到最前，无论append在什么位置，都是在最后追加