Delete and deconstructors

[arcane]

Hello all. I'm trying writing a linked list. Everything works fine, but I don't grasp yet all of the concepts behind delete and deconstructors. I know that I am leaking memory. Here is the part of my main function (called lab5.cpp) that works with the LinkedList:

void processCommand(string command[], ofstream * out, LinkedArrayList * pointer)
{
	string commandType = command[0];
	
	if(commandType.compare("print")==0)
	{
		(*out) << "print" << endl;
		(*pointer).spillOut(out);
	}
	else if(commandType.compare("find")==0)
	{
		int place = (*pointer).find(command[1]);
		(*out) << command[0] << " " << command[1] << " " << place << endl; 
	}
	else
	{
		int a = getNumber(command[1]);
		if(commandType.compare("list")==0)
		{
			if(a>=2)
			{
				(*pointer).clear();
				(*pointer).setSize(a);
			}
			(*out) << command[0] << " " << command[1] << endl;
		}
		else if(commandType.compare("insert")==0)
		{
			(*pointer).insert(command[2], a);
			
			(*out) << command[0] << " " << command[1] << " " << command[2] << endl;
		}
		else if(commandType.compare("remove")==0)
		{
			string taken = (*pointer).remove(a);
			(*out) << command[0] << " " << command[1] << " " << taken << endl;
		}
	}
}

int getNumber(string toChange)
{
	int a = atoi(toChange.c_str());
	return a;
}

and here's the class to hold the linked list (called LinkedArrayList)

class LinkedArrayList 
{

private:

	class Node 
	{
	private:
		Node* prev;
	        int capacity;
		int filled;
		string * value;
	public:
		Node* next;
		Node(string name, int size)
		{
			next = NULL;
			prev = NULL;
			capacity = size;
			value = new string[capacity];
			value[0] = name;
			filled = 0;
		}
		
		int getFilled()
		{
			return filled;
		}
		
		
		bool findPlaceBack(string name, int location, Node * tail)
		{
			if(filled >= location || ((capacity > location) && filled + 1 ==location))
			{
				location = filled + 1 - location;
				addItem(name, location, tail);
				return true;
			}
			else
			{
				if(prev)
					prev->findPlaceBack(name, location - (filled+1), tail);
				else
					return false;
			}
		}
		

		void addItem(string name, int location, Node * tail)
		{
			if(capacity == filled + 1)
			{
				Node* newNext = new Node(value[capacity/2], capacity);
				if(next)
				{
					next->prev = newNext;
					newNext->next = next;
				}
				else
					tail = newNext;
				newNext->prev = this;
				next = newNext;
				
				placeNew(location, newNext, name);
			}
			else
			{
				for(int a = filled; a >= location; a--)
				{
					value[a+1] = value[a];
				}
				value[location] = name;
				filled++;
			}
		}
		
		
		void placeNew(int location, Node * newNext, string name)
		{
			for(int a = (capacity/2) + 1; a <=filled; a++)
			{
				newNext->value[a - (capacity/2)] = value[a];
				newNext->filled++;
			}
			filled = (capacity/2)-1;
			if(location >= (capacity/2))
			{
				for(int c = newNext->filled; c >= (location-(capacity/2)); c--)
				{
					newNext->value[c+1] = newNext->value[c];
				}
				newNext->value[location-(capacity/2)] = name;
				newNext->filled++;
			}
			else
			{
				for(int b = filled; b >= location; b--)
				{
					value[b+1] = value[b];
				}
				value[location] = name;
				filled++;
			}
		}
		
		
		bool findPlace(string name, int location, Node * tail)
		{
			if(filled >= location || ((capacity > location) && filled + 1 ==location))
			{
				addItem(name, location, tail);
				return true;
			}
			else
			{
				if(next)
					next->findPlace(name, location - (filled+1), tail);
				else
					return false;
			}
		}

