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?

 ``123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242`` ``````#include #include 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..

 ``12345678910111213141516171819202122232425262728`` ``````template void LList :: concatenate (LList B) { Node *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.
closed account (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.
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...

 ``12345678910111213141516171819`` ``````template void LList :: concatenate (LList& B) { Node *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.