1. class Node(object):
    2.     """单个节点 """
    3.     def __init__(self, elem):
    4.         # 该节点存放的数据
    5.         self.elem = elem
    6.         # 指向下个节点的标识
    7.         self.next = None
    8.         self.prev = None
    11. class DoubleLinkList(object):
    12.     """单链表"""
    13.     def __init__(self, node=None):
    14.         self.__head = node
    16.     def is_empty(self):
    17.         """判断是否为空"""
    18.         return self.__head is None
    20.     def length(self):
    21.         """求长度"""
    22.         # cur游标，用来移动遍历节点
    23.         cur = self.__head
    24.         # count记录数量
    25.         count = 0
    26.         while cur is not None:
    27.             count += 1
    28.             cur = cur.next
    29.         return count
    31.     def travel(self):
    32.         """遍历"""
    33.         cur = self.__head
    34.         while cur is not None:
    35.             print(cur.elem, end=" ")
    36.             cur = cur.next
    38.     def add(self, item):
    39.         """头部添加元素，头插法"""
    40.         node = Node(item)
    41.         node.next = self.__head
    42.         self.__head = node
    43.         node.next.prev = node
    45.     def append(self, item):
    46.         """尾部添加元素，尾插发"""
    47.         node = Node(item)
    48.         if self.is_empty():
    49.             self.__head = node
    50.         else:
    51.             cur = self.__head
    52.             while cur.next is not None:
    53.                 cur = cur.next
    54.             cur.next = node
    55.             node.prev = cur
    57.     def insert(self, pos, item):
    58.         """指定位置添加元素
    59.         :param item:节点数据
    60.         :param pos:插入位置，从0开始
    61.         """
    62.         if pos <= 0:
    63.             self.add(item)
    64.         elif pos > (self.length() - 1):
    65.             self.append(item)
    66.         else:
    67.             node = Node(item)
    68.             cur = self.__head
    69.             count = 0
    70.             while count < pos:
    71.                 cur = cur.next
    72.                 count += 1
    73.             # 当循环退出后，cur指向pos-1位置
    74.             node.next = cur
    75.             node.prev = cur.prev
    76.             node.prev.next = node
    77.             node.next.prev = node
    79.     def remove(self, item):
    80.         """删除指定元素"""
    81.         cur = self.__head
    82.         while cur:
    83.             if cur.elem == item:
    84.                 # 先判断此节点是否是头节点
    85.                 if cur == self.__head:
    86.                     self.__head == cur.next
    87.                     if cur.next:
    88.                         # 判断链表是否只有一个节点
    89.                         cur.next.prev = None
    90.                 else:
    91.                     cur.prev.next = cur.next
    92.                     if cur.next:
    93.                         cur.next.prev = cur.prev
    94.                 return True
    95.             else:
    96.                 cur = cur.next
    97.         return False
    99.     def search(self, item):
    100.         """查看节点是否存在"""
    101.         cur = self.__head
    102.         while cur is not None:
    103.             if cur.elem == item:
    104.                 return True
    105.             else:
    106.                 cur = cur.next
    107.         return False