Concatenating two linked lists

[spirit3ch]

Hi guys, I am supposed to implement a sequence using linked list. But I seem to have an error in the code. As I am getting trash for the results of the concatenate function. It might be a problem with my constructor too. I am not sure. Please help. I have pasted the code.

#include <iostream>
using namespace std;

typedef int ElementType;

struct Node
{
       ElementType data;
       Node* next;

};

class Sequence
{
      public:
             Sequence();
             
             Sequence(ElementType s);
             
             ~Sequence();
             
             
      
			 
			 Sequence concatenate(Sequence &s);
             
             void insert(ElementType s);
             ElementType remove();
             
             bool isEmpty();
             void printSeq();
             
      private:
              Node* head;
              
};

#include "sequence.h"



Sequence::Sequence()
{
                    head = NULL;
}

Sequence::~Sequence()
{
       while(head != 0)
       {
                  Node* iter = head;
                  head = head->next;
                  delete iter;
       }
}

                   
                            
                            
                            
Sequence::Sequence(ElementType s)
{
      Node *temp = new Node;
      temp->data = s;
      temp->next = head;
      head = temp;
     
	  	  
}


void Sequence::insert(ElementType s)
{
     Node *temp = new Node;
     temp->data = s;
     temp->next = head;
     head = temp;
    
     
}
        
ElementType Sequence::remove()
{
	ElementType delnode;
	Node* temp;
	if (head != NULL)
    {
		temp = head;
		head = head->next;
		delete temp;
	}

	return delnode;

}
Sequence Sequence::concatenate(Sequence &seqb)
{
         Sequence seqc;
                 
         Node* iterator = head;
         while (iterator != NULL)
         {
               seqc.insert(iterator->data);
               iterator = iterator->next;
         }
         
         Sequence tempseq;
         while (seqb.isEmpty() == false)
         {
               ElementType bnode;
               bnode = seqb.remove();
               seqc.insert(seqb.remove());
               tempseq.insert(bnode);
               
         }
         
         while (tempseq.isEmpty() == false)
         {
               ElementType tnode;
               tnode = tempseq.remove();
               seqb.insert(tnode);
               
         }
   return seqc;
   
}

bool Sequence::isEmpty()
{
	return(head == NULL);

}

void Sequence::printSeq()
{
	Node* iterator = head;
	if (head != NULL) {
		do
		{
			cout << iterator->data << " ";
			iterator = iterator->next;
		}while(iterator != NULL);
	}
	cout << endl;
}

int main()

{
	
	cout << "Some simple normal tests" << endl;
	
	Sequence s1;
	
	//some inserts
	s1.insert(4);
	s1.insert(8);
	s1.insert(15);
	s1.insert(16);
	s1.insert(23);
	s1.insert(42);
	
	//Should print out list
	cout << "List printed is: ";
	s1.printSeq();
	cout << "It should be 42 23 16 15 8 4" <<endl;
	
	
	s1.remove();
	s1.remove();
	s1.remove();
	
	
	cout << "List printed is: ";
	s1.printSeq();
	cout << "It should be 15 8 4" <<endl;
	
	
	Sequence s2 = s1;
	
	cout << "Should be same list again." <<endl;
	s1.printSeq();
	
	cout << "Should be same list again." << endl;
	s1 = s2;
	s1.printSeq();
	cout << "This is s2." << endl;
	s2.printSeq();
	
	s1.insert(8);
	s1.insert(15);
	s1.insert(16);
	
	cout << "These two should be different" << endl;
	
	s1.printSeq();
	s2.printSeq();
	
	
	Sequence s3 = s1.concatenate(s2);

	cout << "This is the concatenated list" << endl;
	
	s3.printSeq();
    
    cout << "Sequence 1" << endl;
    
    s1.printSeq();
    
    cout << "Sequence 2" << endl;
    
    s2.printSeq();
 
}

[mrnutty]

1) Your insert function is incorrect
2) Your remove function is mis informative, called it removeTop() or pop_front().
3) You concat function shouldn't be very hard(unless I am missing
something). All you have to do is either append the whole list you get
into your list front part or the rear. I will assume its towards the rear, or
the end. All you have to do is get a Node*ptr towards the end of your
list. Then keep adding the list content into the end. In fact, you should
make a function call addToEnd(ElementType val). Then you can just
call it inside your concat function.

