在单链表之后，一种更复杂的链表是“双向链表”或“双面链表”。每个节点有两个链接：一个指向前一个节点（前驱），当此节点为第一个节点时，前驱指向None；另一个指向下一个节点（后继），当此节点最后一个节点时，后继指向None。
【示例】节点实现
双向链表的 is_empy、search、length、travel 操作与单向链表相同，由于双链表的双面性，故在 add、append、insert、remove 操作中有所区别。
【示例】双向链表实现
#定义节点的类class Node(object): def __init__(self, elem): #定义元素值 self.elem = elem #定义后继 self.next = None #定义前驱 self.prev = None#定义单向链表class DoubleLinkList: def __init__(self, node=None): if node != None: headNode = Node(node) self.__head = headNode else: self.__head = node #头部添加元素 def add(self, item): node = Node(item) if self.is_empty(): self.__head = node else: #node的后继指向头节点 node.next = self.__head #头节点的前驱指向node self.__head.prev = node #__head私有属性指向node self.__head = node #在任意位置插入元素 def insert(self, pos, item): if pos <= 0: self.add(item) elif pos > (self.length()-1): self.append(item) else: node = Node(item) curNode = self.__head count = 0 while count < (pos-1): count += 1 curNode = curNode.next #将node节点的前驱指向当前节点 node.prev = curNode #将node节点的后继指向当前节点的下一个节点 node.next = curNode.next #将当前节点的下一个节点的前驱指向node curNode.next.prev = node #将当前节点的后继指向node curNode.next = node #尾部追加元素 def append(self, item): node = Node(item) if node == None: self.__head = node else: curNode = self.__head while curNode.next != None: curNode = curNode.next curNode.next = node #将node节点前驱指向当前节点 node.prev = curNode #删除节点 def remove(self, item): curNode = self.__head while curNode != None: if curNode.elem == item: #判断是否是头节点 if curNode == self.__head: #是头节点 self.__head = curNode.next #判断当前节点是否只有一个节点，若只有一个节点，则不需要移动下一个节点的前驱 if curNode.next: curNode.next.prev = None else: #删除节点 curNode.prev.next = curNode.next #判断当前节点是否为最后一个节点，若为最后一个节点，最后一个节点的下一个节点指向None if curNode.next: curNode.next.prev = curNode.prev break else: curNode = curNode.next #判断链表长度 def length(self): curNode = self.__head count = 0 while curNode != None: count += 1 curNode = curNode.next return count #判断是否为空 def is_empty(self): return self.__head == None #遍历链表 def travel(self): curNode = self.__head while curNode != None: print(curNode.elem, end='t') curNode = curNode.next print('') #元素查找 def search(self, item): curNode = self.__head while curNode != None: if curNode.elem == item: return True curNode = curNode.next return Falseif __name__=='__main__': doubleLinkList = DoubleLinkList() doubleLinkList.add(11) doubleLinkList.add(22) doubleLinkList.travel() print('------追加------') doubleLinkList.append(100) doubleLinkList.append(200) doubleLinkList.travel() print('---------指定位置插入--------') doubleLinkList.insert(-1, 44) doubleLinkList.travel() doubleLinkList.insert(2, 33) doubleLinkList.travel() print('---------删除节点--------') doubleLinkList.remove(44) doubleLinkList.travel() doubleLinkList.remove(200) doubleLinkList.travel() doubleLinkList.remove(33) doubleLinkList.travel() print('------链表长度-------') print(doubleLinkList.length()) print('------元素查找-------') print('查找节点22:',doubleLinkList.search(22))【示例】双链表实现_执行结果