CPSC170
Fundamentals of Computer Science II

Recursive view lists

A list is a recursive structure. A recursive structure is a structure that can be defined in terms of itself. This can be seen in the definition of the Node struct template we viewed in the last lab. Here's a stripped down version of Node that highlights the recursive structure of lists.

template <typename T>
struct Node{
  T _data;                
  Node<T>* _next;
}

Can you see why this is a recursive structure? In the Node struct, we have a pointer to a Node struct. This definition is sound because, _next is a pointer (address) to a Node object. If _next was a Node object, then we would have a circular definition (a mathematical sin!), which cannot be created, let alone compiled.

Recursive code can be especially simple and elegant for recursive structures. In this lab you will implement some of these functions. This isn't meant to be an efficient implementation of a linked list, instead, this is an inefficient but simple implementation.

Now let's get down to the recursive view of a list. A list L has two forms. L is either the empty list [], or L has the form: a T, where a is the first element of the list (head), T is the tail of the list, it is the list of all the elements that follow a. In other words, a list is either the empty list, or a list with at least one element. When a list has at least one element, it can be broken down into two parts: the first element in the list (a) and the elements that follow the first element (T). For example, the list L = 1 2 can be written as L = 1 T, where T = 2. The list T can be written as T = 2 S, where S = [] is the empty list. Hopefully, you're convinced that every list is either the empty list, or can be written as the first element of the list, followed by a list of elements that follows the first element.

Now let's see how this characterization of lists can help us write very simple and elegant recursive code. Since we now know that there are only two types of list, we can write code with an if-else statement that handles each type of list. So, our code will look something like:

procedure(list L)
  if(L is empty){
    do_something;
	return something or nothing;
  }
  else{ //ASSERT: L has the form a T
	procedure(T);
        if you want to, do something with the previous result;
	return something or nothing;
  }

First, lets convince ourselves that such a function will eventually terminate. We can see that the if-statement terminates since it doesn't make any recursive calls. Second, the recursive call (else-statement) is always made on a smaller list, in fact, the size of the list is reduced by one for each recursive call, therefore the function will terminate once we hit the empty list. Notice the similarity between this and the recursive code we've seen in the past. In the code we saw before, we had numbers that got smaller, in this case we have a structure that is getting smaller.

Let's make a size function using the above template. The size of a list L is is the number elements in the list. We have to consider the two types of lists. What is size(L) when L is the empty list? I hope you shouted zero. What is size(L) when L has the form a T? This slightly trickier but still simple. First we count the element a, then we count the number of elements in T. Then the size of L will be the sum of both numbers. In other words size(L) = 1 + size(T). Just like the typical recursive code, we know we will get the correct answer for size(T) because the size of T is smaller than that of L. Here's what the size function will look like.

size(list L)
  if(L is empty){
	return 0;
  }
  else{ //ASSERT: L has the form a T
	return 1 + size(T);
  }

Now let's see how we can do all this in C++. Our lists will be represented by pointers, the empty list by the null pointer nullptr, a non-empty list by a pointer to a Node object. We create a class template called List with one data member, a pointer to a Node. As mentioned in the previous lab, the Node struct will be a private inner struct. Here's the list template class with only data members and constructors.

template <typename T>
class List{

  /*CI: Every variable of type Node* is
        either nullptr or points to an
        valid Node object.
  */

  struct Node{ // private inner node struct.
    T _data;
    Node* _next;

    Node(const T& data = T{}, Node* next = nullptr) // constructor for Node struct.
      :_data{data}, _next{next}{ }
  };
  
  Node* lst; // pointer to the head of the list.
  
public:

  List():lst{nullptr}{} // creates the empty list.
};

lst is a pointer to the head of the list. When lst is nullptr, the list is empty, otherwise, it contains at least one element.

Printing

To print each element of the list also breaks down into two cases, the empty and non-empty list. We could easily make a recursive function, but, the format I want the list printed in makes things slightly more complicated. So, we will print the non-empty list iteratively. The comments in the following code explain how the list is printed.

