CS21 Lab: LinkedLists

This lab is OPTIONAL (we will not grade it). However, you may want to write these methods as practice for the final exam.

Implementing a linked list class

For this lab, run update21 to get a clean copy of the code we wrote in class in your cs21/labs/12 directory. You should have the Node class and the start of the LinkedList class.

This linked list class is defined to implement an interface similar to the Python list interface. in particular, this means that it has methods that implement an indexing interface to a linked list. Your job for this lab is to write/finish the linked list class so that it behaves like a Python list. In particular, your class must support the following methods:

More detailed documentation is provided in the linkedlist.py file. To get you started, we have already written the __init__() and __str__() methods. You may also use any code that we have given you or that we have worked on in class together. (Note: see how to copy code in vim for a nice way to copy code from one file to another).

The first part of the lab is to understand exactly what the methods we went over in class are doing. Remember, there are three attributes that the linked list must always keep up to date: head, tail, and size. At the end of every method call, all three of these attributes must be correct. Watch out for special cases, such as deleting a node when there's only one node left in the list.

Note: If you need to insert or remove an item from the beginning or end of the list in one of your methods (for example, a call of pop(0) will remove the first item in the list), your method should call the methods you specifically wrote to handle these situations (e.g., removeHead()). Calling one method from another method in the same class is done with self as the object. For example, calling the removeHead() method from the pop() method would be: self.removeHead()

Testing your code

You should always test your code! We have written some assert statements. For each method you write, add additional asserts to test the method. No output means the assert test passed. If the assert test doesn't pass, you will see an AssertionError. Here are a few examples:


    # Test the constructor __init__, __str__, append and len
    LL = LinkedList()
    assert len(LL) == 0
    assert str(LL) == "[]"
    LL.append("A")
    LL.append("B")
    LL.append("C")
    assert len(LL) == 3
    assert str(LL) == "[A, B, C]"

Optional Challenge

The following methods allow linked list objects to use square-bracket indexing and the membership (in) operator. If you have time, see if you can implement these extra methods:

>>> from linkedlist import *
>>> LL = LinkedList()
>>> for ch in "ABCDE":
...   LL.append(ch)
... 
>>> print(LL)
[A, B, C, D, E]
>>> "C" in LL
True
>>> "Z" in LL
False
>>> print(LL[1])
B
>>> LL[4] = "Z"
>>> print(LL)
[A, B, C, D, Z]