1
h05
CS24 S19
Name:
(as it would appear on official course roster)
Umail address: @umail.ucsb.edu section
Optional: name you wish to be called
if different from name above.
Optional: name of "homework buddy"
(leaving this blank signifies "I worked alone"

h05: Chapter 9: Recursion

ready? assigned due points
true Wed 05/01 02:00PM Tue 05/07 09:00AM

You may collaborate on this homework with AT MOST one person, an optional "homework buddy".

MAY ONLY BE TURNED IN IN THE LECTURE/LAB LISTED ABOVE AS THE DUE DATE,
OR IF APPLICABLE, SUBMITTED ON GRADESCOPE. There is NO MAKEUP for missed assignments;
in place of that, we drop the lowest scores (if you have zeros, those are the lowest scores.)


Please:

  • No Staples.
  • No Paperclips.
  • No folded down corners.

Complete your reading of Chapter 9 (If you don’t have a copy of the textbook yet, there is one on reserve at the library under “COMP000-STAFF - Permanent Reserve”).

    1. (15 pts) Consider the following definition of a doubly linked-list.
    class LinkedList{
    	public:
    		LinkedList():head(0), tail(0){}
    		~LinkedList();
    		void reverse(); 
    		//reverses the order of elements in the linked list
    		void insert(int value);
    	private:
    	    struct Node{
      			int data;
      			Node* next;
      			Node* prev;
    		};
    		Node* head;
    		Node* tail;
    		//Add your helper function here that recursively reverses the order of elements in the linked list
    
    
    };
    
    Write the declaration of a helper function in the class provided above that recursively reverses the order of elements in the linked list. This function will be used by the reverse() method. The implementation of the function should be provided on the next page.
    2. (25 pts) Consider the doubly linked list in the previous question. Implement the reverse method that uses a helper function to recursively reverse the order of elements in a linked list. You must implement the helper function as well.