L21 - operator= in Linked List and Recursion

#ece244

Recall from L19's linked list class definition:

#include 'Node.h'

class List {
	private:
		Node* head;
		int data;
	public:
		List() { head = NULL; } // default constructor; set head to NULL
		~List() { delete head; } // destructor; deallocate head node
		void insertData(int d); // insert data into the linked list
		bool dataExists(int d); // search list for data and return bool
		bool deleteData(int d);
		// delete data from list; returns bool for existence of data
		List (const List&); // copy constructor
		List& operator=(const List&); // operator= definition
}

operator= in a linked list

Recall from L14, the operator= operator sets the LHS values equal to the RHS values. However, normally this would just copy over pointers and not the values at the pointers, so modifying the values at those pointers would affect both RHS and LHS. So, we should define our own operator=. This is very similar to the copy constructor, but we also need to deallocate whatever is at the original linked list, instead of allocating an entirely new linked list. We must consider the following cases:

• both the RHS and LHS are the same
  • just return *this (dereferenced pointer to LHS)
• if the LHS is empty (head == NULL)
  • invoke the copy constructor
• if the LHS has values
  • deallocate the entire LHS first (calls ~List(), which deallocates head, which then recursively deallocates each node)
  • invoke the copy constructor

List& List::operator=(const List& rhs) {
	// 1. first, check for self-assignment between RHS and LHS
	if (&rhs == this) { // invokes &rhs.operator==(this)
		return *this;
	}
	
	// 2. free the old list, if there exist nodes in 'this' already
	if (head != NULL) {
		delete head; // recursively deletes each node in the linked list
		head = NULL;
	}
	
	// 3. copy the RHS list to the LHS
	// same as copy constructor code
	
	Node *p = original.head;
	Node *np = NULL;

	while (p != NULL) {
		Node *n = new Node(p->getData(), NULL);
		if (np == NULL) { // make the first node the head
			head = n;
		} else { // if np is already a non NULL node pointer
			np->setNext(n); // set the next of previous node to new node
		}
		p = p->getNext(); // shift p along original list
		np = n; // make np the current node
	}
	
	return *this;
}

Notes:

• Function header:
  • Return type is List& because operator= is called on a pre-existing Linked List
  • (const List& rhs) is the parameter, we include const because we do not wish to modify the RHS list. Also, we use List& as a memory-saving technique.
• if (&rhs == this) { ... } invokes the default operator== operator, which sees if the LHS and RHS objects are located at the same memory address. See: L14.

  However, invoking this comparison on two linked lists with identical values that are stored in completely separate memory would return false, as it is only checking for self-assignment.

• again, we return *this to allow for chained assignments; we are modifying the LHS directly

recursion

The definition in C++, of course, is the exact same. Let's go through some examples together.

recursion example 1: find factorial

Let's write a function that finds the factorial of an integer. We did this in APS105 too!

We can implement this recursively by multiplying by n each time.

• Recursive call: if n > 1, return from function n * factorial(n-1)
• Base case: when $n=1$ or $n=0$, return $1$

#include <iostream>
using namespace std;

int factorial(int n) {
	if (n > 1) {
		return factorial(n-1) * n;
	}
}

int main(void) {
	int n = 4;
	cout << "Factorial of " << n << " is " << factorial(n) << endl;
	return 0;
}