Linked List Concatenation

[jjroyale]

Having trouble with concatenating a linked list.. Can anyone tell me why when I call the display function for the concatenated list, it loops endlessly?

#include <iostream>
#include <cstdlib>
using namespace std;
#ifndef Null	//Null is being defined to 0 here
	#define Null 0
#endif

class Node	//Class for our Node
{
	public:
		int data;	//Data portion
		Node *link;	//Pointer to node called link (the link section)
					//This will point to a successor if there is one
};

class LList	//Class for our Linked List
{
	public:
		LList ();	//default constructor
		~LList();	//default destructor
		void create();	//create function
		void display();	//display function
		Node* getNode();	//getNode function, returns a Node pointer
		void append(Node* NewNode);	//append function, add to end, pass it a node's address
		void insert(Node *NewNode, int pos);	//insert function, pass it a node's address and position
		void rtraverse();	//visits all the positions to make sure everything is OK
		void deleteNode(int pos);	//deleteNode function, pass it a position to delete
		void concatenate(LList A);	//function to conjoin two linked lists
	private:
		Node *Head, *Tail;	//Create pointers Head and Tail, that will point to a node
		void recursiveTraverse (Node *tmp) // passed a pointer called tmp, points to a node
											//just visits all the positions
		{
			if (tmp == Null)	//if what was passed was empty (null)
			{
				return;	//get out
			}
			cout << tmp->data << "\t";	//output what is in that node
			recursiveTraverse (tmp->link);	//call fct again, but pass it next node
											//which is the link of our current node
		}
};

LList :: LList ()
{
	Head = Tail = Null;	//set head and tail to NULL
						//empty LList
}

LList :: ~LList () //DESTRUCTOR: Think of a cart loading, rerouting, and deleting
{
	Node *Temp;	//Create a pointer called Temp, it will point to a node
	while (Head != Null)	//while the beginning of the list != NULL
	{
		Temp = Head;	//make temp equal to the head (copying this cell to temp cart)
		Head = Head->link;	//Head is rerouted to it's link (next node/successor)
		delete Temp;	//get rid of temp (what we loaded in the cart)
	}
}

void LList :: create ()	//create constructor
{
	char ans;	//Variable to hold Y or N from user
	Node *NewNode;	//create a Node pointer called NewNode
	while (1)	//while there is an input
	{
		cout << "Any more nodes to be added (Y/N):";
		cin >> ans;
		if (ans == 'n' || ans == 'N')
		{
			break;
		}
		NewNode = getNode ();	//create a NewNode in memory, call the function	
		append(NewNode);	//calls append function, adds the NewNode to the end
	}
}

void LList :: append(Node *NewNode)	//function passed a pointer called NewNode
									//this will point to a node
{
	if (Head == Null)	//if it was empty
	{
		Head = NewNode;	//make NewNode cell the head
		Tail = NewNode;	//make NewNode the tail as well
	}
	else
	{
		Tail->link = NewNode;	//the last spot (link) will now point to NewNode
		Tail = NewNode;	//tail is now NewNode because it is the last member
	}
}

void LList :: insert (Node *NewNode, int pos)
{
	Node *temp = Head;	//Create a node pointer called temp, points to the beginning
	int count = 1, flag = 0;
	
	if (pos == 1)	//inserting at first position
	{
		NewNode->link = temp;	//our new node's link is now temp
								//which was set to the Head
		Head = NewNode;	//Head is now pointing to our NewNode
	}
	else	//not first position
	{
		while (count != pos-1)	//stops at the position right before where we want
		{
			temp = temp->link;	//set our temp pointer (pointing to Head or beginning link)
								//to that link's successor (link), so next node really
			if (temp = Null)
			{
				flag = 1;	//raise flag this is the end
				break;	//break out of this loop
			}
			count ++;
		}
		
		if (flag == 0) //if flag was never raised, we didn't get to the end
		{
			NewNode->link = temp->link; //our NewNode will point will come between
										//temp and its link (next node)
			temp->link = NewNode;	//make temp now point to this newNode
		}
		else
		{
			cout << "\nPosition was not found!\n";
		}
	}
}

Node* LList :: getNode()	//function returns a pointer to Node
{
	Node *NewNode;	//create a Node pointer called NewNode
	NewNode =  new Node;	//NewNode will now point to a new Node created
	cin >> NewNode->data;	//data inputted goes to the data portion of this Newnode
	NewNode->link = Null;	//the back (link) section of this Newnode is now Null
	return (NewNode);	//return the address of the Newnode
}

void LList :: display()	//function to display the node
{
	Node *temp = Head;	//Create a pointer to node called temp
						//Set it equal to the first node (head of list)
	if (temp == Null)	//If this head was actually Null, the list is empty
	{
		cout << "Empty List";
	}
	else
	{
		while(temp != Null)	//While we know it is not an empty list
		{
			cout << temp->data << "\t";	//Output the pointed to cell's data portion
			temp = temp->link;			//Set temp = the link of this cell
										//which points to the successor's head
		}
	}
	cout << endl;
}

