Part 1: Adding Some List Operations
Printing a Linked List in Reverse
- Write the following functions as part of your doubly linked list class.
- You will need to add the prototypes inside of your List class definition.
- Then, implement the functions below the List class inside of List.h
public: /**Additional Operations*/
void print_reverse();
//Calls the reverse helper function to print a list in reverse
//prints nothing if the List is empty
private: void reverse(NodePtr node);
//Helper function for the public printReverse() function.
//Recursively prints the data in a List in reverse.
- Why do we need the private helper function here?
- Since
we are going to be reversing our list node by node, in a recursive
fashion, we want to pass a one node at a time to our reverse
function.
- However, since our nodes are private, we cannot access them if we call the function inside of main.
- Now, test your function inside of ListTest.cpp to verify that it is working.
Adding an Index to Our List
- While arrays have a built-in index, we can add an index to our list by adding just two functions.
- Since
we will be using these functions for search (below), we will assume
that the index will go from 1 to the length of the list.
- See the image below to help you visualize the index.
- Note that the index is not stored, but must be counted each time that get_index is called.
/**Accessor Functions*/
int get_index();
//Indicates the index of the Node where the cursor is currently pointing
//Nodes are numbered from 1 to size of the list
//Does not need to be implemented recursively
//Pre: !off_end()
/**Manipulation Procedures*/
void scroll_to_index(int index);
//Moves the cursor to the node whose index is specified by the user
//Does not need to be implemented recursively
//Pre: !empty()
- Now test your functions inside of ListTest.cpp
Implementing Search as Part of Our List Operations
- To
help you gain a better understanding of the binary and linear search
functions discussed in class, you will write these functions as part of
your List class for this Lab.
- The pseudocode for both functions is provided during Thursday's lesson 8
- All you will need to do is to implement it.
- Note
that binary search assumes a sorted List. Thus, to test this function,
you must create a List and add values to it in a way that is sorted.
- Note 1: You must use the above functions -- getIndex and scrollToIndex -- in your implementation of the binary search function.
- Note 2: Be able to answer this question: Do you think that binary search is efficient for a Linked List?
/**Access Functions*/
int linear_search(listitem value);
//Searchs the list, element by element, from the head of the List to the tail of the List
//Returns the index of the value, if it is found in the List
//Returns -1 if the element is not in the List
//Does not need to be implemented recursively
//Pre: !empty()
int binary_search(int low, int high, listitem value);
//Recursively searchs the list by dividing the search space in half
//Returns the index of the value, if it is found in the List
//Returns -1 if the value is not in the List
//Pre: !empty()
//Pre: List is sorted. Note that you cannot test this with an if statement.
//Assumes list is sorted when the function is called.
- Now test your functions inside of ListTest.cpp
|
|
