1. Write the definitions of the following methods for the class doublyLinkedList
    a. copyList
    b. copy constructor
    c. function to overload the assignment operator
    d. destructor

Also, write a program to test the copy constructor and the assignment operator methods of the class doublyLinkedList.

#ifndef H_doublyLinkedList
#define H_doublyLinkedList

#include <iostream>
#include <cassert>

using namespace std;

  //Definition of the node
template <class Type>
struct nodeType
{  
    Type info;
    nodeType<Type> *next;
    nodeType<Type> *back;  
};

template <class Type>
class doublyLinkedList
{
public:
    const doublyLinkedList<Type>& operator=
                           (const doublyLinkedList<Type> &);
      //Overload the assignment operator.

    void initializeList();
      //Function to initialize the list to an empty state.
      //Postcondition: first = NULL; last = NULL; count = 0;

    bool isEmptyList() const;
      //Function to determine whether the list is empty.
      //Postcondition: Returns true if the list is empty,
      //               otherwise returns false.

    void destroy();
      //Function to delete all the nodes from the list.
      //Postcondition: first = NULL; last = NULL; count = 0;

    void print() const;
      //Function to output the info contained in each node.

    void reversePrint() const;
      //Function to output the info contained in each node
      //in reverse order.

    int length() const;
      //Function to return the number of nodes in the list.
      //Postcondition: The value of count is returned.

    Type front() const;
      //Function to return the first element of the list.
      //Precondition: The list must exist and must not be empty.
      //Postcondition: If the list is empty, the program terminates;
      //    otherwise, the first element of the list is returned.

    Type back() const;
      //Function to return the last element of the list.
      //Precondition: The list must exist and must not be empty.
      //Postcondition: If the list is empty, the program terminates;
      //    otherwise, the last element of the list is returned.

    bool search(const Type& searchItem) const;
      //Function to determine whether searchItem is in the list.
      //Postcondition: Returns true if searchItem is found in the
      //    list, otherwise returns false.

    void insert(const Type& insertItem);
      //Function to insert insertItem in the list.
      //Precondition: If the list is nonempty, it must be in order.              
      //Postcondition: insertItem is inserted at the proper place
      //    in the list, first points to the first node, last points
      //    to the last node of the new list, and count is 
      //    incremented by 1.

    void deleteNode(const Type& deleteItem);
      //Function to delete deleteItem from the list. 
      //Postcondition: If found, the node containing deleteItem is
      //    deleted from the list; first points to the first node of
      //    the new list, last points to the last node of the new 
      //    list, and count is decremented by 1; otherwise an
      //    appropriate message is printed. 

    doublyLinkedList(); 
      //default constructor
      //Initializes the list to an empty state.
      //Postcondition: first = NULL; last = NULL; count = 0;

    doublyLinkedList(const doublyLinkedList<Type>& otherList); 
      //copy constructor
    ~doublyLinkedList(); 
      //destructor
      //Postcondition: The list object is destroyed.

protected:
    int count;
    nodeType<Type> *first; //pointer to the first node
    nodeType<Type> *last;  //pointer to the last node

private:
    void copyList(const doublyLinkedList<Type>& otherList); 
      //Function to make a copy of otherList.
      //Postcondition: A copy of otherList is created and assigned
      //    to this list.
};

template <class Type>
doublyLinkedList<Type>::doublyLinkedList()
{
    first= NULL;
    last = NULL;
    count = 0;
}

template <class Type>
bool doublyLinkedList<Type>::isEmptyList() const
{
    return (first == NULL);
}

template <class Type>
void doublyLinkedList<Type>::destroy()
{ 
    nodeType<Type>  *temp; //pointer to delete the node

    while (first != NULL)
    {
        temp = first;
        first = first->next;
        delete temp;
    }

    last = NULL;
    count = 0;
}

template <class Type>
void doublyLinkedList<Type>::initializeList()
{
    destroy();
}

template <class Type>
int doublyLinkedList<Type>::length() const
{
    return count;
}

template <class Type>
void doublyLinkedList<Type>::print() const
{
    nodeType<Type> *current; //pointer to traverse the list

    current = first;  //set current to point to the first node

    while (current != NULL)
    {
        cout << current->info << "  ";  //output info
        current = current->next;
    }//end while
}//end print


template <class Type>
void doublyLinkedList<Type>::reversePrint() const
{
    nodeType<Type> *current; //pointer to traverse 
                             //the list

    current = last;  //set current to point to the 
                     //last node

    while (current != NULL)
    {
        cout << current->info << "  ";  
        current = current->back;
    }//end while
}//end reversePrint

