As a convenience for you we have already created an inner$/$nested class for you called SListNode. You are free to modify this class as you see fit, but it should remain an inner class to the SList class. Note that this kind of encapsulation is great for readability, maintainability, and portability.

Step $2$ The SList Class

The SList class is the most significant piece of this project. As mentioned above $$ you would be wise to implement this class as though it will only ever store int values. This will make it easier to think about, and we will see that thanks to dynamic typing $$ will be enough to make it work in the general case as well if we are just a little bit careful. SList must implement the following methods:

insert$($item$)$ : item is inserted in the list at the appropriate location to maintain a non$-$decreasing ordering based on whatever key the item is compared on$.$ If two items are considered identical, the newer item should appear AFTER the older item $($i$.$e$.$ ascending order of arrival time$).$ For instance if the list contains the integers $1,5,6,9($and in this case the value of the integer is used to establish an ordering$)$ and an additional $6$ is inserted, then the list would contain $1,5,6,6,9$ and the second $6$ would be the newly inserted $6.$ For simple integers this doesn$$t matter $$ but for more complex objects it might. This function does not return a value

remove$($key$)$ : Removes the first occurrence of an item as indicated by the key from the list. Returns True if an item was found and removed, False if not.

remove$\_$all$($key$)$ : Removes ALL occurrences of an item as indicated by the key from the list. Doesn$$t return a value.

size$()$ : Returns the current number of items$/$nodes in the list.

find$($key$)$ : Searches for the first occurrence of an item as indicated by the key value in the list. If found, the item is returned; returns None otherwise.

$\_\_$str$\_\_()$ : Returns a string representation of the contents of the list. This string should start with $[$ and end with $],$ and the string representations of the list items should be comma separated, and listed in order. Note the somewhat recursive nature of this method as it will need to call $\_\_$str$\_\_()$ on the individual list items...

We recommend implementing these methods and creating simple unit tests on your own to validate their behavior.

Step $3-$ Make it Iterable

In addition to the methods listed above, your SList class must support several of the $$goodies$$ that Python lists make available to us$.$ The first of these is that your SList class must be iterable so that it can be used in for loops etc. as we are accustomed to doing with $$regular$$ Python lists. For a class to be iterable it must implement or otherwise provide access to the following methods:

$\_\_$iter$\_\_()$ : Returns an iterator object $($something that has implemented $\_\_$next$\_\_())$

$\_\_$next$\_\_()$ : Returns $($or yields$)$ the next value in a sequence $$ in this cas the next value in the list. $($may not be explicitly necessary if you choose to implement a generator function$)$

Step $4$ Show us the Brackets!

Being able to access an item at a give position in a list is an extremely useful capability. You must extend SList to support position based indexing via the square bracket notation we are used to $($e$.$g$.$ theList$[3]).$ To do this you must implement the $\_\_$getitem$\_\_()$ magic method as follows

$\_\_$getitem$\_\_($index$)$ : Returns the value stored at position index in the list. Once again we suggest that you implement these methods and test your code to validate its performance. The is$\_$sorted$()$ function provided in the supplied p$3\_$main$\_$template.py file may be useful to you at this point.