L20 - Ordered Linked List Copy Constructor

#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
}

copy constructor for an ordered linked list

Recall from L15 that copy constructors are not the same as operator=; while both copy the values to a new object, rather than letting them point to the original object, the copy constructor copies to an entirely new object. Furthermore, we would like for the actual values stored at the pointers (nodes) to be copied, rather than the pointers themselves. Thus, we would like to define our own copy constructor! We would like to make it do a deep copy, rather than the default shallow copy.

• Copy one node at a time
• use p to iterate through original list, and np to build up the new linked list

Implementation:

List::List(const List& original) {
	Node *p = original.head;
	Node *np = NULL;
	head = NULL; // setting the head of the new list to NULL by default
	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
	}
}