-
Notifications
You must be signed in to change notification settings - Fork 4
Expand file tree
/
Copy pathdouble_link_list.py
More file actions
executable file
·144 lines (116 loc) · 3.64 KB
/
Copy pathdouble_link_list.py
File metadata and controls
executable file
·144 lines (116 loc) · 3.64 KB
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
#!/usr/bin/env python
# -*- coding:utf-8 -*-
__author__ = 'MFC'
__time__ = '2020/6/19 17:37'
"""
手撕循环双端链表
现理解 循环双端链表 的概念，再来实现
首尾循环相连
https://www.bilibili.com/video/BV1ZE411P7ov?p=7
practice：
https://leetcode.com/problems/lru-cache/description/
"""
class Node:
def __init__(self, value=None, prev=None, next=None):
self.value, self.prev, self.next = value, prev, next
class CircualDoubleLinkedList:
def __init__(self, maxsize=None):
self.maxsize = maxsize
node = Node()
node.next, node.prev = node, node
self.root = node
self.length = 0
def __len__(self):
return self.length
def headnode(self):
"""
获取root节点的下一个节点
:return:
"""
return self.root.next
def tailnode(self):
"""
:return:
"""
return self.root.prev
def append(self, value):
if self.maxsize is not None and len(self) > self.maxsize:
raise Exception("full")
node = Node(value=value)
tailnode = self.tailnode()
tailnode.next = node
node.prev = tailnode
node.next = self.root
self.root.prev = node
self.length += 1
def appendleft(self, value):
if self.maxsize is not None and len(self) > self.maxsize:
raise Exception("full")
node = Node(value=value)
# 如果为空，则自己指向自己
if self.root.next is self.root:
node.next = self.root
node.prev = self.root
self.root.next = node
self.root.prev = node
else:
# 不为空，则把当前节点指向 头节点
node.prev = self.root
headnode = self.root.next
node.next = headnode
headnode.prev = node
self.root.next = node
self.length += 1
def remove(self, node): # O(1), because node isn't a value, it is a node.
# 如果是根节点，什么都不做
if node is self.root:
return
else:
# 如果是非根节点
node.prev.next = node.next
node.next.prev = node.prev
self.length -= 1
return node
def iter_node(self):
if self.root.next is self.root:
return
curnode = self.root.next
while curnode.next is not self.root: # 如果不是tailnode
yield curnode
curnode = curnode.next
yield curnode
def __iter__(self):
for node in self.iter_node():
yield node.value
def iter_node_reverse(self):
"""
实现反向遍历
:return:
"""
if self.root.prev is self.root:
return
curnode = self.root.prev # tailnode
while curnode.prev is not self.root:
yield curnode
curnode = curnode.prev
yield curnode
# 开始写最复杂的步骤，单元测试
def test_double_link_list():
cdll = CircualDoubleLinkedList()
assert len(cdll) == 0
cdll.append(0)
cdll.append(1)
cdll.append(2)
assert list(cdll) == [0,1,2]
# 测试遍历
assert [node.value for node in cdll.iter_node()] == [0,1,2]
# 测试反向遍历
assert [node.value for node in cdll.iter_node_reverse()] == [2,1,0]
headnode = cdll.headnode()
assert headnode.value == 0
cdll.remove(headnode) # O(1) , remove node
assert len(cdll) == 2
assert [node.value for node in cdll.iter_node()] == [1,2]
cdll.appendleft(0)
assert [node.value for node in cdll.iter_node()] == [0, 1, 2]
# Unit tset finished