# Lab 5 (Feb. 12/13)

This document contains the instructions for lab number 5 in CSC 148 H1. To earn your lab mark, you must actively participate in the lab.
We mark you in order to ensure a serious attempt at learning, NOT to make careful critical judgments on the results of your work.

## General rules

We will use the same general rules as for the first lab (including pair programming). See the instructions at the beginning of Lab 1 to refresh your memory.

## Overview

In this lab, you will get more practice writing linked list code, some of it recursively!

Even though you do not have to implement Skip Lists anymore for Part I of the project — you're welcome! :) — you still need to understand how to work with linked structures because they will come up again many times in this course (and in your future courses and work).

You know that in a linked list, elements are stored in a sequence of `Node` objects, where each `Node` stores one list element and a reference to the next `Node` in the sequence. But a "`LinkedList`" class is a higher-level structure that stores the entire chain of `Node`s (indirectly, by keeping a single reference to the first `Node`), along with methods that perform list-like operations on the entire list.

### Getting started

(Student `s1` drives and student `s2` navigates.)

• Create a new file named "`linkedlist.py`".
• In this file, write a "private" class `_Node` that stores one object reference and one `_Node` reference. (The underscore at the start of the name makes this class "private", which means that it cannot be used from outside the file `linkedlist.py`.)
• Next, write a class `LinkedList`, that stores one reference to a `_Node` (the first one in the list) and one `int` (the number of elements in the list). Your constructor should take no extra argument (in addition to the usual `self`) and it should initialize the attributes to make the list empty.
• Your class should implement the following methods.
`__len__(self)`:
Return the number of elements in this linked list.
`__contains__(self, elem)`:
Return `True` iff this linked list contains `elem`.
`__getitem__(self, ind)`:
Return the element stored at index `ind` in this linked list. Raises `IndexError` if `ind < 0` or `ind > size−1`.
`__setitem__(self, ind, elem)`:
Replace the element stored at index `ind` in this linked list with `elem`. Raises `IndexError` if `ind < 0` or `ind > size−1`.
`insert(self, ind, elem)`:
Insert `elem` at index `ind` in this linked list. Does not overwrite the element previously at index `ind`, though the index of that element (and all that follow) increases by one. Raises `IndexError` if `ind < 0` or `ind > size`.
`remove(self, ind)`:
Remove the element at index `ind` in this linked list. Raises `IndexError` if `ind < 0` or `ind > size−1`.
• Many of these are "special" methods that are never called directly, but that get called automatically in appropriate situations. For example, here is one way that your class could get used and its expected behaviour:
```    list1 = LinkedList()  # creates a new empty linked list
print(len(list1))  # automatically calls list1.__len__(); prints '0'
print(5 in list1)  # automatically calls list1.__contains__(5); prints 'False'
#print(list1[0])  # automatically calls list1.__getitem(0); raises IndexError
list1.insert(0, 5)
print(len(list1))  # prints '1'
print(5 in list1)  # prints 'True'
print(list1[0])  # prints '5'
list1[0] = 20  # automatically calls list1.__setitem__(0, 20)
print(list1[0])  # prints '20'
list1.insert(1, 5)
print(len(list1))  # prints '2'
print(list1[1])  # prints '5'
list1.remove(0)
print(len(list1))  # prints '1'
print(list1[0])  # prints '5'
```
• As you are writing code for these methods, you should be drawing lots of pictures that show the values of various `_Node` references during the execution of your code. This is not something you should do only if you have trouble, but something that you should always do when working with linked structures.

When you are done, show your work to your TA and switch roles.

### Now for some recursion...

(Student `s2` drives and student `s1` navigates.)

• Add the following method to your class `LinkedList`:
reverse(self):
Change the position of elements in this linked list so that the order of the entire list is reversed. This is done in-place, without creating a new list.
• Your method should not create or "delete" any `_Node`s. Instead, it should simply rearrange the links to reverse all of them — and also update the list's reference to the first `_Node`.
• The simplest way to do this is to write a recursive helper function that works directly with `_Node`s to perform the reversal, and then simply make the initial call to the helper within the body of `reverse`.
• To come up with the correct helper, think carefully about the following questions:
• What information does the helper need to be given to carry out its work? (This determines parameters.)
• What information does the helper need to give back? (This determines return value(s).)
• What is the precise purpose of the helper? (This is its docstring, which will help understand how to write it recursively.)

When you are done, show your work to your TA. You're done!