//PRE:
//POST: Prints this list to out.
void print(ostream& out) const{
    if(lst == nullptr){ // ASSERT: the list is empty.
      out << "[]";
      return;
    }

    //ASSERT: the list is non-empty.
    Node* current = lst;           // current points to the first element in the list.
	
    out << "[" << current->_data; // prints the first element.
    current = current->_next;     // sets current to the next element in the list.
    
    while(current != nullptr){    // loop prints all the elements following the first element.
      out << ", " << current->_data;
      current = current->_next;   // sets current to the next element in the list.
    }

    cout << "]";
  }

Insertion

The easiest place to insert an element in a singly linked list is at the front (why?). All we have to do is create a new node, set that node's pointer to the head of the current list (lst), then update the head to point to the new node. All this can be done in a single line of code. I will also present the longer version.

//short and beautiful.
//PRE:
//POST: A node with _data set to data has been added to the front of the list.
void push_front(const T& data){
    lst = new Node(data, lst);
}

//long version.
//PRE:
//POST: A node with _data set to data has been added to the front of the list.
void push_front(const T& data){
    Node* new_node = new Node(data); // create a new node.
    new_node->_next = lst;           // set new_node to point to the head of the old list.
    lst = new_node;                  // update lst to point to new_node, the front of the list.
}

Deleting

When we inserted a node, we created the node on the heap. So, when we remove a node we need to free up the space it occupied. Just like, insertion, the easiest place to remove a node in a singly linked list is from the front (why?).

//PRE:
//POST: If the list wasn't empty, the head has been removed,
//      otherwise, an UnderflowException is thrown.
void pop_front(){
    if(empty()){
      throw UnderflowException{};
    }
    else{
      Node* tmp = lst;  // temporarily hold a pointer to the current head of the list. 
      lst = lst->_next; // update the head of the list to the next node. 
      delete tmp;       // free up the space of the former head.
    }
  }

Destructor

When a list is destroyed, we need to free up all the stack space it was allocated. We can do this iteratively, going through each node from first to last and freeing up each node. But we will do it recursively. Since we can't call List's destructor recursively, we will do the recursion with a private helper called free. free will use the recursive strategy we developed above. When the list is empty (i.e. nullptr) we do nothing since there no memory to be freed. Otherwise, when the list has at lease one node, we first free up the tail (all nodes following the head) of the list (why?), then we free up the head.

//PRE:
//POST: The heap space allocated by the list pointed to by node is freed.
void free(Node* node){
    if(node == nullptr){ //ASSERT: list is empty.
      return;            //nothing to do here.
    }
    else{                //ASSERT: list is not empty.
      free(node->_next); //free up the tail.
      delete node;       //free up the head.
    }
  }

Simplify free to be an if-statement without the else part. Now we can implement our destructor by calling free on the head of the list.

//PRE:
//POST:
~List(){
   free(lst); 
}

Exercise (Exam questions?)

Create an empty function. It should return true if and only if the list is empty. It should be a one line non-recursive function.

Create a size function for the list class. This function should use a private recursive helper. The helper should have the header/signature unsigned size(Node* node) const. Then the public function will be:

//PRE:
//POST: returns the size of the list.
unsigned size()const{
   return size(lst); 
}

In the following functions, use private recursive helpers in your implementation. Your implementation should be similar to the size function.

Create a contains function. It should take a target tar and return true if and only if the list contains tar.

Create a count function. It should take a target tar and return the number of times tar occurs in the list.

Create an equals function. It should take a list and return true if and only if the two lists are equal. Uses this function to implement the operator ==.

Create a push_back function. It should take data object d and insert a node containing d to the back of the list. The recursive helper function needs to take the node pointer by reference. This is because the function needs to be able to make changes to the pointer given.

Use the push_back function to implement a copy constructor. This function should be iterative.