Okay, so i'm making a custom linked list class using templates, and i'm having a problem when removing elements from it, more specifically at the delete instruction.
Here's the code for the class
#ifndef _LINKED_LIST_H_
#define _LINKED_LIST_H_
#include <cstring>
template <typename Type>
struct sNode
{
//Pointer to the next element
sNode *next;
//This element's data
Type data;
};
template <typename Type>
class LinkedList
{
//Public Properties
public:
//Private Properties
private:
//The root element
sNode<Type> *first;
//The last element
sNode<Type> *last;
//The number of elements
unsigned short numNodes;
//Public Methods
public:
//Default constructor
LinkedList();
//Destructor
~LinkedList();
//Add an element (empty)
bool Insert(Type **address);
//Removes an element
bool Remove(Type **address);
//DEBUG: Dump the linked list
void Dump();
//Private Methods
private:
};
//-------------------- Constructor / Destructor --------------------
template <typename Type>
LinkedList<Type>::LinkedList()
:first(NULL),
last(NULL),
numNodes(0)
{
}
template <typename Type>
LinkedList<Type>::~LinkedList()
{
//TODO: Clear the list here!
}
//-------------------- Public Methods --------------------
template <typename Type>
bool LinkedList<Type>::Insert(Type **pAddress)
{
//Check if there are no elements
if(!this->first)
{
//Allocate space for the new element
this->first = new sNode<Type>;
//The first element is also the last
this->last = this->first;
//Set the pointer to this struct (to return)
(*pAddress) = &this->first->data;
//OPT: Initialize data to 0
memset(&this->first->data, 0, sizeof(sNode<Type>));
//OPT: Set 'next' pointer to NULL
this->first->next = NULL;
this->last->next = NULL;
}
//There's already at least an element
else
{
//Allocate space for the new element
this->last->next = new sNode<Type>;
//Point to the last
this->last = this->last->next;
//Set the pointer to this struct (to return)
(*pAddress) = &this->last->data;
//OPT: Initialize data to 0
memset(&this->last->data, 0, sizeof(sNode<Type>));
//OPT: Set 'next' pointer to NULL
this->last->next = NULL;
}
//Update the number of elements
this->numNodes++;
return true;
}
//Removes an element
template <typename Type>
bool LinkedList<Type>::Remove(Type **pAddress)
{
//Check for NULL address
if(!(*pAddress))
return false;
//---------- Check if the 1st element matches ----------
//Check if the 1st DATA address matches the given address
if(&this->first->data == *pAddress)
{
//VAR: Pointer to the current node on the list
sNode<Type> *ptr = this->first->next;
//Delete the element
delete this->first;
this->first = NULL;
//Set the next element as the next
this->first = ptr;
//Update the node counter
this->numNodes--;
//Set the address to NULL
(*pAddress) = NULL;
return true;
}
//---------- Check if any other element matches ----------
//VAR: Pointer to the current node on the list
sNode<Type> *ptr = this->first->next;
//VAR: Pointer to the 2nd to current node on the list
// Will be used for pointing to the element after the one deleted
sNode<Type> *last = this->first;
//Loop through the list until the node is found (IF it is found)
do
{
//Check if the addresses match
if(&ptr->data == *pAddress)
{
//VAR: Pointer to the next element
sNode<Type> *nex = ptr->next;
//Delete the element
delete ptr;
ptr = NULL;
//Set the element before, point to the next
last->next = nex;
//Update the node counter
this->numNodes--;
//Set the address to NULL
(*pAddress) = NULL;
return true;
}
//The address didn't match, so update the pointers
last = ptr;
ptr = ptr->next;
}
while(ptr->next);
//---------- Check if the last element matches ----------
//Check if the addresses match
if(&ptr->data == *pAddress)
{
//Delete the element
delete ptr;
ptr = NULL;
//Point to the last element
this->last = last;
//Set the element before, point to the next
last->next = NULL;
//Update the node counter
this->numNodes--;
//Set the address to NULL
(*pAddress) = NULL;
return true;
}
return false;
}
//DEBUG: Dump the linked list
template <typename Type>
void LinkedList<Type>::Dump()
{
printf("Nodes: %i\n", this->numNodes);
sNode<Type> *ptr = this->first;
while(ptr)
{
printf("PTR: 0x%08X NEXT: 0x%08X DADR: 0x%08X DATA: %i\n", ptr, ptr->next, &ptr->data, ptr->data);
ptr = ptr->next;
}
}
//-------------------- Private Methods --------------------
//-------------------- Get / Set --------------------
#endif //_LINKED_LIST_H_
And, if it help, here's the main
#include <cstdio>
#include <conio.h>
#include "LinkedList.h"
int main()
{
LinkedList<int> my;
int *ptr1 = NULL;
int *ptr2 = NULL;
int *ptr3 = NULL;
int *ptr4 = NULL;
//printf("Nodes: %i\n", my.numNodes);
my.Insert(&ptr1); *ptr1 = 333;
printf("ADR: 0x%08X PNT: 0x%08X VAL: %i\n", &ptr1, ptr1, *ptr1);
my.Insert(&ptr2); *ptr2 = 666;
printf("ADR: 0x%08X PNT: 0x%08X VAL: %i\n", &ptr2, ptr2, *ptr2);
my.Insert(&ptr3); *ptr3 = 999;
printf("ADR: 0x%08X PNT: 0x%08X VAL: %i\n\n", &ptr3, ptr3, *ptr3);
my.Remove(&ptr3);
my.Insert(&ptr4); *ptr4 = 1222;
printf("ADR: 0x%08X PNT: 0x%08X VAL: %i\n\n", &ptr4, ptr4, *ptr4);
//my.Remove(&ptr3);
my.Dump();
_getch();
return 0;
}
Now the problem is that when calling the Remove method, when the program reaches the delete instruction (any of them) it crashes with the error "Heap corruption detected".
I don't know if i'm just fed up with pointers, that i can't find the error, or if it is something else, so please help.
NOTE: I know that there are already Linked List classes, and that the way i made it may not (and probably isn't) be the best way to do it, but try to bear with it.
Thanks in advance.