In-Class Activity: Linked List Methods

Objective

It is possible to implemented a List ADT using either contiguous storage (an array) or a linked structure. Python's built-in list class uses the first approach. The goal of this activity is to gain experience working with linked structures by implemented a subset of the methods from the List ADT using a singly-linked list as the underlying data structure.

Exercises

1. Download the file linked_list.py. This file contains an incomplete implementation of a Python LinkedList class. Take a minute to look over this code. Open a Python interpreter and experiment with creating a LinkedList object and calling the methods that have already been implemented.
2. Complete the implementation of the __getitem__ and __setitem__ methods of the LinkedList class. Test your methods to make sure that they work as expected.
   
   Notes:
   • Don't forget to handle negative index values. Negative index values can be converted into their positive form by adding the length of the list.
   • A for loop is more appropriate here than a while loop. For loops are preferred when the loop body should execute a fixed number of times.
   • Most of the code required for __getitem__ and __setitem__ is the same. Each method needs to handle negative index values, raise an IndexError if the index is out of the allowed range, and obtain the _ListNode at the appropriate position. It makes sense to write a helper method that handles these common tasks. The following provides a starting point:

       def _nodeAt(self, indx):
          # Returns the _ListNode at position indx. 
          # Raises an IndexError if the index is out of range. 
     

     Once _nodeAt is completed, __getitem__ and __setitem__ should each require at most two lines of code.
3. (If you have time.) Implement the insert method. One way of organizing this method is to work through the following steps:
   • If necessary, convert the index value from negative to positive.
   • Raise an exception if the index is out of bounds.
   • Create a new node to contain the item being inserted.
   • Check to see if insertion should occur at the head, if so handle that as a special case.
   • If the item is not being inserted at the head, use a loop to step through the correct number of nodes, keeping track of a predecessorNode and a currentNode. Insert the new node at the appropriate location.
   • Increment the size of the list.

Finishing Up

There is nothing to hand in for this assignment. Make sure that you save a copy of your code.