/
doublyLinkedList.py
192 lines (163 loc) · 4.35 KB
/
doublyLinkedList.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
# -*- coding: utf-8 -*-
__author__ = 'xiaowang'
__date__ = '19/11/15'
class Node(object):
def __init__(self, data=None):
self.data = data
self.pre = None
self.next = None
class DoublyLinkedList(object):
"""初始化双向链表"""
def __init__(self):
"""
设置头尾，操作比较容易
头－－（next）－－》尾
尾－－（pre）－－》头
:return:
"""
head = Node()
tail = Node()
self.head = head
self.tail = tail
self.head.next = self.tail
self.tail.pre = self.head
"""追加节点"""
def append(self, data):
"""
:param data:
:return:
"""
node = Node(data)
pre = self.tail.pre
pre.next = node
node.pre = pre
self.tail.pre = node
node.next = self.tail
return node
"""插入节点"""
def insert(self, index, data):
"""
因为加了头尾节点所以获取节点node就一定存在node.next 和 node.pre
:param index:
:param data:
:return:
"""
length = len(self)
if abs(index + 1) > length:
return False
index = index if index >= 0 else index + 1 + length
next_node = self.get(index)
if next_node:
node = Node(data)
pre_node = next_node.pre
pre_node.next = node
node.pre = pre_node
node.next = next_node
next_node.pre = node
return node
"""删除节点"""
def delete(self, index):
node = self.get(index)
if node:
node.pre.next = node.next
node.next.pre = node.pre
return True
return False
"""反转链表"""
def __reversed__(self):
"""
1.node.next --> node.pre
node.pre --> node.next
2.head.next --> None
tail.pre --> None
3.head-->tail
tail-->head
:return:
"""
pre_head = self.head
tail = self.tail
def reverse(pre_node, node):
if node:
next_node = node.next
node.next = pre_node
pre_node.pre = node
if pre_node is self.head:
pre_node.next = None
if node is self.tail:
node.pre = None
return reverse(node, next_node)
else:
self.head = tail
self.tail = pre_head
return reverse(self.head, self.head.next)
"""获取链表长度"""
def __len__(self):
length = 0
node = self.head
while node.next != self.tail:
length += 1
node = node.next
return length
"""获取节点"""
def get(self, index):
"""
获取第index个值，若index>0正向获取else 反向获取
:param index:
:return:
"""
length = len(self)
index = index if index >= 0 else length + index
if index >= length or index < 0: return None
node = self.head.next
while index:
node = node.next
index -= 1
return node
"""设置节点"""
def set(self, index, data):
node = self.get(index)
if node:
node.data = data
return node
"""清空链表"""
def clear(self):
self.head.next = self.tail
self.tail.pre = self.head
"""打印链表"""
def show(self, order=1):
"""
输出双向链表
:param order 1－－》正向；－1－－》反向 :
:return: None
"""
if order >= 0:
node = self.head.next
while node is not self.tail:
print(node.data, end=" ")
node = node.next
else:
node = self.tail.pre
while node is not self.head:
print(node.data, end=" ")
node = node.pre
print()
if __name__ == '__main__':
ls = DoublyLinkedList()
print(len(ls))
ls.append(1)
ls.append(2)
ls.append(3)
ls.append(4)
ls.show(1)
print(len(ls))
print(ls.get(0).data)
ls.set(0, 10)
ls.show()
ls.insert(1, -2)
ls.show()
ls.delete(-2)
ls.show()
reversed(ls)
ls.show()
ls.clear()
ls.show()