template <class Type>
bool doublyLinkedList<Type>::
                       search(const Type& searchItem) const
{
    bool found = false;
    nodeType<Type> *current; //pointer to traverse the list

    current = first;

    while (current != NULL && !found)
        if (current->info >= searchItem)
            found = true;
        else
            current = current->next;

    if (found)
       found = (current->info == searchItem); //test for 
                                              //equality

    return found;
}//end search

template <class Type>
Type doublyLinkedList<Type>::front() const
{
    assert(first != NULL);

    return first->info;
}

template <class Type>
Type doublyLinkedList<Type>::back() const
{
    assert(last != NULL);

    return last->info;
}

template <class Type>
void doublyLinkedList<Type>::insert(const Type& insertItem)
{
    nodeType<Type> *current;      //pointer to traverse the list
    nodeType<Type> *trailCurrent; //pointer just before current
    nodeType<Type> *newNode;      //pointer to create a node
    bool found;

    newNode = new nodeType<Type>; //create the node
    newNode->info = insertItem;  //store the new item in the node
    newNode->next = NULL;
    newNode->back = NULL;

    if(first == NULL) //if the list is empty, newNode is 
                      //the only node
    {
       first = newNode;
       last = newNode;
       count++;
    }
    else
    {
        found = false;
        current = first;

        while (current != NULL && !found) //search the list
            if (current->info >= insertItem)
                found = true;
            else
            {
                trailCurrent = current;
                current = current->next;
            }

        if (current == first) //insert newNode before first
        {
            first->back = newNode;
            newNode->next = first;
            first = newNode;
            count++;
        }
        else
        {
              //insert newNode between trailCurrent and current
            if (current != NULL)
            {
                trailCurrent->next = newNode;
                newNode->back = trailCurrent;
                newNode->next = current;
                current->back = newNode;
            }
            else
            {
                trailCurrent->next = newNode;
                newNode->back = trailCurrent;
                last = newNode;
            }

            count++;
        }//end else
    }//end else
}//end insert

template <class Type>
void doublyLinkedList<Type>::deleteNode(const Type& deleteItem)
{
    nodeType<Type> *current; //pointer to traverse the list
    nodeType<Type> *trailCurrent; //pointer just before current

    bool found;

    if (first == NULL)
        cout << "Cannot delete from an empty list." << endl;
    else if (first->info == deleteItem) //node to be deleted is  
                                       //the first node
    {
        current = first;
        first = first->next;

        if (first != NULL)
            first->back = NULL;
        else
            last = NULL;

        count--;

        delete current;
    }
    else 
    {
        found = false;
        current = first;

        while (current != NULL && !found)  //search the list
            if (current->info >= deleteItem)
                found = true;
            else
                current = current->next;

        if (current == NULL)
            cout << "The item to be deleted is not in " 
                 << "the list." << endl;
        else if (current->info == deleteItem) //check for 
                                                 //equality
        {
            trailCurrent = current->back; 
            trailCurrent->next = current->next;

            if (current->next != NULL)
                current->next->back = trailCurrent;

            if (current == last)
                last = trailCurrent;

            count--;
            delete current;
        }
        else
            cout << "The item to be deleted is not in list." 
                 << endl;
    }//end else
}//end deleteNode

template <class Type>
void doublyLinkedList<Type>::copyList(const doublyLinkedList<Type>& otherList)
{
    nodeType<Type> *newNode; //pointer to create a node
    nodeType<Type> *current; //pointer to traverse the list

    if (first != NULL) //if the list is nonempty, make it empty
       destroyList();

    if (otherList.first == NULL) //otherList is empty
    {
        first = NULL;
        last = NULL;
        count = 0;
    }
    else
    {
        current = otherList.first; //current points to the 
                                   //list to be copied
        count = otherList.count;

            //copy the first node
        first = new nodeType<Type>;  //create the node

        first->info = current->info; //copy the info
        first->link = NULL;        //set the link field of 
                                   //the node to NULL
        last = first;              //make last point to the
                                   //first node
        current = current->link;     //make current point to
                                     //the next node

           //copy the remaining list
        while (current != NULL)
        {
            newNode = new nodeType<Type>;  //create a node
            newNode->info = current->info; //copy the info
            newNode->link = NULL;       //set the link of 
                                        //newNode to NULL
            last->link = newNode;  //attach newNode after last
            last = newNode;        //make last point to
                                   //the actual last node
            current = current->link;   //make current point 
                                       //to the next node
        }//end while
    }//end else
}

template <class Type>
doublyLinkedList<Type>::doublyLinkedList(const doublyLinkedList<Type>& otherList)

{
    first = NULL;
    copyList(otherList);
}

template <class Type>
const doublyLinkedList<Type>& doublyLinkedList<Type>::operator=
                            (const doublyLinkedList<Type> &)
{ 
    if (this != &otherList) //avoid self-copy
    {
        copyList(otherList);
    }//end else

     return *this; 
}



template <class Type>
doublyLinkedList<Type>::~doublyLinkedList()

{
   destroyList();
}

#endif

Edited 3 Years Ago by deceptikon: Changed to a discussion thread

It was posted as a code snippet, so I'm assuming they are just showing off their work :)

Oh, nevermind. :) I missed the article title that says Having trouble with doublyLinkedList ... no clue what the problem is lol.

I concur with the others. Without saying what the problem is (how it manifests itself), there is little chance that anyone is going to comb through the code to find the error.

There were actually several problems with the code ... please see added comments, fixes and ... small test program ...

// test_DoublyLinkedList.h.cpp //


#ifndef DoublyLinkedList_H
#define DoublyLinkedList_H

#include <iostream>
#include <cassert>

//Definition of the node
template < class Type >
struct NodeType
{
    Type info;
    NodeType < Type >* next;
    NodeType < Type >* back;

    // ctor added ... //
    NodeType( const Type& info = Type(0) )
    : info(info), next(NULL), back(NULL) {}
} ;

template < class Type >
class DoublyLinkedList
{
public:
    DoublyLinkedList();
      //default constructor
      //Initializes the list to an empty state.
      //Postcondition: first = NULL; last = NULL; count = 0;

    DoublyLinkedList( const DoublyLinkedList< Type >& otherList );
      //copy constructor

    ~DoublyLinkedList();
      //destructor

    const DoublyLinkedList< Type >& operator =
        ( const DoublyLinkedList< Type > & );
      //Overload the assignment operator.

    //void initializeList(); // redundant ... same as 'clear' //
      //Function to initialize the list to an empty state.
      //Postcondition: first = NULL; last = NULL; count = 0;

    bool empty() const;
      //Function to determine whether the list is empty.
      //Postcondition: Returns true if the list is empty,
      //               otherwise returns false.

    void clear(); // more consistent with general use to name 'clear()'
      //Function to delete all the nodes from the list.
      //Postcondition: first = NULL; last = NULL; count = 0;

    void print() const;
      //Function to output the info contained in each node.

    void reversePrint() const;
      //Function to output the info contained in each node
      //in reverse order.

    int size() const;
      //Function to return the number of nodes in the list.
      //Postcondition: The value of count is returned.

    Type front() const;
      //Function to return the first element of the list.
      //Precondition: The list must exist and must not be empty.
      //Postcondition: If the list is empty, the program terminates;
      //    otherwise, the first element of the list is returned.

    Type back() const;
      //Function to return the last element of the list.
      //Precondition: The list must exist and must not be empty.
      //Postcondition: If the list is empty, the program terminates;
      //    otherwise, the last element of the list is returned.

    bool find( const Type& findItem ) const;
      //Function to determine whether findItem is in the list.
      //Postcondition: Returns true if findItem is found in the
      //    list, otherwise returns false.

    void insert( const Type& insertItem );
      //Function to insert insertItem in the list.
      //Precondition: If the list is nonempty, it must be in order.              
      //Postcondition: insertItem is inserted at the proper place
      //    in the list, first points to the first node, last points
      //    to the last node of the new list, and count is 
      //    incremented by 1.

    void erase( const Type& deleteItem );
      //Function to delete deleteItem from the list. 
      //Postcondition: If found, the node containing deleteItem is
      //    deleted from the list; first points to the first node of
      //    the new list, last points to the last node of the new 
      //    list, and count is decremented by 1; otherwise an
      //    appropriate message is printed. 


      //Postcondition: The list object is destroyed.

private:
    NodeType < Type >* first; //pointer to the first node
    NodeType < Type >* last;  //pointer to the last node
    int count;

    void copyList( const DoublyLinkedList< Type >& otherList );
      //Function to make a copy of otherList.
      //Postcondition: A copy of otherList is created and assigned
      //    to this list.
} ;



template < class Type >
DoublyLinkedList< Type >::DoublyLinkedList()
    : first(NULL), last(NULL), count(0) {}

