-
Notifications
You must be signed in to change notification settings - Fork 6
/
test.py
executable file
·169 lines (139 loc) · 3.84 KB
/
test.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
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
class Node:
"""
Node is used to construct a node of linked list
"""
def __init__(self, val: int, next: '__class__' = None):
"""
construct a node
:param val: value of current node
:param next: point to next node
"""
self.val = val
self.next = next
class MyLinkedList:
"""
MyLinkedList is used to construct a linked list
"""
def __init__(self, head: Node = None, tail: Node = None, size: int = 0):
"""
construct a empty linked list
:param head: head of linked list
:param tail: tail of linked list
:param size: size of linked list
"""
self.head = head
self.tail = tail
self.size = size
def get(self, index: int) -> int:
"""
get the value of index-th node of the linked list
:param index: index
:return: value of the node
"""
if index < 0 or index >= self.size:
return -1
p = self.head
i = 0
while i < index:
p = p.next
i += 1
return p.val
def add_at_head(self, val: int) -> None:
"""
add a node of val in head of the linked list
:param val: val of the node
:return: None
"""
node = Node(val)
if self.head is None:
self.head = node
self.tail = node
else:
node.next = self.head
self.head = node
self.size += 1
def add_at_tail(self, val: int) -> None:
"""
add a node of val in the tail of the linked list
:param val: val of the node
:return: None
"""
node = Node(val)
if self.head is None:
self.head = node
self.tail = node
else:
self.tail.next = node
self.tail = node
self.size += 1
def add_at_index(self, index: int, val: int) -> None:
"""
add a node of val before the index-th node of the linked list
:param index: index
:param val: val of the node
:return: None
"""
if index < 0 or index > self.size:
return
node = Node(val)
if 0 == index: # add at head
node.next = self.head
self.head = node
if 0 == self.size:
self.tail = node
elif self.size == index: # add at tail
self.tail.next = node
self.tail = node
else:
p = self.head
i = 0
while i < index - 1:
p = p.next
i += 1
node.next = p.next
p.next = node
self.size += 1
def delete_at_index(self, index: int) -> None:
"""
delete the index-th node of the linked list
:param index: index
:return: None
"""
if index < 0 or index >= self.size:
return
if 0 == index:
self.head = self.head.next
if 1 == self.size:
self.tail = None
else:
p = self.head
i = 0
while i < index - 1:
p = p.next
i += 1
p.next = p.next.next
if self.size - 1 == index:
self.tail = p
self.size -= 1
def __str__(self) -> str:
"""
return str of the linked list
:return: str
"""
p = self.head
values = []
while p is not None:
values.append(str(p.val))
p = p.next
return ', '.join(values)
if '__main__' == __name__:
my_list = MyLinkedList()
my_list.add_at_head(1)
print(my_list)
my_list.add_at_head(2)
print(my_list)
my_list.add_at_head(3)
print(my_list)
print(my_list.get(0))