1+ from typing import Any
2+
3+
14class Node :
2- def __init__ (self , data ):
5+ def __init__ (self , data : Any ):
6+ """
7+ Create and initialize Node class instance.
8+ >>> Node(20)
9+ Node(20)
10+ >>> Node("Hello, world!")
11+ Node(Hello, world!)
12+ >>> Node(None)
13+ Node(None)
14+ >>> Node(True)
15+ Node(True)
16+ """
317 self .data = data
418 self .next = None
519
6- def __repr__ (self ):
20+ def __repr__ (self ) -> str :
21+ """
22+ Get the string representation of this node.
23+ >>> Node(10).__repr__()
24+ 'Node(10)'
25+ """
726 return f"Node({ self .data }
827
928
1029class LinkedList :
1130 def __init__ (self ):
31+ """
32+ Create and initialize LinkedList class instance.
33+ >>> linked_list = LinkedList()
34+ """
1235 self .head = None
1336
14- def __iter__ (self ):
37+ def __iter__ (self ) -> Any :
38+ """
39+ This function is intended for iterators to access
40+ and iterate through data inside linked list.
41+ >>> linked_list = LinkedList()
42+ >>> linked_list.insert_tail("tail")
43+ >>> linked_list.insert_tail("tail_1")
44+ >>> linked_list.insert_tail("tail_2")
45+ >>> for node in linked_list: # __iter__ used here.
46+ ... node
47+ 'tail'
48+ 'tail_1'
49+ 'tail_2'
50+ """
1551 node = self .head
1652 while node :
1753 yield node .data
@@ -23,7 +59,7 @@ def __len__(self) -> int:
2359 >>> linked_list = LinkedList()
2460 >>> len(linked_list)
2561 0
26- >>> linked_list.insert_tail("head ")
62+ >>> linked_list.insert_tail("tail ")
2763 >>> len(linked_list)
2864 1
2965 >>> linked_list.insert_head("head")
@@ -38,13 +74,18 @@ def __len__(self) -> int:
3874 """
3975 return len (tuple (iter (self )))
4076
41- def __repr__ (self ):
77+ def __repr__ (self ) -> str :
4278 """
4379 String representation/visualization of a Linked Lists
80+ >>> linked_list = LinkedList()
81+ >>> linked_list.insert_tail(1)
82+ >>> linked_list.insert_tail(3)
83+ >>> linked_list.__repr__()
84+ '1->3'
4485 """
4586 return "->" .join ([str (item ) for item in self ])
4687
47- def __getitem__ (self , index ) :
88+ def __getitem__ (self , index : int ) -> Any :
4889 """
4990 Indexing Support. Used to get a node at particular position
5091 >>> linked_list = LinkedList()
@@ -68,7 +109,7 @@ def __getitem__(self, index):
68109 return node
69110
70111 # Used to change the data of a particular node
71- def __setitem__ (self , index , data ) :
112+ def __setitem__ (self , index : int , data : Any ) -> None :
72113 """
73114 >>> linked_list = LinkedList()
74115 >>> for i in range(0, 10):
@@ -95,13 +136,54 @@ def __setitem__(self, index, data):
95136 current = current .next
96137 current .data = data
97138
98- def insert_tail (self , data ) -> None :
139+ def insert_tail (self , data : Any ) -> None :
140+ """
141+ Insert data to the end of linked list.
142+ >>> linked_list = LinkedList()
143+ >>> linked_list.insert_tail("tail")
144+ >>> linked_list
145+ tail
146+ >>> linked_list.insert_tail("tail_2")
147+ >>> linked_list
148+ tail->tail_2
149+ >>> linked_list.insert_tail("tail_3")
150+ >>> linked_list
151+ tail->tail_2->tail_3
152+ """
99153 self .insert_nth (len (self ), data )
100154
101- def insert_head (self , data ) -> None :
155+ def insert_head (self , data : Any ) -> None :
156+ """
157+ Insert data to the beginning of linked list.
158+ >>> linked_list = LinkedList()
159+ >>> linked_list.insert_head("head")
160+ >>> linked_list
161+ head
162+ >>> linked_list.insert_head("head_2")
163+ >>> linked_list
164+ head_2->head
165+ >>> linked_list.insert_head("head_3")
166+ >>> linked_list
167+ head_3->head_2->head
168+ """
102169 self .insert_nth (0 , data )
103170
104- def insert_nth (self , index : int , data ) -> None :
171+ def insert_nth (self , index : int , data : Any ) -> None :
172+ """
173+ Insert data at given index.
174+ >>> linked_list = LinkedList()
175+ >>> linked_list.insert_tail("first")
176+ >>> linked_list.insert_tail("second")
177+ >>> linked_list.insert_tail("third")
178+ >>> linked_list
179+ first->second->third
180+ >>> linked_list.insert_nth(1, "fourth")
181+ >>> linked_list
182+ first->fourth->second->third
183+ >>> linked_list.insert_nth(3, "fifth")
184+ >>> linked_list
185+ first->fourth->second->fifth->third
186+ """
105187 if not 0 <= index <= len (self ):
106188 raise IndexError ("list index out of range" )
107189 new_node = Node (data )
@@ -118,17 +200,96 @@ def insert_nth(self, index: int, data) -> None:
118200 temp .next = new_node
119201
120202 def print_list (self ) -> None : # print every node data
203+ """
204+ This method prints every node data.
205+ >>> linked_list = LinkedList()
206+ >>> linked_list.insert_tail("first")
207+ >>> linked_list.insert_tail("second")
208+ >>> linked_list.insert_tail("third")
209+ >>> linked_list
210+ first->second->third
211+ """
121212 print (self )
122213
123- def delete_head (self ):
214+ def delete_head (self ) -> Any :
215+ """
216+ Delete the first node and return the
217+ node's data.
218+ >>> linked_list = LinkedList()
219+ >>> linked_list.insert_tail("first")
220+ >>> linked_list.insert_tail("second")
221+ >>> linked_list.insert_tail("third")
222+ >>> linked_list
223+ first->second->third
224+ >>> linked_list.delete_head()
225+ 'first'
226+ >>> linked_list
227+ second->third
228+ >>> linked_list.delete_head()
229+ 'second'
230+ >>> linked_list
231+ third
232+ >>> linked_list.delete_head()
233+ 'third'
234+ >>> linked_list.delete_head()
235+ Traceback (most recent call last):
236+ ...
237+ IndexError: List index out of range.
238+ """
124239 return self .delete_nth (0 )
125240
126- def delete_tail (self ): # delete from tail
241+ def delete_tail (self ) -> Any : # delete from tail
242+ """
243+ Delete the tail end node and return the
244+ node's data.
245+ >>> linked_list = LinkedList()
246+ >>> linked_list.insert_tail("first")
247+ >>> linked_list.insert_tail("second")
248+ >>> linked_list.insert_tail("third")
249+ >>> linked_list
250+ first->second->third
251+ >>> linked_list.delete_tail()
252+ 'third'
253+ >>> linked_list
254+ first->second
255+ >>> linked_list.delete_tail()
256+ 'second'
257+ >>> linked_list
258+ first
259+ >>> linked_list.delete_tail()
260+ 'first'
261+ >>> linked_list.delete_tail()
262+ Traceback (most recent call last):
263+ ...
264+ IndexError: List index out of range.
265+ """
127266 return self .delete_nth (len (self ) - 1 )
128267
129- def delete_nth (self , index : int = 0 ):
268+ def delete_nth (self , index : int = 0 ) -> Any :
269+ """
270+ Delete node at given index and return the
271+ node's data.
272+ >>> linked_list = LinkedList()
273+ >>> linked_list.insert_tail("first")
274+ >>> linked_list.insert_tail("second")
275+ >>> linked_list.insert_tail("third")
276+ >>> linked_list
277+ first->second->third
278+ >>> linked_list.delete_nth(1) # delete middle
279+ 'second'
280+ >>> linked_list
281+ first->third
282+ >>> linked_list.delete_nth(5) # this raises error
283+ Traceback (most recent call last):
284+ ...
285+ IndexError: List index out of range.
286+ >>> linked_list.delete_nth(-1) # this also raises error
287+ Traceback (most recent call last):
288+ ...
289+ IndexError: List index out of range.
290+ """
130291 if not 0 <= index <= len (self ) - 1 : # test if index is valid
131- raise IndexError ("list index out of range" )
292+ raise IndexError ("List index out of range. " )
132293 delete_node = self .head # default first node
133294 if index == 0 :
134295 self .head = self .head .next
@@ -141,9 +302,30 @@ def delete_nth(self, index: int = 0):
141302 return delete_node .data
142303
143304 def is_empty (self ) -> bool :
305+ """
306+ Check if linked list is empty.
307+ >>> linked_list = LinkedList()
308+ >>> linked_list.is_empty()
309+ True
310+ >>> linked_list.insert_head("first")
311+ >>> linked_list.is_empty()
312+ False
313+ """
144314 return self .head is None
145315
146- def reverse (self ):
316+ def reverse (self ) -> None :
317+ """
318+ This reverses the linked list order.
319+ >>> linked_list = LinkedList()
320+ >>> linked_list.insert_tail("first")
321+ >>> linked_list.insert_tail("second")
322+ >>> linked_list.insert_tail("third")
323+ >>> linked_list
324+ first->second->third
325+ >>> linked_list.reverse()
326+ >>> linked_list
327+ third->second->first
328+ """
147329 prev = None
148330 current = self .head
149331
@@ -201,6 +383,89 @@ def test_singly_linked_list() -> None:
201383 linked_list [i ] = - i
202384 assert all (linked_list [i ] == - i for i in range (0 , 9 )) is True
203385
386+ linked_list .reverse ()
387+ assert str (linked_list ) == "->" .join (str (i ) for i in range (- 8 , 1 ))
388+
389+
390+ def test_singly_linked_list_2 () -> None :
391+ """
392+ This section of the test used varying data types for input.
393+ >>> test_singly_linked_list_2()
394+ """
395+ input = [
396+ - 9 ,
397+ 100 ,
398+ Node (77345112 ),
399+ "dlrow olleH" ,
400+ 7 ,
401+ 5555 ,
402+ 0 ,
403+ - 192.55555 ,
404+ "Hello, world!" ,
405+ 77.9 ,
406+ Node (10 ),
407+ None ,
408+ None ,
409+ 12.20 ,
410+ ]
411+ linked_list = LinkedList ()
412+ [linked_list .insert_tail (i ) for i in input ]
413+
414+ # Check if it's empty or not
415+ assert linked_list .is_empty () is False
416+ assert (
417+ str (linked_list ) == "-9->100->Node(77345112)->dlrow olleH->7->5555->0->"
418+ "-192.55555->Hello, world!->77.9->Node(10)->None->None->12.2"
419+ )
420+
421+ # Delete the head
422+ result = linked_list .delete_head ()
423+ assert result == - 9
424+ assert (
425+ str (linked_list ) == "100->Node(77345112)->dlrow olleH->7->5555->0->-192.55555->"
426+ "Hello, world!->77.9->Node(10)->None->None->12.2"
427+ )
428+
429+ # Delete the tail
430+ result = linked_list .delete_tail ()
431+ assert result == 12.2
432+ assert (
433+ str (linked_list ) == "100->Node(77345112)->dlrow olleH->7->5555->0->-192.55555->"
434+ "Hello, world!->77.9->Node(10)->None->None"
435+ )
436+
437+ # Delete a node in specific location in linked list
438+ result = linked_list .delete_nth (10 )
439+ assert result is None
440+ assert (
441+ str (linked_list ) == "100->Node(77345112)->dlrow olleH->7->5555->0->-192.55555->"
442+ "Hello, world!->77.9->Node(10)->None"
443+ )
444+
445+ # Add a Node instance to its head
446+ linked_list .insert_head (Node ("Hello again, world!" ))
447+ assert (
448+ str (linked_list )
449+ == "Node(Hello again, world!)->100->Node(77345112)->dlrow olleH->"
450+ "7->5555->0->-192.55555->Hello, world!->77.9->Node(10)->None"
451+ )
452+
453+ # Add None to its tail
454+ linked_list .insert_tail (None )
455+ assert (
456+ str (linked_list )
457+ == "Node(Hello again, world!)->100->Node(77345112)->dlrow olleH->"
458+ "7->5555->0->-192.55555->Hello, world!->77.9->Node(10)->None->None"
459+ )
460+
461+ # Reverse the linked list
462+ linked_list .reverse ()
463+ assert (
464+ str (linked_list )
465+ == "None->None->Node(10)->77.9->Hello, world!->-192.55555->0->5555->"
466+ "7->dlrow olleH->Node(77345112)->100->Node(Hello again, world!)"
467+ )
468+
204469
205470def main ():
206471 from doctest import testmod
0 commit comments