Problem with Linked List

[oceanspell]

I made a linked list that can add an item, go to the first item, and
get the current, next, and previous item in the list. When I compile
it, there are no errors, but it overloads. Here is the code:

//fnamelink.h------------------------------------------------------
class flink
{
public:
char data[_MAX_DIR+1];
flink* previous;
flink* next;
flink()
{
previous = NULL;
next = NULL;
}
};

class fnamelink
{
private:
flink* first;
public:
fnamelink()
{ first = NULL; }
void addItem(char* foldername);
char* getCurrent();
char* getPrevious();
char* getNext();
char* getFirst();
void deleteLink();
~fnamelink()
{
getFirst();
deleteLink();
}
};



//
fnamelink.cpp-------------------------------------------------------------------------------------------------
#include <string.h>
#include <malloc.h>
#include "StdAfx.h" //<--Includes #include "fnamelink.h"

void fnamelink::addItem(char* foldername)
{
flink* newlink = new flink;
memset(newlink->data, NULL, sizeof(newlink->data));
strcpy(newlink->data, foldername);
newlink->previous = first;
if(first)
first->next = newlink;
first = newlink;
}

char* fnamelink::getCurrent()
{
flink* current = first;
if(current != NULL)
return current->data;
else
return NULL;
}

char* fnamelink::getPrevious()
{
flink* current = first;
current = current->previous;
if(current->previous == NULL)
{
first = current;
return NULL;
}
if(current->previous != NULL)
return current->data;
else
return NULL;
}

char* fnamelink::getNext()
{
flink* current = first;
if((current = current->next) == NULL)
{
return NULL;
}
if(current != NULL)
return current->data;
else
return NULL;
}

char* fnamelink::getFirst()
{
flink* current = first;
if(current)
{
=> while(current->previous != NULL)
{
current = current->previous;
}
}
first = current;
if(first)
return first->data;
else
return NULL;
}

void fnamelink::deleteLink()
{
int numToDel = 0;
flink* current = first;
if(current->next)
{
while(current->next != NULL)
{
current = current->next;
first = current;
numToDel++;
}
while((numToDel) >= 0)
{
numToDel--;
first = first->previous;
free(current);
current = first;
}
free(current);
}
else
{
first = first->previous;
free(current);
}
}


The '=>' I placed in the code was the exception the debugger pointed
out, but I can't seem to find a problem with it. Any help would be
greatly appreciated.

 

[Howard]

flink* newlink = new flink;

free(current);

When you allocate using new, you de-allocate using delete, not free.

(I haven't checked for any other errors.)

-Howard

 

[Jim Langston]

I made a linked list that can add an item, go to the first item, and
get the current, next, and previous item in the list. When I compile
it, there are no errors, but it overloads. Here is the code:

//fnamelink.h------------------------------------------------------
class flink
{
public:
char data[_MAX_DIR+1];
flink* previous;
flink* next;
flink()
{
previous = NULL;
next = NULL;
}
};

class fnamelink
{
private:
flink* first;
public:
fnamelink()
{ first = NULL; }
void addItem(char* foldername);
char* getCurrent();
char* getPrevious();
char* getNext();
char* getFirst();
void deleteLink();
~fnamelink()
{
getFirst();
deleteLink();
}
};



//
fnamelink.cpp-------------------------------------------------------------------------------------------------
#include <string.h>
#include <malloc.h>
#include "StdAfx.h" //<--Includes #include "fnamelink.h"

void fnamelink::addItem(char* foldername)
{
flink* newlink = new flink;
memset(newlink->data, NULL, sizeof(newlink->data));
strcpy(newlink->data, foldername);
newlink->previous = first;
if(first)
first->next = newlink;
first = newlink;
}

char* fnamelink::getCurrent()
{
flink* current = first;
if(current != NULL)
return current->data;
else
return NULL;
}

char* fnamelink::getPrevious()
{
flink* current = first;
current = current->previous;
if(current->previous == NULL)
{
first = current;
return NULL;
}
if(current->previous != NULL)
return current->data;
else
return NULL;
}

char* fnamelink::getNext()
{
flink* current = first;
if((current = current->next) == NULL)
{
return NULL;
}
if(current != NULL)
return current->data;
else
return NULL;
}

char* fnamelink::getFirst()
{
flink* current = first;
if(current)
{
=> while(current->previous != NULL)
{
current = current->previous;
}
}
first = current;
if(first)
return first->data;
else
return NULL;
}

void fnamelink::deleteLink()
{
int numToDel = 0;
flink* current = first;
if(current->next)
{
while(current->next != NULL)
{
current = current->next;
first = current;
numToDel++;
}
while((numToDel) >= 0)
{
numToDel--;
first = first->previous;
free(current);
current = first;
}
free(current);
}
else
{
first = first->previous;
free(current);
}
}


The '=>' I placed in the code was the exception the debugger pointed
out, but I can't seem to find a problem with it. Any help would be
greatly appreciated.

You are attempting to dereference a NULL pointer. Lets look at one of your
methods:

char* fnamelink::getPrevious()
{
flink* current = first;
current = current->previous;
if(current->previous == NULL)
{
first = current;
return "NULL";
}
if(current->previous != NULL)
return current->data;
else
return "NULL";
}

flink* current = first;
at this point first may be NULL if there are no items in the list.
current = current->previous;
if first was NULL, you just attempted to use a NULL pointer. This will
abend (abnormal end). Now, lets presume we have 1 item in the list, so
first was not null. But since there's only one item, previous will be NULL.
So current is now NULL. So we get to the next line:
if(current->previous == NULL)
Ooops, current is NULL Again, you are attempting to derefence a NULL
pointer. You didn't check if current was NULL first.

These types of errors are all over the code in all the functions.

 

[Howard]

You are attempting to dereference a NULL pointer. Lets look at one of
your methods:

You're correct, of course, but interestingly, the location of the reported
error is in the one function which does NOT allow a NULL pointer to be
dereferenced! (But once you've got undefined behavior, nothing else can
be trusted, so the location of the crash *could* be just about anywhere.)

-Howard

 

[Jim Langston]

You're correct, of course, but interestingly, the location of the reported
error is in the one function which does NOT allow a NULL pointer to be
dereferenced! (But once you've got undefined behavior, nothing else
can be trusted, so the location of the crash *could* be just about
anywhere.)

Yeah, the interesting this is when I compiled and tested (with a few
modifications such as changing free to delete, returning "NULL" instead of
NULL for testing, etc...) getFirst() was actually working. I think it
depends on how the class is used however, and without code showing how he
was using it, could only go on what I observed.

The intesting thing about his linked list, however, is that you can get the
first, second and last items in the list, but no other using fnamelink's
wrapper. Also, the first in the fnamelink is actually the last item in the
list, since new items are iserted before first. So to get the first item
added, he has to iterate through from the last item added XD

 

[=?ISO-8859-1?Q?Erik_Wikstr=F6m?=]

Yeah, the interesting this is when I compiled and tested (with a few
modifications such as changing free to delete, returning "NULL" instead of
NULL for testing, etc...) getFirst() was actually working. I think it
depends on how the class is used however, and without code showing how he
was using it, could only go on what I observed.

The intesting thing about his linked list, however, is that you can get the
first, second and last items in the list, but no other using fnamelink's
wrapper. Also, the first in the fnamelink is actually the last item in the
list, since new items are iserted before first. So to get the first item
added, he has to iterate through from the last item added XD

Actually, as far as I can understand the code, it is possible to get any
element in the list, since first does not necessarily point to the first
element (look at getNext()/getPrevious()). This means that insertions
are not necessarily made at the end either, it could be in the middle.