Week 6 Lab—Virtual Memory

TCO 9—Given the need to support the runtime creation of varying quantities of data objects, learn how dynamic memory allocation can provide this capability in a very efficient way.
TCO 8—Given the need to understand virtual memory, describe how memory allocation and paging are used to give a computer program access to more memory than physically available.

Scenario 
In this week’s lab, you will override the new and delete operators for an implementation of linked list. 

Rubric

Point distribution for this activity
Lab Activity	
Document	Points possible	Points received	
Code and screenshot	40		
Total Points	40		

Generally, the default implementation of new and delete is sufficient for a given program. At times, you may want to specialize memory allocation for advanced tasks. You may want to allocate instances of a certain class from a particular memory pool, implement your own garbage collector, or caching. 

We will override the new and delete operator in this lab. When overriding these operators, both need to be overridden. The new operator allocates memory and creates an object. The delete operator deallocates memory.

We will be implementing a linked list class and overloading the new and delete operator. We can improve the speed of allocating new nodes by keeping a list of deleted nodes and reusing the memory when new nodes are allocated. 
The code for the linked list is below. You may also use your own implementation of linked list. 
The overloaded new operator will check a freelist to recycle a node before going to the heap and getting one that way. The delete operator will add the node to the freelist. 
Hint: Use the following in the Node class.
void * operator new(size_t);
void operator delete(void*);
static void printFreelist();
After the class Node definition, be sure to set the freelist to NULL.
Node* Node::freelist=NULL;

Implement Node::printFreelist() as well, and in the Main, include calls to 
Node::printFreelist();
to see the nodes in the free list.
Original C++ Code:
#include <iostream>
using namespace std;

//looks like this:
// ---------              ---------
// -  x    -              -   x  -
// ---------              ---------
// -Pointer-  -------->   -Pointer-
// ---------              ----------
//
//Individual node class. Contains one integer x value and a pointer to the next node
class Node
{
private:
	int x;
	Node* next;
public:
	Node() {};
	Node(int y) {x=y; next=NULL;}
	static Node* freelist;
	void setVal(int data) { x = data; }
void setNext(Node* aNext) { next = aNext; }; 
int getVal() { return x; }; 
Node* getNext() { return next; }; 

};

//Linked List class. Contains head node which is initially set to null
class LinkedList
{
private:
	Node *head;
public:
	LinkedList(){head = NULL;};
		void Print();
	void Append(int y);
	void Delete (int y);
};

//Append a node to the list
void LinkedList::Append(int y)
{
	//Create a new node and set the integer data value
	Node* newNode = new Node();
	newNode->setVal(y);
	newNode->setNext(NULL);

	Node *tmp=head;//Create a temp pointer

	//Search through the list
	if(tmp!=NULL) {
		while(tmp->getNext()!=NULL){
			tmp = tmp->getNext();
		}
		// point the last node to the new node
		tmp->setNext(newNode);
	}
	else{
		//First node in the linked list
		head = newNode;
	}

}

//Delete a node from the list
void LinkedList::Delete(int y) { 
	Node *tmp =head; //Create a temp pointer
	if(tmp==NULL) //No nodes
		return;

	if(tmp->getNext()==NULL) //Last node
	{
		delete tmp;
		head = NULL;
	}
		else{
	Node * curr;
	//Search through nodes
	while(tmp!=NULL)
	{
		if(tmp->getVal()==y)
			break;
		curr=tmp;
		tmp=tmp->getNext();
	}

	curr->setNext(tmp->getNext());
	delete tmp; //delete current node
		}

}

void LinkedList::Print()
{
	Node *tmp=head;
      if(tmp==NULL)
	  {
		  cout<<"Empty"<<endl;
		  return;
	  }
	  do{
		  cout<<tmp->getVal();
		  cout<<" -->";
		  tmp=tmp->getNext();
	  }while (tmp!=NULL);
	  cout<<"NULL"<<endl;
}

int main()
{
	LinkedList newLinkedList;
	newLinkedList.Append(42);
	newLinkedList.Print();
		newLinkedList.Append(17);
	newLinkedList.Print();
		newLinkedList.Append(21);
	newLinkedList.Print();
		newLinkedList.Append(1701);
	newLinkedList.Print();
	newLinkedList.Delete(1701);
	newLinkedList.Print();
		newLinkedList.Delete(17);
	newLinkedList.Print();
		newLinkedList.Delete(21);
	newLinkedList.Print();
		newLinkedList.Delete(42);
	newLinkedList.Print();
	newLinkedList.Append(42);
	newLinkedList.Print();
		newLinkedList.Append(17);
	newLinkedList.Print();
		newLinkedList.Delete(17);
	newLinkedList.Print();
		newLinkedList.Delete(42);
	system("pause");
}

Implementation with overloaded new and delete:
C++ Code:

Screenshot: