Trouble with linked lists

Discussion in 'C++' started by Skywise, Aug 31, 2004.

  1. Skywise

    Skywise Guest

    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++;
    };
    };
    Skywise, Aug 31, 2004
    #1
    1. Advertising

  2. Skywise

    David Hilsee Guest

    "Skywise" <> wrote in message
    news:...
    > 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
    David Hilsee, Aug 31, 2004
    #2
    1. Advertising

  3. * 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?
    Alf P. Steinbach, Aug 31, 2004
    #3
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Chris Ritchey
    Replies:
    7
    Views:
    475
    emerth
    Jul 10, 2003
  2. Chris Ritchey

    Generating a char* from a linked list of linked lists

    Chris Ritchey, Jul 9, 2003, in forum: C Programming
    Replies:
    7
    Views:
    462
    emerth
    Jul 10, 2003
  3. =?UTF-8?B?w4FuZ2VsIEd1dGnDqXJyZXogUm9kcsOtZ3Vleg==

    List of lists of lists of lists...

    =?UTF-8?B?w4FuZ2VsIEd1dGnDqXJyZXogUm9kcsOtZ3Vleg==, May 8, 2006, in forum: Python
    Replies:
    5
    Views:
    397
    =?UTF-8?B?w4FuZ2VsIEd1dGnDqXJyZXogUm9kcsOtZ3Vleg==
    May 15, 2006
  4. fool
    Replies:
    14
    Views:
    501
    Barry Schwarz
    Jul 3, 2006
  5. jawdoc
    Replies:
    9
    Views:
    747
    Chris Thomasson
    Mar 10, 2008
Loading...

Share This Page