Question

Data Structures using C++

Searching a Linked List

Here are the declarations for a simple unsorted linked list of ints that ends in a null pointer.

//===============================================================

class Cell {

friend class UList;

private:

int data;

Cell* next;

Cell( int dt, Cell* nx=nullptr ) : data(dt), next(nx) {}

};

//===============================================================

class UList {

private:

Cell* head = nullptr;    // stationary head pointer.

Cell* scan = nullptr;          // for walking down the List.

Cell* follow = nullptr;

public:

void find( int key );

A. (2) Given an unsorted list with n names in it, how many comparisons would you make when searching for a name in the list, if the name is not there? What is the big-O of the search function?
B. (2) Given a sorted alphabetical list with n names in it, how many comparisons would you make when searching for a name in the list, if the name is not there? What is the big-O of the search function?
C. (3) Write the entire definition of an appropriate Cell destructor.
D. (6) Assume that ls is a Ulist that contains at least one Cell. Write the code for the find( int key ) function to use the pointers scan and follow. When find() exits, scan must point AT the cell that contains the key value (if such a cell exists) or at the nullptr that ends the list.

Answer 1