Linked List Lab

Objectives

The goal of this lab is to gain experience with the implementation of singly-linked lists.

Introduction

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.

Download the file singly_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.

Exercises

  1. Implement the count method, which should return a count of the number of times that the given item is found in the list.
  2. Implement the index method. This will be very similar to the included __contains__ method, except that it needs to return the index of the element if it is found, rather than a simple boolean. Thus, you will need to track the current index as you traverse the linked list.
  3. Implement the append method, which should add a new element onto the tail of the list. You must also remember to handle the special case when the list is empty. Given the current implementation, there is no O(1) way to add an element to the tail of the list. You have two options to implement this function:
    1. Iterate to the end of the list, finding the last node and adding the new node after that node. This will be O(n) but that is ok for the purposes of this lab.
    2. Add a _tail reference to the LinkedList class and use it to add a new item in O(1) time. This is a better solution, but will require you to change several other functions to properly maintain the tail pointer.
  4. Implement the __eq__ and __ne__ methods. For these functions, equality should be defined as follows: both lists have the same number of elements, and each pair of corresponding elements in the list are also equal (as defined by the == operator). You should implement only one of these operators from scratch; the other should delegate to the first.
  5. (Optional) 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 prev_node and a cur_node. Insert the new node at the appropriate location.
    • Increment the size of the list.
  6. (Optional) Implement the remove method. You will need to traverse the list looking for the item to remove, keeping track of the predecessor node so that you can reconnect the two separate parts of the list after removal. If the item is not found in the list, the method should raise a ValueError.

Submission

This lab will not be graded so there is nothing to submit. Make sure you keep a copy of your code for future reference. If you would like to discuss your solution or any problems you encounter while working on this lab, please come to office hours or make an appointment.