Sorted Linked List Lab

Objectives

In PA3, you will implement a Sorted Set ADT, which is identical to the Set ADT from PA2 except that iterating over a Sorted Set produces a list of the set items in strictly increasing order. As a preliminary exercise, you will finish the implementation of a basic sorted linked list with a head sentinel.

Introduction

Download the lab starter files here:

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

The sorted_list_t struct represents a sorted, singly-linked linked list. Every node in the list contains a data element and a single reference to the next node. The nodes are "sorted," in the sense that a standard traversal of the linked list will produce a sorted sequence of all the data elements stored in the list.

This particular linked list implementation also uses a single sentinel value at the head of the list. A sentinel value is a special node that doesn't represent an actual object that is being stored in the list; rather, it helps streamline the implementation of various functions by allowing you to assume it is present rather than checking for it explicitly. For instance, you don't need any special check for an "empty" list in the add or remove functions, because you know there will always be at least one node (the sentinel) in the list.

Exercises

  • Implement the add function, which should add a new element to the list, maintaining the sorted nature of the list. Don't forget to update the size tracker!

  • Implement the contains function, which should return true if the given element is present in the list and false otherwise.

  • Implement the find function, which should return the first index of the given element if it is present in the list. If the element is not present in the list, it should return -1. What is the running time of this function?

  • Implement the remove function, which 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. If the item is not found in the list, the function should make no changes.

  • Implement the free function, which should clean up the list by deallocating all of the nodes in the list and clearing the list members.

(Challenge) Looking Forward

Consider your find implementation. Does it run faster than O(n)? Can you think of any way to make searching in this list faster?

HINT: The list is stored in sorted order; we should be able to take advantage of this fact to search more quickly.

Can we do a binary search on a linked list? If so, how? If not, is there any other way we could search the list faster?