python实现双链表

　　＂＂＂     创建一个结点类 ＂＂＂   class Node:     def __init__(self, value=None):         self.value = value         self.prev = None         self.next = None   ＂＂＂     创建一个双链表 ＂＂＂   class doubleLink:     def __init__(self):         self.header = None  # 初始化头结点         self.length = 0  # 链表的长度      # 判断链表是否为空     def is_empty(self):         return self.length == 0      ＂＂＂         实现向双链表添加元素的功能         有三种实现方式:         1.头插法         2.尾插法         3.向双链表的指定位置添加元素     ＂＂＂      # 1.头插法     def __add__(self, value):         node = Node(value)         if self.is_empty():             node.prev = self.header             self.header = node             self.length += 1             return         else:             node.next = self.header             self.header.prev = node             self.header = node             self.length += 1      # 2.尾插法     def append(self, value):         node = Node(value)         if self.is_empty():             self.__add__(value)         else:             cur = self.header             while cur.next is not None:                 cur = cur.next             cur.next = node             node.prev = cur         self.length += 1      # 3.向双链表的指定位置添加元素     def insert(self, index, value):         node = Node(value)         cur = self.header         if index <= 0 or index > self.length:             print(＂您输入的信息有误＂)             return ＂ ＂         if index == 1:             self.__add__(value)         for i in range(2, index):             cur = cur.next         node.next = cur.next         cur.next.prev = node         cur.next = node         node.prev = cur         self.length += 1         return value      ＂＂＂         实现插寻双链表元素的功能         有三种实现方式:         1.根据索引查询元素         2.直接查询元素         3.遍历整个双链表，并打印出所有的元素     ＂＂＂      # 1.根据索引查询元素     def __getitem__(self, index):         cur = self.header         for i in range(index - 1):             cur = cur.next         return cur.value      # 2.直接查询元素，并返回该元素的索引     def getIndex(self, value):         cur = self.header         temp = 0         while cur.next is not self.header:             if cur.value == value:                 return temp + 1             cur = cur.next             temp += 1      # 3.遍历整个双链表，并打印出所有的元素     def getAll(self):         if self.is_empty():             print(＂目前双链表中没有元素！＂)             return         cur = self.header         for i in range(self.length):             print(＂%d＂ % cur.value, end=＂ ＂)             cur = cur.next      # 4.查询某个元素的后继节点     def getItem(self, value):         cur = self.header         temp = 0         while cur.next is not self.header:             if cur.value == value:                 if cur.next is not None:                     return cur.next.value                 else:                     return -1             cur = cur.next             temp += 1      # 5.查询某个元素的前驱节点     def getPrevItem(self, value):         cur = self.header         temp = 0         while cur.next is not self.header:             if cur.value == value:                 if cur.prev is not None:                     return cur.prev.value                 else:                     return -1             cur = cur.next             temp += 1      ＂＂＂         实现修改指定位置元素的功能     ＂＂＂      def __setitem__(self, index, value):         cur = self.header         for i in range(index - 1):             cur = cur.next         cur.value = value         return value      ＂＂＂         实现删除双链表元素的功能             ＂＂＂     # 直接删除元素     def __delete__(self, value):         cur = self.header         if self.getIndex(value) == 1:             self.header = cur.next             self.length -= 1         elif self.getIndex(value) != 1:             while self.getIndex(value) != self.length:                 cur = cur.next             cur=None             self.length -= 1         else:             while cur.value != value:                 cur = cur.next             cur.prev.next = cur.next             cur.next.prev = cur.prev             self.length -= 1   if __name__ == ＂__main__＂:     s = doubleLink()     s.__add__(12)     s.__add__(13)     s.__add__(14)     s.__add__(15)     s.append(22)     s.getAll()     print(＂ 第%d个位置的元素是%d.＂ % (1, s.__getitem__(1)))     print(＂ 元素%d在双链表的第%d个位置＂ % (14, s.getIndex(14)))     print(＂获取元素%d的后继节点%d＂ % (12, s.getItem(12)))     print(＂获取元素%d的前驱节点%d＂ % (13, s.getPrevItem(13)))     print(＂在第%d个位置插入元素%d:＂ % (2, s.insert(2, 45)))     s.getAll()     print(＂ 将第%d个位置的元素修改为%d:＂ % (1, s.__setitem__(1, 900)))     s.getAll()     print(＂ 删除第%d个元素:＂ % 5)     s.__delitem__(5)     print(＂ 删除元素22:＂)     s.__delete__(22)     s.getAll()