Trouble with linked lists
 

I am fairly new to linked lists. I am trying to write a class using
linked lists. It seems to work fine, but I need to know if I have any
resource leaks in it because I plan on using this class quite a bit in
my program. By the way, I am not a student hoping someone will do my
work for me (the "cout"s are going to be taken out when I finalize the
class... there just for debugging purposes now). This code is part of
a computer program I am making which will surely make me rich (read:
I'm a 32 year old with a hobby). If anyone sees any basic problems,
please let me know. I am trying to learn.

Also, if this isn't the sort of thing I should be posting here, let me
know that too (you guys helped me before, and I thank you for it).

The following code is the class I created. The list stores a class
called UNITDEF which is a simple class containing no pointers, or
anything... just regular ints and stuff and so I didn't include it (I
know it works perfectly).


class UnitDefNode
{
public:
UnitDefNode();
UnitDefNode(UNITDEF uData);
UNITDEF UnitData; // Data to be stored
UnitDefNode * next;
};

UnitDefNode::UnitDefNode()
{
next=0;
};

UnitDefNode::UnitDefNode(UNITDEF uData)
{
next=0;
UnitData = uData;
};


// LINKED LIST CLASS

class UnitDefList
{
public:
UnitDefList();
void CleanList();
void Insert(UNITDEF uData);
int GetNumUnitsDefined() { return iNumUnitsDefined;};

private:
UnitDefNode *HEAD;
int iNumUnitsDefined;
};

UnitDefList::UnitDefList()
{
HEAD = new UnitDefNode;
HEAD->next = NULL;
iNumUnitsDefined = 0;
};

void UnitDefList::CleanList()
{
if (HEAD != NULL)
{
cout << "Head is not Null and there are " << iNumUnitsDefined << "
nodes in list!\n";
UnitDefNode* temp;
if (iNumUnitsDefined > 0)
{
while (HEAD->next != NULL)
{
temp = HEAD;
HEAD = HEAD->next;
delete temp;
cout << "Node deleted!\n";
iNumUnitsDefined--;
}; // end while
delete HEAD;
HEAD->next= NULL;
cout << "Head is null\n";
};// end if
}; //end if
};

void UnitDefList::Insert(UNITDEF uData)
{
if (HEAD == NULL) // if the head is NULL
{
HEAD = new UnitDefNode(uData); // creates and adds in data to node
HEAD->next = NULL;
iNumUnitsDefined++;
}
else
{
UnitDefNode * temp = HEAD;
while (temp->next != NULL) // transverse the list
{
temp = temp->next; // transverse the list
}
UnitDefNode * NewNode = new UnitDefNode(uData); // creates and adds
in data to node
temp ->next = NewNode;
NewNode->next=NULL;
iNumUnitsDefined++;
};
};

Re: Trouble with linked lists
 

