Problem with Linked List

Collapse
This topic is closed.
X
X
Collapse
 
  • Page of 1
  • Time
  • Show
Clear All
new posts
Previous template Next
  • oceanspell
    #1

    Problem with Linked List

    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::addI tem(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::getC urrent()
    {
    flink* current = first;
    if(current != NULL)
    return current->data;
    else
    return NULL;
    }

    char* fnamelink::getP revious()
    {
    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::getN ext()
    {
    flink* current = first;
    if((current = current->next) == NULL)
    {
    return NULL;
    }
    if(current != NULL)
    return current->data;
    else
    return NULL;
    }

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

    void fnamelink::dele teLink()
    {
    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.

    Tags: None
    • Howard
      #2
      Re: Problem with Linked List

      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

        Comment

        • Jim Langston
          #3
          Re: Problem with Linked List

          "oceanspell " <randomuser5000 @gmail.comwrote in message
          news:1189976472 .525301.187410@ o80g2000hse.goo glegroups.com.. .
          >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::addI tem(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::getC urrent()
          {
          flink* current = first;
          if(current != NULL)
          return current->data;
          else
          return NULL;
          }
          >
          char* fnamelink::getP revious()
          {
          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::getN ext()
          {
          flink* current = first;
          if((current = current->next) == NULL)
          {
          return NULL;
          }
          if(current != NULL)
          return current->data;
          else
          return NULL;
          }
          >
          char* fnamelink::getF irst()
          {
          flink* current = first;
          if(current)
          {
          = while(current->previous != NULL)
          {
          current = current->previous;
          }
          }
          first = current;
          if(first)
          return first->data;
          else
          return NULL;
          }
          >
          void fnamelink::dele teLink()
          {
          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::getP revious()
          {
          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.


            Comment

            • Howard
              #4
              Re: Problem with Linked List


              "Jim Langston" <tazmaster@rock etmail.comwrote in message
              news:WSlHi.85$a e3.16@newsfe02. lga...

              >char* fnamelink::getF irst()
              >{
              > 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

                Comment

                • Jim Langston
                  #5
                  Re: Problem with Linked List

                  "Howard" <me@here.comwro te in message
                  news:zbOdnfqtlY Wcc3DbnZ2dnUVZ_ ruqnZ2d@comcast .com...
                  >
                  "Jim Langston" <tazmaster@rock etmail.comwrote in message
                  news:WSlHi.85$a e3.16@newsfe02. lga...
                  >
                  >
                  >>char* fnamelink::getF irst()
                  >>{
                  >> 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


                    Comment

                    • =?ISO-8859-1?Q?Erik_Wikstr=F6m?=
                      #6
                      Re: Problem with Linked List

                      On 2007-09-17 05:28, Jim Langston wrote:
                      "Howard" <me@here.comwro te in message
                      news:zbOdnfqtlY Wcc3DbnZ2dnUVZ_ ruqnZ2d@comcast .com...
                      >>
                      >"Jim Langston" <tazmaster@rock etmail.comwrote in message
                      >news:WSlHi.85$ ae3.16@newsfe02 .lga...
                      >>
                      >>
                      >>>char* fnamelink::getF irst()
                      >>>{
                      >>> 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

                        Comment

                        Previous template Next
                        Working...