Lab 10

Wed, Sep 30, 2015

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 implement a List ADT using either contiguous storage (an array) or a linked structure. The goal of this activity is to gain experience working with linked structures by implementing a subset of the methods from the List ADT using a singly-linked list as the underlying data structure.

Download the lab starter files here:

• Tarball
• Zip file

Don’t forget to download and customize your machine-specific makefile.

These files contain an incomplete implementation of a singly-linked list data structure. Take a moment to look over this code and experiment with the provided functions.

Exercises

• Implement the count method, which should return a count of the number of times that the given item is found in the list.

• Implement the find 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. This method should return -1 if the item is not found.

• Implement the addlast 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. Don’t forget to update the size tracker! IMPORTANT: 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:

  • 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.

  • Add a tail reference to the sllist_t struct 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.

• Implement the is_equal function. 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).

(Optional) More Exercises

• Implement the insert function. This function should insert an item at an arbitrary index in the linked list. This operation will be inherently inefficient because index-based accesses are not O(1) as they are in arrays. One way of organizing this method is to work through the following steps:

  1. Check to make sure the index is in bounds.

  2. Create a new node to contain the item being inserted.

  3. Check to see if insertion should occur at the head; if so, handle that as a special case.

  4. 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.

  5. Increment the size of the list.

• Implement the remove function. This function should remove the given item from the list if it is present. If there are multiple occurences of the given item, it should only remove the first one. 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 function should make no changes.

Challenge Problems

• Convert your implementation to use a doubly-linked list with head and tail sentinel nodes. Which of the above operations can be implemented more quickly using a doubly-linked implementation?

• Convert your implementation to be a referential list, where the “items” are actually pointers to the items.