		string remover(int location)
		{
			string toReturn = "";
			if(filled >= location || (capacity > location && (filled + 1) >=capacity))
			{
				toReturn = value[location];
				for(int a = location; a < filled; a++)
				{
					value[a] = value[a+1];
				}
				filled--;
			}
			else
			{
				if(next)
				{
					toReturn = next->remover(location - (filled+1));
				}
			}
			if(filled<0)
			{
				if(next)
					next->prev = prev;
				if(prev)
					prev->next = next;
			}
			return toReturn;			
		}
		
		
		int inHere(string toCheck, int currentNode)
		{
			int toReturn = -1;
			for(int a = 0; a <= filled; a++)
			{
				if(value[a].compare(toCheck)==0)
				{
					toReturn = currentNode;
					break;
				}
				currentNode++;
			}

			if(toReturn==-1)
			{
				if(next)
					toReturn = next->inHere(toCheck, currentNode);
			}
			return toReturn;
		}
		
		
		
		void showAll(ofstream * print, int place)
		{
			(*print) << "node " << place << ": ";
			for (int a = 0; a <= filled; a++)
			{
				(*print) << value[a] << " ";
			}
			(*print) << endl;
			cout << endl;
			if(next)
				next->showAll(print, place + 1);
		}
		string person()
		{
			return value[0];
		}
		
		
		
	};

	Node* head;
	Node* tail;
	int size;
	int things;

public:

	LinkedArrayList()
	{
		head = NULL;
		tail = NULL;
		size = 0;
		things = 0;
	}

	void setSize(int setSize) 
	{
		size = setSize;
	}


	void insert(string item, int index)
	{
		if(!(index > things) && !(index < 0))
		{
			if(things==0 && index==0)
			{
				head = new Node(item, size);
				tail = head;
				things++;
			}
			else 
				putInPlace(item, index);
			setTail();
		}
	}
	
	
	void putInPlace(string item, int index)
	{
		if((things/2)> index)
		{
			if(head->findPlace(item, index, tail))
				things++;
				
		}
		else
		{
			index = things-index;
			if(tail->findPlaceBack(item, index, tail))
				things++;
		}
	}
	
	
	void setTail()
	{
		Node * stat = head;
		while(!(*stat).next==NULL)
		{
			stat = (*stat).next;
		}
		tail = stat;
	}
	

	string remove(int index)
	{
		string toReturn = "";
		if(!head==NULL)
			toReturn = head->remover(index);
		if((head->getFilled())<0)
		{
			if(!(*head).next==NULL)
				head = (*head).next;
			else
			{
				head = NULL;
				tail = NULL;
			}
		}
		if(!head==NULL)
			setTail();

		if(!toReturn.compare("") == 0)
			things--;
		return toReturn;
	}
	

	int find(const string item) 
	{
		int toReturn = -1;
		if(!head==NULL)
		{
			toReturn = head->inHere(item, 0);
		}
	    return toReturn;
	}
	
	
	void spillOut(ofstream * printer)
	{
		if(!head==NULL)
			head->showAll(printer, 0);
	}


	void clear()
	{
		for(Node*n = head; n!=NULL; n = n->next)
			delete n;
		head = NULL;
		tail = NULL;
		size = 0;
		things = 0;
	}


};

and last of all, here's the report I get from Valgrind when I check for leaks

bash-4.1$ valgrind --leak-check=full ./h input.txt o.txt
==14147== Memcheck, a memory error detector
==14147== Copyright (C) 2002-2009, and GNU GPL'd, by Julian Seward et al.
==14147== Using Valgrind-3.5.0 and LibVEX; rerun with -h for copyright info
==14147== Command: ./h input.txt o.txt
==14147== 


