-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathLinkedLists.py
228 lines (182 loc) · 6.66 KB
/
LinkedLists.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
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
"""
Author: Ahmad Elkholi
Created on Fri Feb 25 16:58:57 2022
"""
from abc import ABC, abstractmethod
class Node:
'''Create a singly linked list node'''
def __init__(self, data = None):
self.data = data
self.next = None
def __repr__(self) -> str:
return f"{self.data}"
class LinkedList(ABC):
'''Base Class for linked lists implementations'''
def __init__(self, *vals, circular = False) -> None:
self.head = None
self.tail = None
self.circular = circular
self._length = 0
for val in vals:
self.insert(val)
def __len__(self) -> int:
return self._length
def __iter__(self):
self.__node = self.head
return self
def __next__(self) -> Node:
if self.__node is None:
raise StopIteration
node = self.__node
if self.circular and self.__node == self.tail:
self.__node = None
else:
self.__node = self.__node.next
return node
def __contains__(self, val) -> bool:
for node in self:
if node.data == val: return True
return False
@abstractmethod
def insert(self, val):
pass
def delete(self):
'''Delete all elements of a linked list.
Once you set the head & tail to None, the garpage collector will delete all nodes one by one.
'''
self.head = None
self.tail = None
self._length = 0
return self
class SinglyLL(LinkedList):
"""Single Linked List Class
Parameters
----------
vals: list, tuple
values of the nodes in the linked list. Values are added in their same order in vals.
Methods
-------
insert(self, val, index: int = None)
Insert a node containing the given value in the specified index.
"""
def __repr__(self) -> str:
values = []
for node in self:
values.append(str(node.data))
return "->".join(values)
def insert(self, val, index: int = None):
"""Insert a node containing the given value to the linked list in the specified index.
Parameters
----------
val:
The value contained in the added node
index: int
The index of the added node in the linked list. if unspecified, the node will be added at the end of the list
default = None
Returns
-------
self
"""
if index == None: index = self._length
if not isinstance(index, int):
raise TypeError(f"Invalid type {type(index)}. Index must be int")
if index not in range(self._length + 1):
raise IndexError(f"index out of bound, please specify an index between 0 and {self._length}")
new_node = Node(val)
if self.head is None:
#If list has no nodes, assign node as both head and tail.
self.head = new_node
self.tail = new_node
elif index == 0:
#The new node is added to the beginning of the list.
new_node.next = self.head
self.head = new_node
elif index == self._length:
#The new node is added to the end of the list.
self.tail.next = new_node
self.tail = new_node
else:
#The new node is added to the middle of the list.
previous_node = self.head
for _ in range(index-1):
previous_node = previous_node.next
new_node.next = previous_node.next
previous_node.next = new_node
if self.circular: self.tail.next = self.head
self._length += 1
return self
def pop(self, index: int = None):
"""Remove the node with the specified index from the Linked List.
Parameters
----------
index: int
The index of the deleted node in the linked list. if unspecified, the last node will be removed.
default = None
Returns
-------
self
"""
#If the list is already empty, return.
if self.head is None:
return self
if index == None:
index = self._length - 1
if not isinstance(index, int):
raise TypeError(f"Invalid type {type(index)}. Index must be int")
if index not in range(self._length):
raise IndexError(f"index out of bound, please specify an index between 0 and {self._length}")
if index == 0:
if self.head == self.tail:
#If the linked list has only one node.
self.head = None
self.tail = None
else:
self.head = self.head.next
if self.circular: self.tail.next = self.head
else:
previous_node = self.head
#Find the node that is directly before the deleted node.
for _ in range(index-1):
previous_node = previous_node.next
previous_node.next = previous_node.next.next
#If the deleted node is the last node then assign previous_node to the tail.
if previous_node.next is None or previous_node.next == self.head:
self.tail = previous_node
self._length -= 1
return self
def remove(self, val):
"""Remove the node with the specified value from the Linked List.
Parameters
----------
val: int
The val of the deleted node in the linked list.
Returns
-------
self
"""
#If the list is already empty, return.
if self.head is None:
return self
if self.head.data == val:
if self.head == self.tail:
#If the linked list has only one node.
self.head = None
self.tail = None
else:
self.head = self.head.next
if self.circular: self.tail.next = self.head
else:
previous_node = self.head
#Find the node that is directly before the deleted node.
for node in self:
if node.data == val:
previous_node.next = node.next
break
previous_node = node
else:
raise ValueError(f"'{val}' does not exists in the list.")
#If the deleted node is the last node then assign previous_node to the tail.
if previous_node.next is None or previous_node.next == self.head:
self.tail = previous_node
self._length -= 1
return self