-
Notifications
You must be signed in to change notification settings - Fork 0
/
singly-linked-list.py
151 lines (123 loc) · 3.19 KB
/
singly-linked-list.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
class Node(object):
def __init__(self, value=None, next_node=None):
self.value = value
self.next_node = next_node
def getValue(self):
return self.value
def setValue(self, value):
self.value = value
def getNext(self):
return self.next_node
def setNext(self, new_next):
self.next_node = new_next
class LinkedList(object):
def __init__(self, head=None):
self.head = head
def insert(self, value):
new_node = Node(value)
new_node.setNext(self.head)
self.head = new_node
def search(self, value):
current = self.head
counter = 0
while current:
counter += 1
if current.getValue() == value:
break
current = current.getNext()
if current is None:
print(f"{value} not found.")
return False
print(f"Found {value} at node {counter}.")
return True
def update(self, value, new_value):
current = self.head
counter = 0
while current:
counter += 1
if current.getValue() == value:
break
current = current.getNext()
if current is None:
print(f"{value} not found.")
return False
current.setValue(new_value)
print(f"Updated {value} to {new_value} at node {counter}.")
return True
def delete(self, value):
current = self.head
previous = None
counter = 0
while current:
counter += 1
if current.getValue() == value:
break
previous = current
current = current.getNext()
if current is None:
print(f"{value} not found.")
return False
if previous is None:
self.head = current.getNext()
else:
previous.setNext(current.getNext())
print(f"Deleted {value} at {counter}")
return True
def traverse(self):
current = self.head
counter = 0
while current:
counter += 1
print(f"{current.getValue()}", end=' ')
current = current.getNext()
print()
def reverse(self):
if self.head == None:
print("Cannot reverse empty linked list")
return
prev_n = self.head
next_n = self.head.next_node
self.head.next_node = None
while next_n:
tmp = next_n
next_n = next_n.next_node
tmp.next_node = prev_n
prev_n = tmp
self.head = prev_n
if __name__ == '__main__':
ll = LinkedList()
ll.insert(1)
ll.insert(2)
ll.insert(3)
ll.insert(2)
ll.traverse()
ll.search(5)
ll.insert(5)
ll.traverse()
ll.search(5)
ll.delete(2)
ll.traverse()
ll.search(1)
ll.search(2)
ll.delete(5)
ll.traverse()
ll.search(3)
ll.update(3, 33)
ll.traverse()
ll.reverse()
ll.traverse()
""" Output
2 3 2 1
5 not found.
5 2 3 2 1
Found 5 at node 1.
Deleted 2 at 2
5 3 2 1
Found 1 at node 4.
Found 2 at node 3.
Deleted 5 at 1
3 2 1
Found 3 at node 1.
Updated 3 to 33 at node 1.
33 2 1
"""