-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathlistNode.py
More file actions
106 lines (90 loc) · 2.56 KB
/
listNode.py
File metadata and controls
106 lines (90 loc) · 2.56 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
class Node(object):
def __init__(self, value=None, next=None):
self.value, self.next = value, next
class LinkedList(object):
def __init__(self, maxsize=None):
self.maxsize = maxsize
self.root = Node()
self.length = 0
self.tailnode = None
def __len__(self):
return self.length
def append(self, value):
if self.maxsize is not None and len(self) > self.maxsize:
raise Exception('Full')
node = Node(value)
tailnode = self.tailnode
if tailnode is None:
self.root.next = node
else:
tailnode.next = node
self.tailnode = node
self.length += 1
def appendleft(self, value):
headnode = self.root.next
node = Node(value)
self.root.next = node
node.next = headnode
self.length += 1
def iter_node(self):
curnode = self.root.next
while curnode is not self.tailnode:
yield curnode
curnode = curnode.next
yield curnode
def __iter__(self):
for node in self.iter_node():
yield node.value
def remove(self, value):
prevnode = self.root
curnode = self.root.next
while curnode.next is not None:
if curnode.value == value:
prevnode.next = curnode.next
del curnode
self.length -= 1
return
def find(self, value):
index = 0
for node in self.iter_node():
if node.value == value:
return index
index += 1
return -1
def popleft(self):
if self.root.next is None:
raise Exception('pop from empty LinkedList')
headnode = self.root.next
self.root.next = headnode.next
self.length -= 1
value = headnode.value
del headnode
return value
def clear(self):
for node in self.iter_node():
del node
self.root.next = None
self.length = 0
def test_linked_list():
ll = LinkedList()
ll.append(0)
ll.append(1)
ll.append(2)
assert len(ll) == 3
assert ll.find(2) == 2
assert ll.find(3) == -1
ll.remove(0)
assert len(ll) == 2
assert ll.find(0) == -1
assert list(ll) == [1, 2]
ll.appendleft(0)
assert list(ll) == [0, 1, 2]
assert len(ll) == 3
headvalue = ll.popleft()
assert headvalue == 0
assert len(ll) == 2
assert list(ll) == [1, 2]
ll.clear()
assert len(ll) == 0
if __name__ == "__main__":
test_linked_list()