Linked List Concatenation

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?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
#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;
}
I revised the LList concate code.. not sure why this doesn't work..

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
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);
Last edited on
Any idea here? Thanks.
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.
Last edited on
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.
That worked...

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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.
Topic archived. No new replies allowed.