CIS22C‎ > ‎22C Class Schedule‎ > ‎


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


        /**Additional Operations*/     

        void print_reverse();
        //Calls the reverse helper function to print a list in reverse
        //prints nothing if the List is empty

        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