SHOW:
|
|
- or go back to the newest paste.
1 | class LLNode: | |
2 | '''Node to be used in linked list | |
3 | ||
4 | nxt: LLNode -- next node | |
5 | None iff we're at end of list | |
6 | value: object --- data for current node | |
7 | ''' | |
8 | ||
9 | def __init__(self, value, nxt=None): | |
10 | ''' (LLNode, object, LLNode) -> NoneType | |
11 | ||
12 | Create LLNode (self) with data value and successor nxt. | |
13 | ''' | |
14 | self.value, self.nxt = value, nxt | |
15 | ||
16 | def __repr__(self): | |
17 | ''' (LLNode) -> str | |
18 | ||
19 | Return a string representation of LLNode (self) that can yields | |
20 | an equivalent LLNode if evaluated in Python. | |
21 | ||
22 | >>> n = LLNode(5, LLNode(7)) | |
23 | >>> n.nxt | |
24 | LLNode(7) | |
25 | >>> n | |
26 | LLNode(5, LLNode(7)) | |
27 | ''' | |
28 | if self.nxt is None: | |
29 | return 'LLNode({})'.format(repr(self.value)) | |
30 | else: | |
31 | return 'LLNode({}, {})'.format(repr(self.value), repr(self.nxt)) | |
32 | ||
33 | def __str__(self): | |
34 | ''' (LLNode) -> str | |
35 | ||
36 | Return a user-friendly representation of this LLNode. | |
37 | ||
38 | >>> n = LLNode(5, LLNode(7)) | |
39 | >>> print(n) | |
40 | 5 -> 7 ->| | |
41 | ''' | |
42 | if self.nxt is None: | |
43 | return '{} ->|'.format(str(self.value)) | |
44 | else: | |
45 | return '{} -> {}'.format(str(self.value), str(self.nxt)) | |
46 | ||
47 | def __eq__(self, other): | |
48 | ''' (LLNode, object) -> bool | |
49 | ||
50 | Return whether LLNode (self) is equivalent to other. | |
51 | ||
52 | >>> LLNode(5).__eq__(5) | |
53 | False | |
54 | >>> n = LLNode(5, LLNode(7)) | |
55 | >>> n2 = LLNode(5, LLNode(7, None)) | |
56 | >>> n.__eq__(n2) | |
57 | True | |
58 | ''' | |
59 | return (type(self) == type(other) and | |
60 | (self.value, self.nxt) == (other.value, other.nxt)) | |
61 | ||
62 | ||
63 | ||
64 | class LinkedList: | |
65 | '''Collection of LLNodes organized into a linked list. | |
66 | ||
67 | front: LLNode -- front of list | |
68 | back: LLNode -- back of list''' | |
69 | ||
70 | def __init__(self): | |
71 | ''' (LinkedList) -> NoneType | |
72 | ||
73 | Create an empty linked list. | |
74 | ''' | |
75 | self.front, self.back = None, None | |
76 | self.size = 0 | |
77 | ||
78 | def __str__(self): | |
79 | ''' (LinkedList) -> str | |
80 | ||
81 | Return a human-friendly string representation of | |
82 | LinkedList (self) | |
83 | ||
84 | >>> lnk = LinkedList() | |
85 | >>> lnk.prepend(5) | |
86 | >>> print(lnk) | |
87 | 5 ->| | |
88 | ''' | |
89 | return str(self.front) | |
90 | ||
91 | def __eq__(self, other): | |
92 | ''' (LinkedList, object) -> bool | |
93 | ||
94 | Return whether LinkedList (self) is equivalent to | |
95 | other. | |
96 | ||
97 | >>> LinkedList().__eq__(None) | |
98 | False | |
99 | >>> lnk = LinkedList() | |
100 | >>> lnk.prepend(5) | |
101 | >>> lnk2 = LinkedList() | |
102 | >>> lnk2.prepend(5) | |
103 | >>> lnk.__eq__(lnk2) | |
104 | True | |
105 | ''' | |
106 | return (type(self) == type(other) and | |
107 | (self.size, self.front) == (other.size, other.front)) | |
108 | ||
109 | def append(lnk, value): | |
110 | ''' (LinkedList, object) -> NoneType | |
111 | ||
112 | Insert a new node with value at back of lnk. | |
113 | ||
114 | >>> lnk = LinkedList() | |
115 | >>> lnk.append(5) | |
116 | >>> lnk.size | |
117 | 1 | |
118 | >>> print(lnk.front) | |
119 | 5 ->| | |
120 | >>> lnk.append(6) | |
121 | >>> lnk.size | |
122 | 2 | |
123 | >>> print(lnk.front) | |
124 | 5 -> 6 ->| | |
125 | ''' | |
126 | new_node = LLNode(value) | |
127 | if lnk.back: | |
128 | lnk.back.nxt = new_node | |
129 | lnk.back = new_node | |
130 | else: | |
131 | lnk.back = lnk.front = new_node | |
132 | lnk.size += 1 | |
133 | ||
134 | def prepend(self, value): | |
135 | ''' (LinkedList, object) -> Nonetype | |
136 | ||
137 | Insert value at front of LLNode (self). | |
138 | ||
139 | >>> lnk = LinkedList() | |
140 | >>> lnk.prepend(0) | |
141 | >>> lnk.prepend(1) | |
142 | >>> lnk.prepend(2) | |
143 | >>> str(lnk.front) | |
144 | '2 -> 1 -> 0 ->|' | |
145 | >>> lnk.size | |
146 | 3 | |
147 | ''' | |
148 | self.front = LLNode(value, self.front) | |
149 | if self.back is None: | |
150 | self.back = self.front | |
151 | self.size += 1 | |
152 | ||
153 | def delete_front(self): | |
154 | ''' (LinkedList) -> NoneType | |
155 | ||
156 | Delete front node from LinkedList (self). | |
157 | ||
158 | self.front must not be None | |
159 | ||
160 | >>> lnk = LinkedList() | |
161 | >>> lnk.prepend(0) | |
162 | >>> lnk.prepend(1) | |
163 | >>> lnk.prepend(2) | |
164 | >>> lnk.delete_front() | |
165 | >>> str(lnk.front) | |
166 | '1 -> 0 ->|' | |
167 | >>> lnk.size | |
168 | 2 | |
169 | ''' | |
170 | ||
171 | self.front = self.front.nxt | |
172 | self.size -= 1 | |
173 | ||
174 | def __getitem__(self, index): | |
175 | ''' (LinkedList, int|slice) -> object | |
176 | ||
177 | Return the value at position index. | |
178 | # don't fuss about slices yet. | |
179 | ||
180 | >>> lnk = LinkedList() | |
181 | >>> lnk.prepend(1) | |
182 | >>> lnk.prepend(0) | |
183 | >>> lnk.__getitem__(1) | |
184 | 1 | |
185 | ''' | |
186 | if index > self.size - 1: | |
187 | raise Exception('out of range') | |
188 | else: | |
189 | current_node = self.front | |
190 | for i in range(0, index): | |
191 | current_node = current_node.nxt | |
192 | return current_node.value | |
193 | ||
194 | ||
195 | def __setitem__(self, index, value): | |
196 | ''' (LinkedList, int|slice, object) -> NoneType | |
197 | ||
198 | Set the value at index to value, if index is in range, otherwise | |
199 | raise an IndexError. Indexs are counted from 0. Note that negative | |
200 | integers can be adjusted by adding self.size, to get a index in | |
201 | range. | |
202 | ||
203 | >>> lnk = LinkedList() | |
204 | >>> lnk.prepend(5) | |
205 | >>> lnk.prepend(7) | |
206 | >>> lnk.__setitem__(1, 9) | |
207 | >>> print(lnk.front) | |
208 | 7 -> 9 ->| | |
209 | >>> lnk[0] = 3 | |
210 | >>> print(lnk.front) | |
211 | 3 -> 9 ->| | |
212 | >>> lnk[-1] = 8 | |
213 | >>> print(lnk.front) | |
214 | 3 -> 8 ->| | |
215 | ''' | |
216 | ||
217 | fixed_index = index if (index >= 0) else (index + self.size) | |
218 | if fixed_index > self.size: | |
219 | raise IndexError | |
220 | else: | |
221 | current_node = self.front | |
222 | for n in range(fixed_index): | |
223 | current_node = current_node.nxt | |
224 | current_node.value = value | |
225 | ||
226 | def __contains__(self, value): | |
227 | ''' (LinkedList, object) -> bool | |
228 | ||
229 | Return whether LinkedList (self) contains value. | |
230 | ||
231 | >>> lnk = LinkedList() | |
232 | >>> lnk.prepend(0) | |
233 | >>> lnk.prepend(1) | |
234 | >>> lnk.prepend(2) | |
235 | >>> lnk.__contains__(1) | |
236 | True | |
237 | >>> lnk.__contains__(3) | |
238 | False | |
239 | ''' | |
240 | current_node = self.front | |
241 | while current_node: | |
242 | if value == current_node.value: | |
243 | return True | |
244 | current_node = current_node.nxt | |
245 | return False | |
246 | ||
247 | def __add__(self, other): | |
248 | ''' (LinkedList, LinkedList) -> LinkedList | |
249 | ||
250 | Concatenate LinkedList (self) to LinkedList (other) and | |
251 | return a new list, leaving self and other unchanged. | |
252 | ||
253 | >>> lnk1 = LinkedList() | |
254 | >>> lnk1.prepend(5) | |
255 | >>> lnk2 = LinkedList() | |
256 | >>> lnk2.prepend(7) | |
257 | >>> lnk3 = lnk1.__add__(lnk2) | |
258 | >>> print(lnk3.front) | |
259 | 5 -> 7 ->| | |
260 | >>> print(lnk1.front) | |
261 | 5 ->| | |
262 | >>> print(lnk2.front) | |
263 | 7 ->| | |
264 | ''' | |
265 | ||
266 | new_llst = LinkedList() | |
267 | new_llst.append((self.front).value) | |
268 | next_link = (self.front).nxt.value if (self.front).nxt else None | |
269 | while next_link: | |
270 | new_llst.append(next_link) | |
271 | next_link = (self.front).nxt.value if (self.front).nxt else None | |
272 | ||
273 | new_llst.append((other.front).value) | |
274 | next_link = (other.front).nxt.value if (other.front).nxt else None | |
275 | while next_link: | |
276 | new_llst.append(next_link) | |
277 | next_link = (other.front).nxt.value if (other.front).nxt else None | |
278 | new_llst.size = self.size + other.size | |
279 | return new_llst | |
280 | ||
281 | ||
282 | def insert_before(lnk, v1, v2): | |
283 | ''' (LinkedList, object) -> NoneType | |
284 | ||
285 | Insert a new node with value v1 before the first occurrence | |
286 | of a node with value v2. Do nothing if no node has value | |
287 | v2. | |
288 | ||
289 | >>> lnk = LinkedList() | |
290 | >>> lnk.prepend(5) | |
291 | >>> insert_before(lnk, 4, 5) | |
292 | >>> print(lnk.front) | |
293 | 4 -> 5 ->| | |
294 | >>> insert_before(lnk, 3, 5) | |
295 | >>> print(lnk.front) | |
296 | 4 -> 3 -> 5 ->| | |
297 | >>> insert_before(lnk, 3, 7) | |
298 | >>> print(lnk) | |
299 | 4 -> 3 -> 5 ->| | |
300 | ''' | |
301 | new_node = LLNode(v1) | |
302 | current_node = lnk.front | |
303 | if not current_node: | |
304 | - | if lnk.front.value == v2: |
304 | + | pass |
305 | - | new_node.nxt = lnk.front |
305 | + | elif current_node.value == v2: |
306 | new_node.nxt = current_node | |
307 | - | n = 1 |
307 | + | |
308 | else: | |
309 | - | while n == 0 and not (current_node.nxt == None): |
309 | + | n = 0 |
310 | - | if current_node.nxt.value == v2: |
310 | + | while current_node.nxt and n == 0: |
311 | - | new_node.nxt = current_node.nxt |
311 | + | if current_node.nxt.value == v2: |
312 | - | current_node.nxt = new_node |
312 | + | new_node.nxt = current_node.nxt |
313 | - | lnk.size += 1 |
313 | + | current_node.nxt = new_node |
314 | n = 1 | |
315 | current_node = current_node.nxt | |
316 | ||
317 | ||
318 | def delete_after(lnk, value): | |
319 | ''' (LinkedList, object) -> NoneType | |
320 | ||
321 | Insert a new node with value after the first occurrence of a | |
322 | node containing value, if possible. | |
323 | ||
324 | >>> lnk = LinkedList() | |
325 | >>> lnk.append(3) | |
326 | >>> lnk.append(5) | |
327 | >>> lnk.append(7) | |
328 | >>> lnk.append(9) | |
329 | >>> delete_after(lnk, 3) | |
330 | >>> print(lnk) | |
331 | 3 -> 7 -> 9 ->| | |
332 | >>> delete_after(lnk, 7) | |
333 | >>> print(lnk) | |
334 | 3 -> 7 ->| | |
335 | >>> delete_after(lnk, 15) | |
336 | >>> print(lnk) | |
337 | 3 -> 7 ->| | |
338 | ''' | |
339 | n = 0 | |
340 | current_node = lnk.front | |
341 | while n == 0 and current_node.nxt: | |
342 | if current_node.value == value: | |
343 | current_node.nxt = (current_node.nxt).nxt | |
344 | lnk.size -= 1 | |
345 | n = 1 | |
346 | current_node = current_node.nxt | |
347 | ||
348 | ||
349 | def delete_back(lnk): | |
350 | ''' (LinkedList) -> NoneType | |
351 | ||
352 | Delete back node of lnk, if it exists, otherwise | |
353 | do nothing. | |
354 | ||
355 | >>> lnk = LinkedList() | |
356 | >>> lnk.prepend(5) | |
357 | >>> lnk.prepend(7) | |
358 | >>> print(lnk.front) | |
359 | 7 -> 5 ->| | |
360 | >>> delete_back(lnk) | |
361 | >>> lnk.size | |
362 | 1 | |
363 | >>> print(lnk.front) | |
364 | 7 ->| | |
365 | >>> delete_back(lnk) | |
366 | >>> lnk.size | |
367 | 0 | |
368 | >>> print(lnk.front) | |
369 | None | |
370 | ''' | |
371 | if lnk.size > 0: | |
372 | prev_node, cur_node = None, lnk.front | |
373 | # walk along until cur_node is lnk.back | |
374 | while not cur_node.nxt is None: | |
375 | prev_node = cur_node | |
376 | cur_node = cur_node.nxt | |
377 | lnk.back = prev_node | |
378 | if lnk.back is None: | |
379 | lnk.front = None | |
380 | else: | |
381 | lnk.back.nxt = None | |
382 | lnk.size -= 1 | |
383 | ||
384 | ||
385 | def odd_nodes(lnk): | |
386 | ''' (LinkedList) -> LinkedList | |
387 | ||
388 | Return a new linked list with values of odd-indexed nodes of lnk. | |
389 | ||
390 | >>> lnk = LinkedList() | |
391 | >>> lnk.append(3) | |
392 | >>> lnk.append(5) | |
393 | >>> lnk.append(7) | |
394 | >>> lnk.append(9) | |
395 | >>> lnk2 = odd_nodes(lnk) | |
396 | >>> print(lnk2) | |
397 | 5 -> 9 ->| | |
398 | ''' | |
399 | ||
400 | new_linked_list = LinkedList() | |
401 | n = 0 | |
402 | for n in range(lnk.size): | |
403 | if n % 2 == 1: | |
404 | new_linked_list.append(lnk[n]) | |
405 | return new_linked_list | |
406 | ||
407 | def filter_nodes(lnk, f): | |
408 | ''' (LinkedList, function) -> LinkedList | |
409 | ||
410 | Return a new linked list with values of lnk for | |
411 | nodes that satisfy boolean-valued function f. | |
412 | ||
413 | >>> lnk = LinkedList() | |
414 | >>> lnk.append(3) | |
415 | >>> lnk.append(4) | |
416 | >>> lnk.append(5) | |
417 | >>> lnk.append(6) | |
418 | >>> def f(node): return node.value % 2 == 0 | |
419 | >>> lnk2 = filter_nodes(lnk, f) | |
420 | >>> print(lnk2) | |
421 | 4 -> 6 ->| | |
422 | ''' | |
423 | ||
424 | new_list, cur_node = LinkedList(), lnk.front | |
425 | while cur_node: | |
426 | if f(cur_node): | |
427 | new_list.append(cur_node.value) | |
428 | cur_node = cur_node.nxt | |
429 | return new_list | |
430 | ||
431 | ||
432 | if __name__ == '__main__': | |
433 | import doctest | |
434 | doctest.testmod() |