-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathlinkedList.py
179 lines (137 loc) · 4.32 KB
/
linkedList.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
class Node:
def __init__(self, val = None, nextNode = None):
self.val = val
self.nextNode = nextNode
class LinkedList:
def __init__(self, head: Node = None) -> None:
self.head = head
def get(self, index: int) -> int:
i = 0
cur = self.head
while cur:
if i < index:
cur = cur.nextNode
i += 1
else:
return cur.val
return -1
def insertHead(self, val: int) -> None:
newHead = Node(val = val, nextNode = self.head)
self.head = newHead
def insertTail(self, val: int) -> None:
previous = cur = self.head
if cur == None:
self.head = Node(val)
return
while cur:
previous = cur
cur = cur.nextNode
previous.nextNode = Node(val = val, nextNode = None)
def NodesFromList(self, values: list[int]) -> None:
if not self.head:
self.head = Node(values[0])
cur = self.head
while cur.nextNode:
cur = cur.nextNode
for val in values[1:]:
newNode = Node(val)
cur.nextNode = newNode
cur = newNode
def remove(self, index):
if index < 0:
print("Index out of range")
return False
if index == 0:
if self.head:
self.head = self.head.nextNode
return True
else:
print("List is empty")
return False
current = self.head
prev = None
count = 0
while current and count != index:
prev = current
current = current.nextNode
count += 1
if current is None:
print("Index out of range")
return False
prev.nextNode = current.nextNode
return True
def getValues(self) -> list[int]:
values = []
cur = self.head
while cur:
values.append(cur.val)
cur = cur.nextNode
return values
def reverseList(self):
prev = None
current = self.head
while current:
next_node = current.nextNode
current.nextNode = prev
prev = current
current = next_node
self.head = prev
#########################################################
print()
#[empty LinkdedList, [insertHead, 1], [insertTail, 2],[ insertHead, 0], [remove, 1]]
testList = LinkedList()
assert testList.getValues() == []
testList.insertHead(1)
assert testList.getValues() == [1]
testList.insertTail(2)
assert testList.getValues() == [1, 2]
testList.insertHead(0)
assert testList.getValues() == [0, 1, 2]
testList.remove(1)
assert testList.getValues() == [0, 2]
print()
#########################################################
# input [empty LinkdedList, "insertHead", 1, "remove", 0]
testList = LinkedList()
assert testList.getValues() == []
testList.insertHead(1)
assert testList.getValues() == [1]
testList.remove(0)
assert testList.getValues() == []
#########################################################
#[empty LinkdedList [insertHead, 1], [insertTail, 2],[ insertHead, 0], [remove, 2], [remove, 0]]
print()
testList = LinkedList()
assert testList.getValues() == []
testList.insertHead(1)
assert testList.getValues() == [1]
testList.insertTail(2)
assert testList.getValues() == [1, 2]
testList.insertHead(0)
assert testList.getValues() == [0, 1, 2]
testList.remove(2)
assert testList.getValues() == [0, 1]
testList.remove(0)
assert testList.getValues() == [1]
print()
#########################################################
#[empty LinkedList, "insertTail", 1, "insertTail", 2, "get", 1, "remove", 1, "insertTail", 2, "get", 1, "get", 0]
testList = LinkedList()
assert testList.getValues() == []
testList.insertTail(1)
assert testList.getValues() == [1]
testList.insertTail(2)
assert testList.getValues() == [1, 2]
assert testList.get(1) == 2
assert testList.getValues() == [1, 2]
testList.remove(1)
assert testList.getValues() == [1]
testList.insertTail(2)
assert testList.getValues() == [1, 2]
assert testList.get(1) == 2
assert testList.get(0) == 1
##############################################################
#["remove", 0]
testList = LinkedList()
testList.remove(0) == False
print('all tests ok')