==14147== 
==14147== HEAP SUMMARY:
==14147==     in use at exit: 168 bytes in 6 blocks
==14147==   total heap usage: 56 allocs, 50 frees, 19,022 bytes allocated
==14147== 
==14147== 168 (32 direct, 136 indirect) bytes in 1 blocks are definitely lost in loss record 5 of 5
==14147==    at 0x4A059DC: operator new(unsigned long) (vg_replace_malloc.c:220)
==14147==    by 0x401E63: LinkedArrayList::Node::addItem(std::string, int, LinkedArrayList::Node*) (LinkedArrayList.h:65)
==14147==    by 0x40228B: LinkedArrayList::Node::findPlace(std::string, int, LinkedArrayList::Node*) (LinkedArrayList.h:123)
==14147==    by 0x4028F8: LinkedArrayList::putInPlace(std::string, int) (LinkedArrayList.h:251)
==14147==    by 0x40282A: LinkedArrayList::insert(std::string, int) (LinkedArrayList.h:241)
==14147==    by 0x40198F: processCommand(std::string*, std::basic_ofstream<char, std::char_traits<char> >*, LinkedArrayList*) (fifthLab.cpp:76)
==14147==    by 0x401693: getCommand(std::string, std::basic_ofstream<char, std::char_traits<char> >*, LinkedArrayList*) (fifthLab.cpp:45)
==14147==    by 0x401463: main (fifthLab.cpp:25)
==14147== 
==14147== LEAK SUMMARY:
==14147==    definitely lost: 32 bytes in 1 blocks
==14147==    indirectly lost: 136 bytes in 5 blocks
==14147==      possibly lost: 0 bytes in 0 blocks
==14147==    still reachable: 0 bytes in 0 blocks
==14147==         suppressed: 0 bytes in 0 blocks
==14147== 
==14147== For counts of detected and suppressed errors, rerun with: -v
==14147== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 6 from 6)

 

Can anyone please help enlighten me? Thanks.

[Athar]

I see no destructor.

[arcane]

No, that's what I'm asking about. How can I use a destructor or delete to get rid of everything at the end of the program so I don't have any memory leakage?

[Athar]

For every new there must be a delete.
A destructor is called when an object is destroyed. Part of its job is to free all memory dynamically allocated by the object (if any). In this case the destructor should call clear().

[viliml]

clear() should also call delete[] value;, and in the function addItem(), a the end of the first if block, add a delete[] newNext;

[arcane]

Those lines didn't help. I've rearranged my code and put in where I think deletes should go as comments, but if I uncomment any of them I have a crash on compiling. How should I be doing these?
Here's the updated LinkedArrayList and Node classes

#include <cstdlib>
#include <string>
#include <iostream>
#include <sstream>
#include <fstream>
#include <istream>

#pragma once

using namespace std;

class LinkedArrayList 
{

private:

	class Node 
	{
	public:
		Node* next;
		Node* prev;
	    int capacity;
		string * value;
		int filled;
		Node(string name, int size)
		{
			next = NULL;
			prev = NULL;
			capacity = size;
			value = new string[capacity];
			value[0] = name;
			filled = 0;
		}

		~Node()
		{
			//delete[] value;
		}


		int getFilled()
		{
			return filled;
		}

		int inHere(string toCheck, int currentNode)
		{
			int toReturn = -1;
			for(int a = 0; a <= filled; a++)
			{
				if(value[a].compare(toCheck)==0)
				{
					toReturn = currentNode;
					break;
				}
				currentNode++;
			}

			if(toReturn==-1)
			{
				if(next)
					toReturn = next->inHere(toCheck, currentNode);
			}
			return toReturn;
		}
		void showAll(ofstream * print, int place)
		{
			(*print) << "node " << place << ": ";
			for (int a = 0; a <= filled; a++)
			{
				(*print) << value[a] << " ";
			}
			(*print) << endl;
			if(next)
				next->showAll(print, place + 1);
		}
		string person()
		{
			return value[0];
		}
		
	};

	Node* head;
	Node* tail;
	Node* newNext;
	int size;
	int things;

public:

	LinkedArrayList()
	{
		head = NULL;
		tail = NULL;
		newNext = NULL;
		size = 0;
		things = 0;
	}

	void setSize(int setSize) 
	{
		size = setSize;
	}


	void insert(string item, int index)
	{
		if(!(index > things) && !(index < 0))
		{
			if(things==0 && index==0)
			{
				head = new Node(item, size);
				tail = head;
				things++;
			}
			else 
				putInPlace(item, index);
			setTail();
		}
	}


	void putInPlace(string item, int index)
	{
		if((things/2)> index)
		{
			if(findPlace(item, index, head))
				things++;
				
		}
		else
		{
			index = things-index;
			if(findPlaceBack(item, index, tail))
				things++;
		}
	}

