CPSC170 Lab 8

Linked Lists

In this lab you are going to implement a linked list that can have objects added to the back and removed from the front.

Adding

The file linked_list.py contains a template for a linked list class. It has instance data for references to the first and last nodes in the list. These references are of type _Node, which is a private sub-class of LinkedList. The node class has two instance variables, object and next. The object instance variable is a is a reference to the data stored in the linked list. The next instance variable is a reference to the next node in the linked list. If next is None, then the node is the last element in the list.

The LinkedList class contains a method stub, add_last, for adding to the linked list. The method should add the specified object to the end of the linked list. The method should begin by creating a new node with object set to the object to add and next set to None (because it is the end of the list). Next, if the list is empty, it should set the first instance variables to reference the new node. If the list is not empty, it should walk through the list, until it finds the last node in the list. You should then update that last nodes next to reference the new node. Finally, increment the size instance variable.

Printing

Before testing the add_last method you will need to be able to print a linked list. Complete the __str__ method. The method should return a string that is a concatenation of all of the elements in the linked list. In order to generate this string you should create a variable that is initialized to the first node in the list and write a loop that concatenates a string representation of the object in the current node to the return string and updates the current node to be the next node in the list. The loop should terminate when there is no next element. Write a program that tests both the add_last and the __str__ methods. Be sure to test the __str__ method on an empty list as well as a full list.

Accessing

The LinkedList class is not very useful without the ability to access objects in the list. Complete the get_first and remove_first methods. The get_first method return the object in the first node in the list without modifying the list. If the list is empty, the method should raise an IndexError. Test the get_first method before proceeding.

The remove_first method should remove the first element from the linked list. If the list is empty, the method should raise an IndexError. If the list contains only one element, the method should set the first and last references to None. If the list contains more than one element, the method should set the first reference to be the second element in the list. Finally, decrement the size variable. Note, the remove method does not actually delete any data. It simply changes references such that there are no variables that reference the deleted node. The Python interpreter keeps track of how many references there are to objects and deletes objects when the reference count becomes zero. Test your remove_first method before proceeding.

Using a Linked List

Linked Lists are useful for storing data that can be of arbitrary size. As you are probably aware, integers in Python can be of arbitrary size. This is in spite of the fact that integers in hardware have a fixed size (usually 32 or 64 bits). This is done in software within python. For this portion of the lab, you will implement your own "Big Integer" class, which can represent arbitrarily large integers.

Integers in this class will be implemented as a singly linked list, orders from the least significant digit. So, for the number 12,345 should conceptually look like this:

Create a class that represents an arbitrarily large integer. You will want to implement the following methods:

• __len__(self) - Returns an integer, the number of digits within this number
• __str__(self) - Returns a String, the number contained within the linked list
• __eq__(self, other) - Returns true if the number represented by self is equal to the number represented by other.
• __add__(self, other) - Returns a new Big Integer, the result of adding the number represented by self to the number represented by parameter other.

Submission

Submit a zip file of your code on the course Inquire site that uses your last names as the file name.