python 双向链表
1 # -*- coding: utf-8 -*-
2 # @author: Tele
3 # @Time : 2019/04/23 下午 3:19
4 # 双向链表的实现
5 # 双向链表的每个节点包含三个部分:上一个节点的链接区,数据区,下一个节点的链接区
6 # 通过双向链表中的任意节点都能访问全部节点
7 class DoubleNode: 8 def __init__(self, data): 9 self.data = data 10 self.prev = None 11 self.next = None 12
13
14 class DoubleLinkedList: 15 def __init__(self, data=None): 16 node = DoubleNode(data) 17 self.__head = node if node.data else None 18
19 def is_empty(self): 20 return self.__head == None 21
22 def length(self): 23 count = 0 24 cur = self.__head
25 while cur: 26 count += 1
27 cur = cur.next 28 return count 29
30 # 头部添加元素
31 def add(self, data): 32 node = DoubleNode(data) 33 # 如果列表是空的,也可以用is_empty
34 if not self.__head: 35 self.__head = node 36 else: 37 self.__head.prev = node 38 node.next = self.__head
39 self.__head = node 40
41 # 尾部添加元素
42 def append(self, data): 43 node = DoubleNode(data) 44 if not self.__head: 45 self.__head = node 46 else: 47 cur = self.__head
48 # 最后一个节点的next为None
49 while cur.next: 50 cur = cur.next 51 cur.next = node 52 node.prev = cur 53
54 # 指定位置插入
55 def insert(self, pos, data): 56 node = DoubleNode(data) 57 cur = self.__head
58 count = 0 59 if self.length() >= pos >= 0: 60 while cur: 61 if count + 1 == pos: 62 node.next = cur.next 63 node.prev = cur 64 cur.next = node 65 break
66 # pos为0
67 elif count == pos: 68 self.add(data) 69 break
70 count += 1
71 cur = cur.next 72 elif pos < 0: 73 self.add(data) 74 else: 75 self.append(data) 76 # 如果列表中插入时没有元素
77 if not self.__head: 78 self.append(data) 79
80 # 遍历
81 def travel(self): 82 cur = self.__head
83 while cur: 84 print(cur.data) 85 cur = cur.next 86
87 def remove(self, data): 88 if self.is_empty(): 89 return
90 count = 0 91 cur = self.__head
92 while cur: 93 # 头节点
94 if cur.data == data: 95 self.__head = cur.next 96 break
97 elif cur.next.data == data: 98 if cur.next.next: 99 cur.next = cur.next.next 100 cur.next.next.prev = cur 101 # 尾节点
102 else: 103 cur.next = None 104 break
105 count += 1
106 cur = cur.next 107
108 # 移除出现的第一个元素
109 # def remove(self, data):
110 # node = self.__find(data)
111 # count = 0
112 # cur = self.__head
113 # while cur:
114 # # 如果要移除的元素是头节点
115 # if cur.data == node.data:
116 # self.__head = cur.next
117 # break
118 # elif cur.next.data == node.data:
119 # cur.next = node.next
120 # # 如果node不是最后一个节点
121 # if node.next:
122 # node.next.prev = cur
123 # break
124 # count += 1
125 # cur = cur.next
126 # 私有方法,用于查找节点
127 # def __find(self, data):
128 # index = -1
129 # cur = self.__head
130 # count = 0
131 # node = DoubleNode(data)
132 # while cur:
133 # if cur.data == data:
134 # index = count
135 # node.next = cur.next
136 # break
137 # count += 1
138 # cur = cur.next
139 # return node
140
141 # 查找,找不到返回-1,找到则返回索引
142 def search(self, data): 143 index = -1
144 cur = self.__head
145 count = 0 146 while cur: 147 if cur.data == data: 148 index = count 149 break
150 count += 1
151 cur = cur.next 152 return index 153
154
155 def main(): 156 dll = DoubleLinkedList() 157 print(dll.is_empty()) 158 print(dll.length()) 159 dll.add(0) 160 dll.add(1) 161 dll.append(1) 162 dll.append(2) 163 print(dll.is_empty()) 164 print(dll.length()) 165 # print("*" * 50)
166 # dll.travel()
167 print("*" * 50) 168 dll.insert(-1, 10000) 169 print(dll.search(10000)) # 0
170 dll.travel() 171 dll.remove(1) 172 print("*" * 50) 173 dll.travel() 174
175
176 if __name__ == '__main__': 177 main()
更多精彩
