-
Notifications
You must be signed in to change notification settings - Fork 1
/
LinkedList.py
258 lines (192 loc) · 6.47 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
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
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
from LLNode import Node
import copy
from collections.abc import Iterable
class LinkedList:
def __init__(self, data=None, iterable=True):
'''
:param data: data to add to linked list (if it is an iterable it will loop through and add each
piece of data unless you specify iterable = False, then it will just add the iterable to one node)
:param iterable: only set this to False if initializing with an iterable and you want that iterable
to be stored in one node and not multiple nodes
'''
self.head = None
self.size = 0
self.current = None
if data:
if isinstance(data, Iterable) and iterable:
self.extend(data)
else:
self.add(data)
def add(self, data, *args):
if isinstance(data, Node): data = data.data
self.size += 1
self.head = Node(data, self.head)
for arg in args:
self.add(arg)
def insert(self, data, index):
if isinstance(data, Node): data = data.data
if index < 0:
index = self.size + index
if index == 0:
self.add(data); return
elif index > self.size or index < 0:
raise IndexError('Invalid index given')
elif index == self.size:
self.get(index-1).next = Node(data)
else:
current = self.get(index-1)
old = current.next
current.next = Node(data, old)
self.size += 1
def get(self, index):
if index < 0:
index = self.size + index
if index == 0:
return self.head
elif index > self.size - 1 or index < 0:
raise IndexError('Invalid index given')
else:
current, ind = self.head, 0
while current:
if index == ind:
return current
ind += 1
current = current.next
def append(self, data, *args):
if isinstance(data, Node): data = data.data
self.insert(data, self.size)
for arg in args:
self.append(arg)
def copy(self):
return self.__copy__()
def __copy__(self):
ll = LinkedList()
ll.extend(self)
return ll
def deepcopy(self):
return self.__deepcopy__()
def __deepcopy__(self, memodict={}):
ll = LinkedList()
for node in self:
ll.append(copy.deepcopy(node.data))
return ll
def remove(self, item):
if self.head.data == item:
self.head = self.head.next; return
last = self.head
for node in self[1:]:
if node.data == item:
last.next = item.next
break
else:
raise IndexError('Item not found')
def pop(self, index=None):
if index is None:
index = self.size - 2
if index < 0:
index = self.size + index
if index == 0:
rv = self.head
self.head = self.head.next
elif index > self.size - 1 or index < 0:
raise IndexError('Invalid index given')
else:
prev = self.get(index-1)
rv = prev.next
prev.next = prev.next.next
self.size -= 1
return rv.data
def extend(self, iterable):
if isinstance(iterable, LinkedList):
if self.size > 0:
self.get(self.size-1).next = iterable.head
else:
self.head = iterable.head
self.size += len(iterable)
else:
for item in iterable:
self.append(item)
def reverse(self):
ll = LinkedList()
while self.head:
ll.add(self.pop(0))
self.extend(ll)
del ll
def contentEquals(self, other):
if self.size != len(other): return False
for n1, n2 in zip(self, other):
if n1 != n2:
return False
return True
def dataEquals(self, other):
if self.size != len(other) or not isinstance(other, LinkedList): return False
for n1, n2 in zip(self, other):
if n1.data != n2.data:
return False
return True
def clear(self):
self.head, self.size = None, 0
def __reversed__(self):
ll = LinkedList()
for node in self:
ll.add(node.data)
return ll
def __iter__(self):
return self
def __next__(self):
if not self.current:
if not self.head:
self.current = None
raise StopIteration
self.current = self.head
else:
if not self.current.next:
self.current = None
raise StopIteration
self.current = self.current.next
return self.current
def __repr__(self):
return f"Linked List Object Containing: [{', '.join(str(i) for i in self)}]"
def __str__(self):
return f"[{', '.join(str(i) for i in self)}]"
def __len__(self):
return self.size
def __mul__(self, other):
assert other > 0
for i in range(other-1):
self.extend(copy.deepcopy(self))
return self
def __getitem__(self, item):
if isinstance(item, int):
return self.get(item)
elif isinstance(item, slice):
start, stop, step = item.start or 0, item.stop or self.size, item.step or 1
assert all(type(i) == int for i in (start, stop, step))
if start < 0: start = self.size + start
if stop < 0: stop = self.size + stop
if step < 0: rev = True; step = -step
else: rev = False
ll = LinkedList()
for i, x in enumerate(self):
if start <= i < stop and (i + start) % step == 0:
ll.append(x)
if rev:
return reversed(ll)
return ll
else:
raise TypeError('Invalid index type given (accepted indexes: int, slice)')
def __setitem__(self, key, value):
assert isinstance(key, int)
self.get(key).data = value
def __delitem__(self, key):
assert isinstance(key, int)
self.pop(key)
def __contains__(self, item):
for node in self:
if node == item or node.data == item:
return True
return False
def sort(self):
new = LinkedList(sorted(self))
self.clear()
self.extend(new)