In this practical you will complete exercises intended to review your pointer-based programming in C++. The exercises will also give you an appreciation of the impact of the underlying data structure on the performance of an implementation.

Download the file binarySearches.cpp in which you will find a partically completed program file.

1. Implement the function insert which inserts a node at the head of a list.

2. Implement the function binarySearchLinked.

3. Compare experimentally the two functions binarySearchLinked and binarySearch. You must write a small function which creates an ordered linked list of nodes and run your function for a number of sizes of list. Do a similar test for binarySearch. Plot the two graphs and add it to your portfolio; include a short explanation of why the graphs are different (if they are).

   Submit your completed program file binarySearches.cpp by Monday of Week3. Your experiments will be marked later when you hand in your portfolio with your assignment.

   All enquiries to Annabelle McIver