Description

4.
set-up
Open le ex.py in Pycharm, and save it under a sub-directory called lab4. This le declares both class LinkedListNode, to represent linked list nodes, and class LinkedList, to represent an entire linked list. There are also headers and docstrings for methods that you will implement, as well as some methods we have already implemented, to get you started.
We have commented-out method headers that you are to implement. You should uncomment these, one-by-one, as you work on them.
Once you have familiarized yourself with the init and str methods for class LinkedListNode and LinkedList, you are almost ready to proceed to the implementation of the methods below. But rst, read the warnings below:
Draw lots of pictures! You will need these to understand what your linked structures should look like before, during, and after operations where you change (mutate) those structures. If you skip the drawing, you are much more likely to mess up!

These pictures are not just for beginners. Experienced programmers routinely draw pictures when they write code for linked structures.
Be sure that you know exactly what attribute each part of your drawing represents. This will guide your code.
implement special method setitem
Read the docstring and examples for method setitem . The type for parameter index is int. You should adjust any negative index from n to 1 (if n is the length of the list) to an index in range by adding the size of the list. However, you should raise an IndexError if index is too large or too small. Notice that this is consistent with the behaviour of Python’s built-in list.
Before you write any code, decide what steps must occur and draw careful pictures of how your list should look before and after each step. If it worked, you should be able to do something like:
>>> lnk = LinkedList()
>>> lnk.prepend(5)
1
>>> print(lnk)
5 ->|
>>> lnk[0] = 7
>>> print(lnk) 7 ->| implement method add
Read the docstring and examples for method add . The aim is to provide a way of adding” (concatenating) linked lists to produce a new one (the original lists are unchanged). As usual, draw careful pictures of each step you carry out.
You are allowed to use method append, if it helps. Once you are nished, you should be able to do things like this:
>>> lnk1 = LinkedList()
>>> lnk1.prepend(5)
>>> lnk2 = LinkedList()
>>> lnk2.prepend(7)
>>> print(lnk1 + lnk2)
5 -> 7 ->|
>>> print(lnk1)
5 ->|
>>> print(lnk2) 7 ->| implement method insert before
Read the docstring and examples for method insert before. The aim is to be able to insert a new node with value v1 before the rst occurrence of v2, if possible.
You will want to keep track of two nodes as you walk the list, which should look something like this:
while <some condition here>: prev_node = cur_node cur_node = cur_node.next_
It is really easy to lose track of a reference between LinkedListNodes as you do this so…draw pictures.
implement method delete after
Read the docstring and examples for method delete after. The aim is to be able to delete the node after the rst occurrence of value, if such a node exists.
Again, it’s really easy to mess up the updating of references, so you’ll need pictures. h
additional exercises
2