template < class Type >
bool DoublyLinkedList< Type >::empty() const
{
    return first == NULL; // or count == 0 ... //
}

template < class Type >
void DoublyLinkedList< Type >::clear()
{ 
    NodeType< Type >  *temp; //pointer to delete the node

    while( first != NULL )
    {
        temp = first;
        first = first->next;
        delete temp;
    }

    last = NULL;
    count = 0;
}
/*
template < class Type >
void DoublyLinkedList< Type >::initializeList()
{
    clear();
}
*/
template < class Type >
int DoublyLinkedList< Type >::size() const
{
    return count;
}

template < class Type >
void DoublyLinkedList< Type >::print() const
{
    NodeType < Type >* current; //pointer to traverse the list

    current = first;  //set current to point to the first node

    while( current != NULL )
    {
        std::cout << current->info << "  ";  //output info
        current = current->next;
    }//end while
}//end print


template < class Type >
void DoublyLinkedList< Type >::reversePrint() const
{
    NodeType < Type >* current; //pointer to traverse
                             //the list

    current = last;  //set current to point to the 
                     //last node

    while( current != NULL )
    {
        std::cout << "'" << current->info << "'  ";
        current = current->back;
    }//end while
}//end reversePrint

template < class Type >
bool DoublyLinkedList< Type >::
    find( const Type& findItem ) const
{
    // bool found = false; // redundant
    NodeType < Type >* current; //pointer to traverse the list

    current = first;

    // advance ...
    while( current != NULL && /*!found*/ current->info != findItem  )
        //if (current->info >= findItem)
            //found = true;
        //else
            current = current->next;

    // ok ... now check end conditions ... //

    if( current != NULL ) // then found ...
       //found = (current->info == findItem); //test for
                                              //equality
        return true;

    //return found;
    // else ... NOT FOUND ... //
    return false;
}//end find

template < class Type >
Type DoublyLinkedList< Type >::front() const
{
    assert( first != NULL );

    return first->info;
}

template < class Type >
Type DoublyLinkedList< Type >::back() const
{
    assert( last != NULL );

    return last->info;
}

template < class Type >
void DoublyLinkedList< Type >::insert(const Type& insertItem)
{
    NodeType < Type >* current;      //pointer to traverse the list
    NodeType < Type >* trailCurrent; //pointer just before current
    NodeType < Type >* newNode;      //pointer to create a node
    //bool found; // redundant

    newNode = new NodeType< Type >( insertItem ); //create the node
    newNode->info = insertItem;  //store the new item in the node
    //newNode->next = NULL;
    //newNode->back = NULL;

    if( first == NULL)  //if the list is empty, newNode is
                      //the only node
    {
       first = newNode;
       last = newNode;
       //count++;
    }
    else // at least one element ... new element could be first //
    {
        //found = false;
        current = first;

        trailCurrent = first; // added ... //

        // traverse list to find insertion spot... //
        while( current != NULL && /*!found*/
               current->info <= insertItem ) //find the list
            //if (current->info >= insertItem)
                //found = true;
            //else
            {
                trailCurrent = current;
                current = current->next;
            }

        // now examine 'while loop' end conditions ...

        if( current == first ) //insert newNode before first
        {
            first->back = newNode;
            newNode->next = first;
            first = newNode;
            //count++;
        }
        else
        {
              //insert newNode between trailCurrent and current
            if( current != NULL )
            {
                trailCurrent->next = newNode;
                newNode->back = trailCurrent;
                newNode->next = current;
                current->back = newNode;
            }
            else
            {
                trailCurrent->next = newNode;
                newNode->back = trailCurrent;
                last = newNode;
            }

            //count++;
        }//end else
    }//end else

    ++count;

}//end insert

template < class Type >
void DoublyLinkedList< Type >::erase( const Type& deleteItem )
{
    NodeType < Type >* current; //pointer to traverse the list
    NodeType < Type >* trailCurrent; //pointer just before current

    //bool found; // redundant ... could be eliminated ... //

    if( first == NULL )
        std::cout << "Cannot delete from an empty list." << std::endl;
    else if( first->info == deleteItem ) //node to be deleted is
                                       //the first node
    {
        current = first;
        first = first->next;

        if( first != NULL )
            first->back = NULL;
        else
            last = NULL;

        count--;

        delete current;
    }
    else 
    {
        //found = false;
        current = first;

        while( current != NULL && /*!found  ) */  //find the list
            // if( current->info >= deleteItem )
            current->info != deleteItem )

                //found = true;
            //else
            current = current->next;

        if( current == NULL )
            std::cout << "The item to be deleted is not in "
                 << "the list." << std::endl;
        //else if( current->info == deleteItem ) //check for
                                                //equality
        else // found
        {
            trailCurrent = current->back; 
            trailCurrent->next = current->next;

            if( current->next != NULL )
                current->next->back = trailCurrent;
            // added
            else last = trailCurrent;

            //if( current == last )
                //last = trailCurrent;

            count--;
            delete current;
        }
        /*
        else
            std::cout << "The item to be deleted is not in list."
                 << std::endl;
        */
    }//end else
}//end erase

