-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathpythonLinklist.py
More file actions
125 lines (102 loc) · 3.43 KB
/
Copy pathpythonLinklist.py
File metadata and controls
125 lines (102 loc) · 3.43 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
from typing import Optional
class Node:
def __init__(self, data: int, next=None):
self.data = data
self._next = next
class SinglyLinkedList:
def __init__(self):
self._head = None
def find_by_value(self, value: int) -> Optional[Node]:
p = self._head
while p and p.data != value:
p = p._next
return p
def find_by_index(self, index: int) -> Optional[Node]:
p = self._head
position = 0
while p and position != index:
p = p._next
position += 1
return p
def insert_value_to_head(self, value: int):
new_node = Node(value)
self.insert_node_to_head(new_node)
def insert_node_to_head(self, new_node: Node):
if new_node:
new_node._next = self._head
self._head = new_node
def insert_value_after(self, node: Node, value: int):
new_node = Node(value)
self.insert_node_after(node, new_node)
def insert_node_after(self, node: Node, new_node: Node):
if not node or not new_node:
return
new_node._next = node._next
node._next = new_node
def insert_value_before(self, node: Node, value: int):
new_node = Node(value)
self.insert_node_before(node, new_node)
def insert_node_before(self, node: Node, new_node: Node):
if not self._head or not node or not new_node:
return
if self._head == node:
self.insert_node_to_head(new_node)
return
current = self._head
while current._next and current._next != node:
current = current._next
if not current._next: # node is not even in the list
return
new_node._next = node
current._next = new_node
def delete_by_node(self, node: Node):
if not self._head or not node:
return
if node._next:
node.data = node._next.data
node._next = node._next._next
return
# node is the last one or not in the list
current = self._head
while current and current._next != node:
current = current._next
if not current: # node not in the list
return
current._next = None
def delete_by_value(self, value: int):
if not self._head or not value:
return
fake_head = Node(value + 1)
fake_head._next = self._head
prev, current = fake_head, self._head
while current:
if current.data != value:
prev._next = current
prev = prev._next
current = current._next
if prev._next:
prev._next = None
self._head = fake_head._next # in case head.data == value
def print_all(self):
current = self._head
if current:
print(current.data, end="")
current = current._next
while current:
print(current.data, end="")
current = current._next
print("\n", flush=True)
if __name__ == "__main__":
l = SinglyLinkedList()
for i in range(15):
l.insert_value_to_head(i)
node9 = l.find_by_value(9)
l.insert_value_before(node9, 20)
l.insert_value_before(node9, 16)
l.insert_value_before(node9, 16)
l.delete_by_value(16)
node11 = l.find_by_index(3)
l.delete_by_node(node11)
l.delete_by_node(l._head)
l.delete_by_value(13)
l.print_all()