4) You know how you are keeping a head Node. Keep a tail node as
well. Then you always have a node pointing to the end. This will make
things easier.

[spirit3ch]

1) Your insert function is incorrect
2) Your remove function is mis informative, called it removeTop() or pop_front().
3) You concat function shouldn't be very hard(unless I am missing
something). All you have to do is either append the whole list you get
into your list front part or the rear. I will assume its towards the rear, or
the end. All you have to do is get a Node*ptr towards the end of your
list. Then keep adding the list content into the end. In fact, you should
make a function call addToEnd(ElementType val). Then you can just
call it inside your concat function.

4) You know how you are keeping a head Node. Keep a tail node as
well. Then you always have a node pointing to the end. This will make
things easier.

Hi, thanks for your response. The insert function isn't giving me any trouble.

The remove function has to return an ElementType as stipulated in the assignment.

As per the assignment I don't have access to the head of seq2 that is why I can't append it to the end of the seq1. Most importantly the concat function has to be NON-DESTRUCTIVE so seq1 and seq2 need to be preserved after the function call. Hence I am not using a copy constructor. This is the only way I am supposed to do. The problem is that I am getting incorrect answers after running concat. Not only is the answer wrong both seq1 and seq2 change which should not happen. I reckon it's a problem either with the concatenate function

Sequence Sequence::concatenate(Sequence &seqb)

or the constructor. I am pasting my test class and the output for reference. Thanks.

int main()

{
        
        cout << "Some simple normal tests" << endl;
        
        Sequence s1;
        
        //some inserts
        s1.insert(4);
        s1.insert(8);
        s1.insert(15);
        s1.insert(16);
        s1.insert(23);
        s1.insert(42);
        
        //Should print out list
        cout << "List printed is: ";
        s1.printSeq();
        cout << "It should be 4 42 23 16 15 8" <<endl;
        
        //a couple of removes
        s1.remove();
        s1.remove();
        s1.remove();
        
        //Should print out list with three removed
        
        cout << "List printed is: ";
        s1.printSeq();
        cout << "It should be 4 15 8" <<endl;
        
        //This is the copy constructor
        Sequence s2 = s1;
        
        cout << "Should be same list again." <<endl;
        //this should print same list
        s1.printSeq();
        
        cout << "Should be same list again." << endl;
        s1 = s2;
        s1.printSeq();
        
        s1.insert(8);
        s1.insert(15);
        s1.insert(16);
        
        cout << "These two should be different" << endl;
        
        s1.printSeq();
        s2.printSeq();
        
        
        Sequence s3 = s1.conacatenate(s2);

        cout << "This is the concatenated list" << endl;
        s3.printSeq();

        cout<<"Sequence 1" << endl;
        s1.printSeq();
         
        cout << "Sequence 2" << endl;
        s2.printSeq();

}

Output

List printed is: 42 23 16 15 8 4 
It should be 42 23 16 15 8 4
List printed is: 15 8 4 
It should be 15 8 4
Should be same list again.
15 8 4 
Should be same list again.
15 8 4 
This is s2.
15 8 4 
These two should be different
16 15 8 15 8 4 
15 8 4 
This is the concatenated list
-4195648 -4195648 4 8 15 8 15 16 
Sequence 1
16 15 8 -4195648 -4195648 
Sequence 2
-4195648 -4195648

[masterovpuppetz]

In concatenate method, removal is being performed twice in a single loop. Shld be something like this

while (seqb.isEmpty() == false)
         {
               ElementType bnode;
               bnode = seqb.remove();
               seqc.insert(bnode);
               tempseq.insert(bnode);

         }

Also in remove method, delnode is being declared but not being assigned nething. Shld be like

if (head != NULL)
    {
		temp = head;
		head = head->next;
		delnode=temp->data;
		delete temp;
	}

After doing the above modifications the concatenation is taking place but the initial sequence r getting modified.

[spirit3ch]

Thank you so much! It's embarrassing that I missed those errors. Truly appreciate it. My seqa is getting changed. Let me see what the problem is.