Thread: circular doubly linked list help

  1. #1
    Registered User
    Join Date
    Mar 2007
    Posts
    7

    circular doubly linked list help

    You need to implement a class ListDL as a circular doubly
    linked list with a sentinel node.

    A private encapsulated class for the nodes of the doubly linked list is provided.
    class ListNode

    ListNodeptr prev_;
    ListNodeptr next_;
    T* data_;
    ListDL<T>* container_;

    class ListDL

    ListNode* head;
    int size_;

    I already create some method, but when i rebuild and run the auto marking program, it stopped after passing the first test( for the size() and isEmpty() ), it did not go through the addFirst( ) test. I am damn sick because of this. Please help me out, thanks all.

    Code:
    //Default constructor
     ListDL(){
            // Add your code here 
            head = new ListNode;
            head->prev_ = head;
            head->next_ = head;
            head->data_ = NULL;
            head->container_ = this;
            size_ = 0;         
        }
    
    /**
         * A virtual destructor.
         * In the destructor you should delete each node in the list.
         */
        virtual ~ListDL(){
            // add your code here
            ListNode* tmp;
            ListNode* traverse = head->next_;
            while (traverse != NULL)
            {
                tmp = traverse;
                traverse = traverse->next_;
                delete tmp;
            }
          size_ = 0;
    
    /**
         * The copy constructory.
         * In the copy constructor you need to create an empty ListDL object, and then
         * add the data from the rhs list to this list.
         * @param rhs an existing ListDL object.
         */
        ListDL(const ListDL<T>& rhs){
            // Add your code here
            ListNode* p = rhs.head;
            ListNode* v = new ListNode(p->prev,p->next,p->data,p->container);
            size_ = rhs.size_;
        }
    
    
    /**
         * The assignment operator for ListDL.
         * In the assignment operator you should:
         * <ol>
         * <li> Check that you are not doing self assignment (just return <b><tt>*this</tt></b> if you are).</li>
         * <li> Delete the data nodes of the <b><tt>*this</tt></b> list (but not the header node).</li>
         * <li> Create and add new data nodes to the <b>this</b> list with the same data as in rhs list.</li>
         * <li> ensure the size is set correctly.</li>
         * <li> return the <b><tt>*this</tt></b> object.
         * </ol>
         * @param rhs an existing ListDL object.
         * @return a reference to the assigned ListDL object.
         */
        ListDL<T>& operator=(const ListDL<T>& rhs){
        	if (this != &rhs){
                // add your code here
                ListNode* tmp;
                ListNode* traverse = head->next_;
                while (traverse != NULL)
                {
                  tmp = traverse;
                  traverse = traverse->next_;
                  delete tmp;
                }
                size_ = rhs.size_;
                ListNode* p = rhs.head;
                ListNode* v = new ListNode(p->prev,p->next,p->data,p->container);
        	}
        	return *this;
        }
    
    /**
         * A method to safely cast a Position pointer object to a ListNode pointer object.
         * 
         * <p>You will find it useful to write a method validate
         * to cast a Position pointer object to a ListNode pointer object,
         * to check its validity, and to return the ListNode pointer object.
         * This checking should be done inside a try block, casting a
         * PositionInvalidException if an exception is thrown or an error found.
         * If the cast to a ListNode* object is successful, the ListNode* object
         * is valid if:
         * <ol>
         * <li> It is not null</li>
         * <li> The container_ field for the ListNode object is equal to this.</li>
         * </ol>
         * In methods that are passed a Position pointer object, you should use
         * this method to get the corresponding ListNode pointer object.
         * @param pos a Position pointer object to validate
         * @return the corresponding listNode* object.
         * @throw PositionInvalidException if the Position object is not valid for this list.
         */
        ListNode* validate(const Position<T>* pos) const throw(PositionInvalidException){
            // replace this code with your own
             if (pos.head == NULL)
                 throw PositionInvalidException("position");
             else
                 return pos.head;
             
        }
    
    /**
         * Add a new Object at the front of the List,
         * returning the Position of the new element in the List.
         * Hint: A <tt>ListNode*</tt> object is a <tt>Position&lt;T&gt;*</tt> object, so you 
         * only need return the pointer to the <tt>ListNode</tt> object that you
         * created and added to the list.  You don't need to cast this object
         * to a <tt>Position&lt;T&gt;*</tt> object.
         *
         * @param e the object to add to the list.
         * @return the Position in the List of the new element.
         */
        virtual Position<T>* addFirst(const T& e){
            // replace this code with your own         
               ListNode* newNode = new ListNode;
               newNode->setData(e);
               newNode->prev_ = head;  newNode->next_ = head->next_;
               newNode->prev_->next_ = newNode;
               newNode->next_->prev_ = newNode;
               size_++;
               return newNode;
        }
    
    
    /**
         * Returns the number of objects in the list.
         *
         * @return integer count of the number of objects in the List.
         */
        virtual int size() const { 
            // add your code here
            return size_;
        }
    
        /**
         *  Test if the List is empty.
         *
         *  @return true if the List is empty, false otherwise.
         */
        virtual bool isEmpty() const { 
            // add your code here 
            if (size_ == 0)
               return true;
            else
               return false;
        }

  2. #2
    Registered User
    Join Date
    Oct 2001
    Posts
    2,934
    Code:
    >    virtual ~ListDL(){
    >        // add your code here
    >        ListNode* tmp;
    >        ListNode* traverse = head->next_;
    >        while (traverse != NULL)
    >        {
    >            tmp = traverse;
    >            traverse = traverse->next_;
    >            delete tmp;
    >        }
    >      size_ = 0;
    I'm surprised it compiles. You're missing a right brace here:
    Code:
        virtual ~ListDL(){
            // add your code here
            ListNode* tmp;
            ListNode* traverse = head->next_;
            while (traverse != NULL)
            {
                tmp = traverse;
                traverse = traverse->next_;
                delete tmp;
            }
          size_ = 0;
        }

  3. #3
    Registered User
    Join Date
    Mar 2007
    Posts
    7
    I did not miss the braces, i miss to include here, well why no one is helping me out, well the problem is now i am stuck big time, well i am stuck at the addFirst method, can anyone guide me how to do it right?

  4. #4
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    Why does ListDL() create a dummy node, rather than just saying
    head = NULL;

    The problem being your
    head->container_ = this;
    seems to be pointing at something completely different (type wise) to what every other node of the list is.

    Inserting at the head of the list should be
    Code:
    if ( head == NULL ) head = newNode;
    else {
      newNode->next = head;
      newNode->prev = NULL;
      head->prev = newNode;
      head = newNode;
    }
    size_++;
    It helps if you draw these out on paper, so you can 'animate' how the next/prev pointers change. As you change a pointer on paper, do the same thing in the code.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  5. #5
    Registered User
    Join Date
    Oct 2001
    Posts
    2,934
    It also helps if a description of what error is occurring is given, not my program isn't working. My program isn't working could mean many different things. It also helps if the complete code is posted, so it can be compiled.

  6. #6
    Registered User
    Join Date
    Nov 2004
    Location
    Pennsylvania
    Posts
    434
    Try the debugger If you're in MSVC it is great.

    I was curious and i whipped up a program for a doubly-linked circular list in 10 minutes. Then again i don't have the constraints of your assignment But just focus on isolating one thing at a time until you find what's wrong.

    Good luck!
    "Anyone can aspire to greatness if they try hard enough."
    - Me

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 5
    Last Post: 11-04-2006, 06:39 PM
  2. Circular doubly linked list with dummy header
    By mag_chan in forum C Programming
    Replies: 5
    Last Post: 10-31-2005, 08:44 AM
  3. doubly linked list problem
    By YevGenius in forum C Programming
    Replies: 4
    Last Post: 05-02-2004, 08:54 PM
  4. Linked list with two class types within template.
    By SilasP in forum C++ Programming
    Replies: 3
    Last Post: 02-09-2002, 06:13 AM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM