python数据结构与算法：双向链表

双向链表：

###################### P4.13-P4. 双向链表 ############################ import singlelinkListclass Node(object):def __init__(self,item):self.elem = itemself.next = Noneself.prev = None# class DoublelinkList(singlelinkList): #继承class DoublelinkList(object):def __init__(self, node = None):self.__head = nodedef is_empty(self):return self.__head is Nonedef travel(self):cur = self.__headwhile cur.next != None:print(cur.elem, end=" ")cur= cur.nextprint("")def length(self):"""length of list 遍历 借助 Cursor 指针或者游标计数"""cur = self.__headcount = 0while cur != None:# cur.next = Nonecount+=1cur = cur.nextreturn countdef add(self, item):node = Node(item)node.next = self.__headself.__head = nodenode.next.prev = nodedef append(self, item):node = Node(item) # node 实例化if self.is_empty():self._head = nodeelse:cur = self.__headwhile cur.next != None:cur = cur.nextcur.next = nodenode.prev = curdef insert(self, pos, item):""":param pos 从0 开始 """if pos < 0:self.add(item)elif pos > (self.length() - 1):self.append(item)else:cur = self.__headcount =0while (count < pos):count += 1cur = cur.nextnode = Node(item)node.next = curnode.prev = cur.prevcur.prev = nodecur.prev.next = nodedef remove(self, item):cur = self.__headwhile cur != None:if cur.elem == item:if cur == self.__head:self.__head = cur.nextif cur.next:cur.next.prev = Noneelse:cur.prev.next = cur.nextif cur.next:cur.next.prev = cur.prevbreakelse:pre = curcur = cur.nextdef search(self, item):cur = self.__headwhile cur != None:if cur.elem == item:return Trueelse:cur = cur.nextreturn Falseif __name__ =="__main__":ll = DoublelinkList()print(ll.is_empty())print(ll.length())ll.append(1)print(ll.is_empty())print(ll.length())ll.append(2)# ll.add(8)ll.append(3)ll.append(4)ll.append(5)ll.append(6)ll.insert(-1, 9)ll.insert(3, 100)ll.insert(8, 1234)ll.travel()### 9 8 1 3 119 1 3 1234ll.remove(1234)ll.travel()