	bool findPlaceBack(string name, int location, Node * c)
	{
		if(c->filled >= location || ((c->capacity > location) && c->filled + 1 ==location))
		{
			location = c->filled + 1 - location;
			addItem(name, location, c);
			return true;
		}
		else
		{
			if(c->prev)
				findPlaceBack(name, location - (c->filled+1), c->prev);
			else
				return false;
		}
	}


	bool findPlace(string name, int location, Node * c)
	{
		if(c->filled >= location || ((c->capacity > location) && c->filled + 1 ==location))
		{
			addItem(name, location, c);
			return true;
		}
		else
		{
			if(c->next)
				findPlace(name, location - (c->filled+1), c->next);
			else
				return false;
		}	
	}

	void addItem(string name, int location, Node * c)
	{
		if(c->capacity == c->filled + 1)
		{
			newNext = new Node(c->value[(c->capacity)/2], c->capacity);
			if(c->next)
			{
				c->next->prev = newNext;
				newNext->next = c->next;
			}
			else
				tail = newNext;
			newNext->prev = c;
			c->next = newNext;
			placeNew(location, newNext, name, c);
			//newNext->~Node();
			newNext = NULL;					
		}
		else
		{
			for(int a = c->filled; a >= location; a--)
			{
				c->value[a+1] = c->value[a];
			}
			c->value[location] = name;
			c->filled++;
		}
	}

	void placeNew(int location, Node * newNext, string name, Node * c)
	{
		int half = (c->capacity)/2;
		for(int a = half + 1; a <=c->filled; a++)
		{
			newNext->value[(a - half)] = c->value[a];
			newNext->filled++;
		}
		c->filled = half-1;
		if(location >= half)
		{
			for(int d = newNext->filled; d >= (location-half); d--)
			{
				newNext->value[d+1] = newNext->value[d];
			}
			newNext->value[location-half] = name;
			newNext->filled++;
		}
		else
		{
			for(int b = c->filled; b >= location; b--)
			{
				c->value[b+1] = c->value[b];
			}
			c->value[location] = name;
			c->filled++;
		}
	}

	void setTail()
	{
		Node * stat = head;
		while(!(*stat).next==NULL)
		{
			stat = (*stat).next;
		}
		tail = stat;
	}

	string remove(int index)
	{
		string toReturn = "";
		if(!head==NULL)
			toReturn = remover(index, head);
		if((head->getFilled())<0)
		{
			if(!(*head).next==NULL)
				head = (*head).next;
			else
			{
				head = NULL;
				tail = NULL;
			}
		}
		if(!head==NULL)
		 setTail();

		if(!toReturn.compare("") == 0)
			things--;
		return toReturn;
	}

	string remover(int location, Node * c)
	{
		string toReturn = "";
		if(c->filled >= location || (c->capacity > location && (c->filled + 1) >=c->capacity))
		{
			toReturn = c->value[location];
			for(int a = location; a < c->filled; a++)
			{
				c->value[a] = c->value[a+1];
			}
			c->filled--;
		}
		else
		{
			if(c->next)
			{
				toReturn = remover(location - (c->filled+1), c->next);
			}
		}
		if(c->filled<0)
		{//need to do some deleting in here
			if(c->next)
				c->next->prev = c->prev;
			if(c->prev)
				c->prev->next = c->next;
			c->~Node();
			//delete c;
		}
		return toReturn;			
	}




	int find(const string item) 
	{
		int toReturn = -1;
		if(!head==NULL)
		{
			toReturn = head->inHere(item, 0);
		}
	    return toReturn;

	}
	void spillOut(ofstream * printer)
	{
		if(!head==NULL)
			head->showAll(printer, 0);
	}


	~LinkedArrayList()
	{
		for(Node * n = head; n!=NULL; n = n->next)
		{
			(*n).~Node();
			delete n->prev;
		}
		//delete tail;
	}


};

[helios]

Every statement of the form
x->~Node();
or
(*x).~Node();
is incorrect. You're not supposed to manually call destructors. For automatic objects, the compiler will generate the call to the destructor for you. For dynamically allocated objects, the use of delete also calls the destructor.