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

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"<

return;

}

do{

cout<getVal();

cout<<" -->";

tmp=tmp->getNext();

}while (tmp!=NULL);

cout<<"NULL"<

}

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: