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<T>*</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<T>*</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;
}
