Add reverse function to doubly linklist class

[hanani]

hello every body .. i want to solve this program ..i tried to slove it but i want your help
Add a function reverse () to the class doublyLinkedLis t, that will reverse the order of all elements in the doubly linked list, your function should display a suitable error message whenever the list is empty or there is only one element in the list otherwise it should perform the reverse operation.
To test your functions write a main program that will create a doubley linked list containing 5 strings ,print the content of the list, then call the reverse function and display the content of the list after reversing it.

You will need to define the following:
1- insertLastNode function inserts a new element at the end of the list.
2- print() function displays the content of the list.

 
#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
{
    friend ostream& operator<<(ostream&, 
                           const doublyLinkedList<Type>&);
       //Overload the stream insertion operator
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();
      //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 reversePrint();
      //Function to output the info contained in each node
      //in the reverse order

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

    Type front();
      //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();
      //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);
      //Function to determine whether searchItem is in the list.
      //Postcondition: Returns true if searchItem is found
      //               in the list; otherwise, it returns false.

    void insertNode(const Type& insertItem);
      //Function to insert newItem in the list.
      //Precondition: If the list is nonempty, it must be in
      //              order.
      //Postcondition: newItem 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. the 
      //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()
{
    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()
{
	return count;
}

template<class Type>
ostream& operator<<(ostream& osObject, 
					const doublyLinkedList<Type>& list)
{
    nodeType<Type> *current; //pointer to traverse the list

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

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

	return osObject;
}

template<class Type>
void doublyLinkedList<Type>::reversePrint()
{
      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)
{
    bool found;
    nodeType<Type> *current; //pointer to traverse the list

    found = false;
    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()
{
      assert(first != NULL);

	      return first->info;
}

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

      return last->info;
}

template<class Type>
void doublyLinkedList<Type>::insertNode(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
    assert(newNode != NULL);

    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 new node 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 insertNode


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)
      cerr<<"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)
{
	cout<<"The definition of this function is left as an exercise."<<endl;
	cout<<"See Programming Execrise 9."<<endl;
}

template<class Type>
doublyLinkedList<Type>::doublyLinkedList(const doublyLinkedList<Type>& otherList)
{
	  cout<<"The definition of the copy constructor is left as an exercise."<<endl;
	  cout<<"See Programming Execrise 9."<<endl;
}

template<class Type>
const doublyLinkedList<Type>& doublyLinkedList<Type>::operator=
							(const doublyLinkedList<Type> &)
{
	cout<<"Overloading the assignment operator is left as an exercise."<<endl;
	cout<<"See Programming Execrise 9."<<endl;
}

template<class Type>
doublyLinkedList<Type>::~doublyLinkedList()
{
	cout<<"Definition of the destructor is left as an exercise."<<endl;
	cout<<"See Programming Execrise 9."<<endl;
}

#endif

[Banfa]

Reversing the order of a doubly linked list all you have to do is for every node swap the next and back pointers.

Care is required when traversing the list during the operation because of the pointer swap. If you start at the head post swap on any node the "next" pointer is actually stored in the nodes back pointer.

[hanani]

i write this code for this problem but i'm not very sure about it and i need to change the reverse number to a reverse 5 element of type string ..soo please help me

 
#include <iostream> 
using namespace std; 
class Node{ 
public: 
Node *next; 
Node *before; // added for double liked list
int data; 
Node( int _data ) { before=NULL;next=NULL ; data=_data;}; 
}; 

class List{ 
Node *first ; 
Node *last ; 
public: 
List(Node* _first) { first = _first; last = first ; } 
~List () { 
while ( first ) { 
Node *temp = first->next; 
delete first; 
first = temp; 
} 
} 

void add(Node* node) { last->next = node; 
node->before = last ;// addded for double linked list
last = node; } 

Node* begin() { return first ; };

void show (){ 
cout<<"\n walk on next....\n";
for( Node* i = begin(); i; i=i->next ) 
cout << i->data << "-" ; 
show2();////!!!!!! 
} 
/////////////// added for double linked list
void show2 (){ 
cout<<"\n walk on before....\n";
for( Node* i = last; i; i=i->before ) 
cout << i->data << "-" ; 
} 

void reverse(){ 
Node *before = first ; 
Node *current = first ->next ; 
Node *further = current->next ; 
before -> next = NULL ; 
for ( ;further ; before=current , 
current=further , further= further-> next ){ 
current->next = before ; 
}
current->next = before ; 
current = first;
first = last ;
last = current ;
reverse2(); ///!!!!!!

}; 
////////////// addded for double linked list
void reverse2(){ 
Node *before = first ; 
Node *current = first ->before ; 
Node *further = current->before ; 
before -> before = NULL ; 
for ( ;further ; before=current , 
current=further , further= further->before ){ 
current->before = before ; 
}
current->before = before ; 
}
}; 

int main(){ 
List l ( new Node(1) ); 
for ( int i = 2 ; i <= 10 ; i++ ) 
l.add( new Node (i) ); 

cout<<"\n before reverse :"; 
l.show(); cout<<endl<<endl; 

l.reverse(); 
cout<<"\n after reverse :\n"; 
l.show(); cout<<endl<<endl; 

}

[weaknessforcats]

Er, don't you reverse a double-linked list by just traversing from the end to the front?

[jkmyoung]

Node *before = first ;  
Node *current = first ->before ;  
Node *further = current->before ;

I'm pretty sure this will give a null error. current will be set to null. Then you're asking for the before of null.

It really is easier just to have a seperate case for reversing a doubly linked list as opposed to a singly linked one, and call only that one. The code is closer to

current = first. 
while current isn't null{
  temp = current.before
  current.before = current.next
  current.next = temp
  current = current.before //used to be the one after it. 
}

[donbock]

Which is your precise requirement:

• Traverse the list in reverse order (back-to-front), printing the nodes as they are encountered.
• Doing the above PLUS actually altering the list so its order is reversed.

If you do need to actually alter the list then you can test your code by calling your reversal function two or three times in succession, making sure the output is correct each time. This verifies that the link pointers are changed properly.