1 '''
  2     创建一个结点类
  3 '''
  4 
  5 
  6 class Node:
  7     def __init__(self, value=None):
  8         self.value = value
  9         self.prev = None
 10         self.next = None
 11 
 12 
 13 '''
 14     创建一个双链表
 15 '''
 16 
 17 
 18 class doubleLink:
 19     def __init__(self):
 20         self.header = None  # 初始化头结点
 21         self.length = 0  # 链表的长度
 22 
 23     # 判断链表是否为空
 24     def is_empty(self):
 25         return self.length == 0
 26 
 27     '''
 28         实现向双链表添加元素的功能
 29         有三种实现方式:
 30         1.头插法
 31         2.尾插法
 32         3.向双链表的指定位置添加元素
 33     '''
 34 
 35     # 1.头插法
 36     def __add__(self, value):
 37         node = Node(value)
 38         if self.is_empty():
 39             node.prev = self.header
 40             self.header = node
 41             self.length += 1
 42             return
 43         else:
 44             node.next = self.header
 45             self.header.prev = node
 46             self.header = node
 47             self.length += 1
 48 
 49     # 2.尾插法
 50     def append(self, value):
 51         node = Node(value)
 52         if self.is_empty():
 53             self.__add__(value)
 54         else:
 55             cur = self.header
 56             while cur.next is not None:
 57                 cur = cur.next
 58             cur.next = node
 59             node.prev = cur
 60         self.length += 1
 61 
 62     # 3.向双链表的指定位置添加元素
 63     def insert(self, index, value):
 64         node = Node(value)
 65         cur = self.header
 66         if index <= 0 or index > self.length:
 67             print('您输入的信息有误')
 68             return ' '
 69         if index == 1:
 70             self.__add__(value)
 71         for i in range(2, index):
 72             cur = cur.next
 73         node.next = cur.next
 74         cur.next.prev = node
 75         cur.next = node
 76         node.prev = cur
 77         self.length += 1
 78         return value
 79 
 80     '''
 81         实现插寻双链表元素的功能
 82         有三种实现方式:
 83         1.根据索引查询元素
 84         2.直接查询元素
 85         3.遍历整个双链表，并打印出所有的元素
 86     '''
 87 
 88     # 1.根据索引查询元素
 89     def __getitem__(self, index):
 90         cur = self.header
 91         for i in range(index - 1):
 92             cur = cur.next
 93         return cur.value
 94 
 95     # 2.直接查询元素，并返回该元素的索引
 96     def getIndex(self, value):
 97         cur = self.header
 98         temp = 0
 99         while cur.next is not self.header:
100             if cur.value == value:
101                 return temp + 1
102             cur = cur.next
103             temp += 1
104 
105     # 3.遍历整个双链表，并打印出所有的元素
106     def getAll(self):
107         if self.is_empty():
108             print('目前双链表中没有元素！')
109             return
110         cur = self.header
111         for i in range(self.length):
112             print('%d' % cur.value, end=' ')
113             cur = cur.next
114 
115     # 4.查询某个元素的后继节点
116     def getItem(self, value):
117         cur = self.header
118         temp = 0
119         while cur.next is not self.header:
120             if cur.value == value:
121                 if cur.next is not None:
122                     return cur.next.value
123                 else:
124                     return -1
125             cur = cur.next
126             temp += 1
127 
128     # 5.查询某个元素的前驱节点
129     def getPrevItem(self, value):
130         cur = self.header
131         temp = 0
132         while cur.next is not self.header:
133             if cur.value == value:
134                 if cur.prev is not None:
135                     return cur.prev.value
136                 else:
137                     return -1
138             cur = cur.next
139             temp += 1
140 
141     '''
142         实现修改指定位置元素的功能
143     '''
144 
145     def __setitem__(self, index, value):
146         cur = self.header
147         for i in range(index - 1):
148             cur = cur.next
149         cur.value = value
150         return value
151 
152     '''
153         实现删除双链表元素的功能
154        
155     '''
156     # 直接删除元素
157     def __delete__(self, value):
158         cur = self.header
159         if self.getIndex(value) == 1:
160             self.header = cur.next
161             self.length -= 1
162         elif self.getIndex(value) != 1:
163             while self.getIndex(value) != self.length:
164                 cur = cur.next
165             cur=None
166             self.length -= 1
167         else:
168             while cur.value != value:
169                 cur = cur.next
170             cur.prev.next = cur.next
171             cur.next.prev = cur.prev
172             self.length -= 1
173 
174 
175 if __name__ == '__main__':
176     s = doubleLink()
177     s.__add__(12)
178     s.__add__(13)
179     s.__add__(14)
180     s.__add__(15)
181     s.append(22)
182     s.getAll()
183     print('\n第%d个位置的元素是%d.' % (1, s.__getitem__(1)))
184     print('\n元素%d在双链表的第%d个位置' % (14, s.getIndex(14)))
185     print('获取元素%d的后继节点%d' % (12, s.getItem(12)))
186     print('获取元素%d的前驱节点%d' % (13, s.getPrevItem(13)))
187     print('在第%d个位置插入元素%d:' % (2, s.insert(2, 45)))
188     s.getAll()
189     print('\n将第%d个位置的元素修改为%d:' % (1, s.__setitem__(1, 900)))
190     s.getAll()
191     print('\n删除第%d个元素:' % 5)
192     s.__delitem__(5)
193     print('\n删除元素22:')
194     s.__delete__(22)
195     s.getAll()