Problem with Linked List

Discussion in 'C++' started by oceanspell, Sep 16, 2007.

  1. oceanspell

    oceanspell Guest

    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.
    oceanspell, Sep 16, 2007
    #1
    1. Advertising

  2. oceanspell

    Howard Guest


    > 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
    Howard, Sep 17, 2007
    #2
    1. Advertising

  3. oceanspell

    Jim Langston Guest

    "oceanspell" <> wrote in message
    news:...
    >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.
    Jim Langston, Sep 17, 2007
    #3
  4. oceanspell

    Howard Guest

    "Jim Langston" <> wrote in message
    news:WSlHi.85$...


    >> 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;
    >> }
    >>


    > 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
    Howard, Sep 17, 2007
    #4
  5. oceanspell

    Jim Langston Guest

    "Howard" <> wrote in message
    news:...
    >
    > "Jim Langston" <> wrote in message
    > news:WSlHi.85$...
    >
    >
    >>> 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;
    >>> }
    >>>

    >
    >> 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.)


    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
    Jim Langston, Sep 17, 2007
    #5
  6. On 2007-09-17 05:28, Jim Langston wrote:
    > "Howard" <> wrote in message
    > news:...
    >>
    >> "Jim Langston" <> wrote in message
    >> news:WSlHi.85$...
    >>
    >>
    >>>> 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;
    >>>> }
    >>>>

    >>
    >>> 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.)

    >
    > 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.

    --
    Erik Wikström
    =?ISO-8859-1?Q?Erik_Wikstr=F6m?=, Sep 17, 2007
    #6
    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:
    458
    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:
    447
    emerth
    Jul 10, 2003
  3. fool
    Replies:
    14
    Views:
    481
    Barry Schwarz
    Jul 3, 2006
  4. joshd
    Replies:
    12
    Views:
    648
    John Carson
    Oct 2, 2006
  5. jawdoc
    Replies:
    9
    Views:
    727
    Chris Thomasson
    Mar 10, 2008
Loading...

Share This Page