template < class Type >
void DoublyLinkedList< Type >::
    copyList( const DoublyLinkedList< Type >& otherList )
{
    NodeType < Type >* newNode; //pointer to create a node
    NodeType < Type >* current; //pointer to traverse the list

    if( first != NULL ) //if the list is nonempty, make it empty
       //destroyList(); // you meant to type destroy() ... //
       clear();
/*
    if( otherList.first == NULL ) //otherList is empty
    {
        first = NULL;
        last = NULL;
        count = 0;
    }
    else
*/
    if( otherList.first ) // list to be copied is NOT empty ... //
    {
        current = otherList.first; //current points to the 
                                   //list to be copied
        count = otherList.count;

        //construct the first node ...
        first = new NodeType< Type > ( current->info ) ;  //create the node

        //first->info = current->info; //copy the info
        //first->link = NULL;        //set the link field of
                                   //the node to NULL
        last = first;              //make last point to the
                                   //first node
        current = current->next;     //make current point to
                                     //the next node

           //copy the remaining list
        while( current != NULL )
        {
            newNode = new NodeType< Type > ( current->info ); //create a node
            //newNode->info = current->info; //copy the info
            //newNode->link = NULL;         //set the link of
                                        //newNode to NULL

            newNode->back = last; // added ...  //

            last->next = newNode;  //attach newNode after last
            last = newNode;        //make last point to
                                   //the actual last node
            current = current->next;   //make current point
                                       //to the next node
        }//end while
    }//end else
}

template < class Type >
DoublyLinkedList< Type >::
    DoublyLinkedList( const DoublyLinkedList< Type >& otherList )

{
    first = NULL;
    copyList( otherList );
}

template < class Type >
const DoublyLinkedList< Type >& DoublyLinkedList< Type >::
    operator = ( const DoublyLinkedList< Type > &otherList )
                                            // added &otherList ... //
{ 
    if( this != &otherList ) //avoid self-copy
    {
        copyList( otherList );
    }//end else

     return *this; 
}



template < class Type >
DoublyLinkedList< Type >::~DoublyLinkedList()

{
   //destroyList(); // typo ... you meant to type clear()
   clear();
}

#endif


#include <string>

// a little test program added ... //
int main()
{
    DoublyLinkedList < std::string > myLst, copy;

    myLst.insert( "Sam" );
    myLst.insert( "Joe" );
    myLst.insert( "Joey" );
    myLst.insert( "Joseph" );
    myLst.insert( "Koe" );
    myLst.insert( "Zoe" );

    myLst.print();
    std::cout << "\nmyLst.reversePrint()... \n";
    myLst.reversePrint();

    if( myLst.find( "Joey" ) )
        std::cout << "\nJoey was found ... \n";
    else
        std::cout << "\nJoey was NOT found ... \n";


    copy = myLst;
    std::cout << "\nPrinting copy ... \n";
    copy.print();
    std::cout << "\ncopy.size = " << copy.size() << std::endl;
    std::cout << "Printing copy reversed... \n ";
    copy.reversePrint();

    std::cout << "\n\nAfter erase Koe, Joe and Zoe ... \n";
    myLst.erase( "Koe" );
    myLst.erase( "Joe" );
    myLst.erase( "Zoe" );
    myLst.print();
    std::cout << "\nmyLst.size = " << myLst.size() << std::endl;

    if( myLst.find( "Joe" ) )
        std::cout << "Joe was found ... \n";
    else
        std::cout << "Joe was NOT found ... \n";

    std::cout << "\nNow ... myLst.reversePrint()... \n";
    myLst.reversePrint();

    std::cout << "\nmyLst.front() is " << myLst.front();
    std::cout << "\nmyLst.back() is " << myLst.back();

    std::cout << "\n\nPress 'Enter' to continue/exit ... " << std::flush;
    std::cin.get();
}
This article has been dead for over six months. Start a new discussion instead.