"Skywise" <theskywise@houston.rr.com> wrote in message
news:2124737f.0408301819.9670517@posting.google.co m...
> I am fairly new to linked lists. I am trying to write a class using
> linked lists. It seems to work fine, but I need to know if I have any
> resource leaks in it because I plan on using this class quite a bit in
> my program. By the way, I am not a student hoping someone will do my
> work for me (the "cout"s are going to be taken out when I finalize the
> class... there just for debugging purposes now). This code is part of
> a computer program I am making which will surely make me rich (read:
> I'm a 32 year old with a hobby). If anyone sees any basic problems,
> please let me know. I am trying to learn.

IMHO, if you really have a program that will make you rich, then you should
pay a great programmer to crank out the implementation quickly. It could
take years to produce a high-quality product if you try to learn C++ from
scratch yourself. If you're just toying around with an idea for fun, then
what you're doing is fine.

If you want a linked list, then you probably shouldn't bother writing your
own unless you're doing it for fun or educational purposes. The standard
library has many containers that will make most custom containers
unnecessary. The std::list template, for example, is a great replacement
for what you have written.

> Also, if this isn't the sort of thing I should be posting here, let me
> know that too (you guys helped me before, and I thank you for it).
>
> The following code is the class I created. The list stores a class
> called UNITDEF which is a simple class containing no pointers, or
> anything... just regular ints and stuff and so I didn't include it (I
> know it works perfectly).
>
>
> class UnitDefNode
> {
> public:
> UnitDefNode();
> UnitDefNode(UNITDEF uData);
> UNITDEF UnitData; // Data to be stored
> UnitDefNode * next;
> };
>
> UnitDefNode::UnitDefNode()
> {
> next=0;
> };
>
> UnitDefNode::UnitDefNode(UNITDEF uData)
> {
> next=0;
> UnitData = uData;
> };
>
>
> // LINKED LIST CLASS
>
> class UnitDefList
> {
> public:
> UnitDefList();
> void CleanList();
> void Insert(UNITDEF uData);
> int GetNumUnitsDefined() { return iNumUnitsDefined;};
>
> private:
> UnitDefNode *HEAD;
> int iNumUnitsDefined;
> };
>
> UnitDefList::UnitDefList()
> {
> HEAD = new UnitDefNode;
> HEAD->next = NULL;
> iNumUnitsDefined = 0;
> };
>
> void UnitDefList::CleanList()
> {
> if (HEAD != NULL)
> {
> cout << "Head is not Null and there are " << iNumUnitsDefined << "
> nodes in list!\n";
> UnitDefNode* temp;
> if (iNumUnitsDefined > 0)
> {
> while (HEAD->next != NULL)
> {
> temp = HEAD;
> HEAD = HEAD->next;
> delete temp;
> cout << "Node deleted!\n";
> iNumUnitsDefined--;
> }; // end while
> delete HEAD;
> HEAD->next= NULL;
<snip>

This line is obviously wrong. I think you meant to write

HEAD = NULL;

BTW, what's with the various inconsistent naming conventions (HEAD versus
iNumUnitsDefined)? You also have many semicolons where none are required.
The only places in your code where you need semicolons after close braces
are at the end of the class definitions (two places).

--
David Hilsee

Re: Trouble with linked lists
 

* Skywise:
> I am fairly new to linked lists. I am trying to write a class using
> linked lists. It seems to work fine, but I need to know if I have any
> resource leaks in it because I plan on using this class quite a bit in
> my program. By the way, I am not a student hoping someone will do my
> work for me (the "cout"s are going to be taken out when I finalize the
> class... there just for debugging purposes now). This code is part of
> a computer program I am making which will surely make me rich (read:
> I'm a 32 year old with a hobby). If anyone sees any basic problems,
> please let me know. I am trying to learn.

The basic & simple solution is to use std::list instead of a DIY list.

That will make sure you don't have any resource leaks due to the list
handling.

However you'll not learn very much about pointers etc. by doing that.


> Also, if this isn't the sort of thing I should be posting here, let me
> know that too (you guys helped me before, and I thank you for it).
>
> The following code is the class I created. The list stores a class
> called UNITDEF

Don't.

All uppercase names are conventionally reserved for macros.

By using them for other things you risk that some macro in some headerfile
makes havoc of your source code, and additionally it's "shouting".


> which is a simple class containing no pointers, or
> anything... just regular ints and stuff and so I didn't include it (I
> know it works perfectly).
>
>
> class UnitDefNode
> {
> public:
> UnitDefNode();
> UnitDefNode(UNITDEF uData);

Pass by reference to const, for efficiency.


> UNITDEF UnitData; // Data to be stored
> UnitDefNode * next;
> };
>
> UnitDefNode::UnitDefNode()
> {
> next=0;
> };

Don't have semicolon here (have you tried to compile this?).

Use memory initialiser list instead of assignment wherever possible.

That way you'll get more efficient and more readable code.


> UnitDefNode::UnitDefNode(UNITDEF uData)
> {
> next=0;
> UnitData = uData;
> };

Ditto.


> // LINKED LIST CLASS

You should include relevant node operations in the node class before
getting on to the list class.

Especially relevant is the 'nextUnlinked' operation:


UnitDefNode* UnitDefNode::nextUnlined()
{
UnitDefNode* const result = next;
if( next != 0 ) { next = next->next; }
return result;
}


Also 'insertNext'.


> class UnitDefList
> {
> public:
> UnitDefList();
> void CleanList();
> void Insert(UNITDEF uData);
> int GetNumUnitsDefined() { return iNumUnitsDefined;};
>
> private:
> UnitDefNode *HEAD;

Don't use uppercase names (explained earlier).


> int iNumUnitsDefined;
> };
>
> UnitDefList::UnitDefList()
> {
> HEAD = new UnitDefNode;
> HEAD->next = NULL;
> iNumUnitsDefined = 0;
> };

Don't have semicolon here (have you tried to compile this?).

Use memory initialiser list instead of assignment wherever possible.

That way you'll get more efficient and more readable code.


> void UnitDefList::CleanList()
> {
> if (HEAD != NULL)

Consider the simplification of having 'head != 0' as a class invariant.


> {
> cout << "Head is not Null and there are " << iNumUnitsDefined << "
> nodes in list!\n";
> UnitDefNode* temp;
> if (iNumUnitsDefined > 0)
> {
> while (HEAD->next != NULL)
> {
> temp = HEAD;
> HEAD = HEAD->next;
> delete temp;
> cout << "Node deleted!\n";
> iNumUnitsDefined--;

Preferentially use pre-decrement rather than post-decrement.

> }; // end while



> delete HEAD;
> HEAD->next= NULL;

See above.

But also, do you notice that here's some duplicated (redundant) code?

You could fix that simply by changing the loop condition.


> cout << "Head is null\n";
> };// end if
> }; //end if
> };

Also consider the simplification and improved flexibility of using
'nextUnlinked' mentioned earlier.


> void UnitDefList::Insert(UNITDEF uData)
> {
> if (HEAD == NULL) // if the head is NULL
> {
> HEAD = new UnitDefNode(uData); // creates and adds in data to node
> HEAD->next = NULL;
> iNumUnitsDefined++;


Preferentially use pre-decrement rather than post-decrement.


> }
> else
> {
> UnitDefNode * temp = HEAD;
> while (temp->next != NULL) // transverse the list
> {
> temp = temp->next; // transverse the list
> }

Consider the time used for this (linear) as opposed to storing a pointer
to the last node in the list (constant), and also consider how the class
invariant mentioned earlier can help in that.


> UnitDefNode * NewNode = new UnitDefNode(uData); // creates and adds
> in data to node
> temp ->next = NewNode;
> NewNode->next=NULL;
> iNumUnitsDefined++;


Preferentially use pre-decrement rather than post-decrement.

Do you notice that there's duplicated (redundant) code here?

Consider the 'insertNext' operation mentioned earlier.

> };
> };

--
A: Because it messes up the order in which people normally read text.
Q: Why is it such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?