void LList :: rtraverse ()
{
	recursiveTraverse(Head);
	cout << "\n";
}

void LList :: deleteNode(int pos)
{
	int count = 1;
	int flag = 0;
	Node *current, *temp;	//Pointers to point to nodes
	
	temp = Head;	//temp pointer is now first node
	if (pos == 1)	//If we need to delete first position
	{
		Head = Head->link;	//Head is equal to what it was pointing to
							//Next spot
		delete temp;	//Delete whatever temp pointed to (Head)
	}
	else
	{
		while (count != pos-1)	//Stop at node before the actual one
		{
			temp = temp->link;	//Keep moving from link to link (node to node)
			if (temp == Null)	//If we reached the end
			{
				flag = 1;	//Raise the flag
				break;	//Get out of loop
			}
			count ++;
		}
		
		if (flag == 0)	//If we didnt reach the end
		{
			current = temp->link;	//current equals the node to be deleted
									//what previous node (temp) points to
			temp->link = current->link;	//set previous node (temp)'s link to what
										//current node was linking to, because we 
										//will delete this
			delete current;
		}
		else
		{
			cout <<"\nPosition not found!\n";
		}
	}
}

void LList :: concatenate (LList A)
{
	Node *X, *Y;	//two node pointers
	
	X = Head;	//X is the head of the caller LList
	Y = A.Head;	//Y is the head of the passed LList
	
	while (X->link != Null)	//While we are not at the end of the caller
	{
		X = X->link;	//Continue to the successor
	}
	
	X->link = Y;	//set the end's link to the start of the passed LList
	Head = X;	//head of caller is pointing to the union
	
	cout << "Head is" << Head->data;
}

int main()
{
	LList L1, L2;	//creates a Linked List called L1
	Node *NewNode;
	
	L1.create();
	L1.display();
	
	L2.create();
	L2.display();
	
	L1.concatenate(L2);
	
	L1.display();
	
	return 0;
}

[jjroyale]

I revised the LList concate code.. not sure why this doesn't work..

template <typename T>
void LList <T> :: concatenate (LList B)
{
	Node <T> *X, *Y, *Union;	//	pointers
	X = Head;	//head of caller
	Y = B.Head;	//head of passed list
	
	while (X->link != NULL)	//while we are not at the end of caller
	{
		X = X->link;	//go to next spot
	}
	
	X->link = Y;	//we are at the end
					//reroute this link to passed list's head
	Union = X;	//mark the spot where they were combined
	
	while (X->link != NULL)	//while we are not at the end of our concatenated list
	{
		X = X->link;	//go to next spot
	}
	
	Tail = X;	//we are at the end of passed list, set caller's tail to this end
	
	delete B.Head;	//delete passed list's head
	delete B.Tail;	//delete passed list's tail
	delete X;
	delete Y;
}

Main's call looks like...

L1.concatenate(L2);

[jjroyale]

Any idea here? Thanks.

[D80DSL3A]

I think your first version of concatenate() was closer. It looks right to me except for line 221 Head = X; which would exclude all but the last node of L1. I think you should not reassign Head.

I don't see what would cause the list to be repeated on display(). This would require A.Tail->next = Head; be assigned, creating a circular list but I don't see that.

A major problem is surely being caused because A is passed by value. This results in a copy of A produced, and the subsequent destruction of A at function end - not just the copy.

Try passing A by reference instead.
void LList :: concatenate (LList& A)<-- note the & in the argument type.

EDIT: I recommend assigning A.Head = 0; at the end of the concatenate() to prevent the nodes in that list (which have become a part of L1) from being deleted twice when L1 and L2 destructors get called at the end of main().

On second thought. The destruction of A was already assured due to the pass by value method used, so dual destruction was (inadvertently) prevented by this. However, this wrecks the concatenation.

You're now working with a template class? Deleting Nodes isn't right in a concat function.

[writetonsharma]

I agree with fun2code. Changing the definition to
void LList :: concatenate (LList* A)
will work. For C code, I will prefer a pointer to a reference.

[jjroyale]

That worked...

template <typename T>
void LList <T> :: concatenate (LList& B)
{
	Node <T> *X, *Y, *Union;	//two node pointers
	
	X = Head;	//X is the head of the caller LList
	Y = B.Head;	//Y is the head of the passed LList
	
	while (X->link != NULL)	//While we are not at the end of the caller
	{
		X = X->link;	//Continue to the successor
	}
	
	X->link = Y;	//set the end's link to the start of the passed LList
	Union = X;	//union points to where they were 
	
	cout << "Head is: " << Head->data;
	cout << "Tail is: " << Tail->data;
}

I also threw in Tail = B.Tail; to mark the new end of the concatenated list.