locked
Adding nodes to the start of a circuilar doubly linked list.

    Question

  • Hi,

    I am trying to implement a function called addFirst that should add elements to the start of a circuilar doubly linked list. The class for the circuilar doubly linked list data structure, which is a template class, is called ListDL. A ListDL object encapsulates a circular doubly linked list of ListNode objects. The first node in the list, is the sentinel node. The ListDL object maintains a pointer "head" to this node. Contained within the class definition of ListDL is the following:

    ListNodeptr prev_;   //< A pointer to the previous node in the doubly linked list
    ListNodeptr        next_;   //< A pointer to the next node in the doubly linked list
    T* data_;   //< A pointer to the data object associated with this node.
    ListDL<T>*  container_;  //< A pointer to the container ListDL class containing this node.

    Below is my implementation of the method addFirst:

        virtual Position<T>* addFirst(const T& e){
            ListNode* newFirst = new ListNode();
            newFirst->prev_ = head->prev_;
            newFirst->next_ = head;
            newFirst->setData(e);
            newFirst->container_ = head->container_;
            newFirst->prev_->next_ = newFirst;
            newFirst->next_->prev_ = newFirst;
            ++size_;
            return newFirst;
        }

    The method should return a pointer to the newly inserted node. The default constructor that I used in this method sets the four pointers to NULL. size, however, keeps tracks of the number of nodes in the list. Debugging the program results in the following warning message being displayed:

    Unhandled exception at 0x6216bb30 in Assignment 2.exe: 0xC0000005: Access violation reading location 0x0000001c.

    Upon further investigation using Visual C++ 2008 Express, I found that the call to the method setData is the source of the problems. Below is the definition of the method setData:

        void setData(const T& data){
            *data_ = data;
        }

    This is confusing me because theoretically speaking, everything should work just fine, but for some reason it isn't. I was wondering if someone could point me in the right direction on how to deal with this.

    Cheers
    • Edited by Arondals Friday, May 08, 2009 3:19 PM
    • Changed type Nancy Shao Thursday, May 14, 2009 10:02 AM op does not follow up
    • Changed type nobugzMVP, Moderator Thursday, May 14, 2009 11:09 AM marking answered
    Friday, May 08, 2009 3:19 PM

Answers

  • You forgot to allocate memory for the data_ member:

      newFirst->data_ = new T;
      newFirst->setData(e);

    Beware that you'll have to release this data too or your program will leak badly.
     
    Hans Passant.
    Friday, May 08, 2009 6:52 PM

All replies

  • You forgot to allocate memory for the data_ member:

      newFirst->data_ = new T;
      newFirst->setData(e);

    Beware that you'll have to release this data too or your program will leak badly.
     
    Hans Passant.
    Friday, May 08, 2009 6:52 PM
  • Thanks for your reply Hans,

    I also forgot something else with that code fragment which is updating the head pointer as it was still pointing the old first node. Now I modified the method and made the head point to the newly inserted node.

    However, I have another problem with the same project and I wasn't sure whether to start a new thread or continue with this one. Eventually I decided to continue with this one so that I don't repeat myself. The problem that I currently facing is with another method that is supposed to add a node to the end of the list as the last node as opposed to the start of the list. I visualized the problem and found that a significant portion of this new method would look almost identical to the addFirst method. The only difference being that there is no need to update the head pointer.

    Below is the code that I developed for this particular method:

        virtual Position<T>* addLast(const T& e){ 
            ListNode* newLast = new ListNode();
            newLast->prev_ = head->prev_;
            newLast->next_ = head;
            newLast->data_ = new T;
            newLast->setData(e);
            newLast->container_ = head->container_;
            newLast->prev_->next_ = newLast;
            newLast->next_->prev_ = newLast;
            ++size_;
            return newLast;
        }

    Code that is contained within a seperate source file is supposed to check whether the function is performing what it is supposed to. Below is relevant code from that source file:

    int ListMarks::addLastTest(){
    int max = 4;
    int result = 0;
    Position<std::string>* p = NULL;
    msg("ListDL: Testing addLast()");
    try{
    List<std::string>* l = new ListDL<std::string>();
    l->addLast("A");
    if ((l->size()==1) && (l->first()->element().compare("A")==0)){
    msg("\tpassed - addLast to empty list");
    result = inc(result, 2, max);
    p = l->addLast("B");
    if ((p == l->last()) && (l->size()==2) && (l->last()->element().compare("B")==0)){
    msg("\tpassed - addLast to non-empty list");
    result = inc(result, 2, max);
    }else{
    msg("\t***failed - addLast to a non-empyt list");
    }
    }else{
    msg("\t***failed - addLast to an empty list");
    }
    }catch (...){
    msg("\tUnexpected exception during test ***failed test");
    }
    return result;
    }

    The function addLast is not functioning properly because of the code that is underlined and as such, the following message is being dispalyed: "Unexpected exception during test ***failed test". Below are the definitions of the first() and element() methods:

        virtual Position<T>* first() const throw(ListEmptyException){
            if(isEmpty())		//Tests whether a linked list is empty by checking the size_ member
                throw ListEmptyException("Exception: List Empty");
            return head;
        }

        virtual T& element()  { 
            if (data_ != 0)
                return *data_; 
            throw PositionInvalidException("element() called with NULL data pointer");
        }
    

    Debugging the code, I found that after calling the addLast method, the data_ member contains the string "A" in the body of the addLast method. However, when I am at the line of code that is underlined, the value that is contained within data_ member of the sentinel node (head) of the new l listDL object is 0x00000000. This is causing the PositionInvalidException to be thrown when the element() method is called.

    Why is this happening? That is, why is the value within the data_ member of the sentinel node of the l ListDL object not equal to "A" when the expression l->first()->element().compare("A")==0 is being evaluated?

    Cheers.
    Saturday, May 09, 2009 9:35 AM
  • I can't see how this code compiles.  The first() method returns a Position<T>* but the element() method looks like a member of the ListDL class.  There is no obvious mapping from one to the other that I can see.

    Inventing your own list class is okay, but it's hard to get support for it from a forum.  Consider using std::list instead.

    Hans Passant.
    Saturday, May 09, 2009 11:34 AM
  • Hi,

    We are changing the issue type to “General Discussion” because you have not followed up with the necessary information. If you have more time to look at the issue and provide more information, please feel free to change the issue type back to “Question” by opening the Options list at the top of the post editor window, and changing the type. If the issue is resolved, we will appreciate it if you can share the solution so that the answer can be found and used by other community members having similar questions.

    Thank you!

    Best Regards,
    Nancy


    Please remember to mark the replies as answers if they help and unmark them if they provide no help.
    Welcome to the All-In-One Code Framework! If you have any feedback, please tell us.
    Thursday, May 14, 2009 10:01 AM