Runtime error in Linked List

Question

I have been working with Linked Lists (for learning purpose, using class). I decided to use friend function this time. The program generates 2 linked lists objects and calls the friend void mergeAlternate(LL LL1, LL LL2); function. (LL is the name of my class)

The mergeAlternate function takes nodes from both the linked list and places them alternatively. For example:

LL1: 1->2->3

LL2: 4->5->6

Ans: 1->4->2->5->3->6

This is my code::

#include <iostream> using namespace std; class Node { public: int data; Node *next; Node(int data) { this->data = data; this->next = NULL; } }; class LL { private: Node *head; public: LL() : head(NULL) { createLL(); } void printLL(Node *head) { if(head == NULL) head = this->head; Node *temp = head; while (temp != NULL) { cout << temp->data << "-->"; temp = temp->next; } cout << "NULL" << endl; } void createLL() { head = new Node(2); head->next = new Node(7); head->next->next = new Node(8); head->next->next->next = new Node(1); head->next->next->next->next = new Node(4); head->next->next->next->next->next = new Node(9); } friend void mergeAlternate(LL LL1, LL LL2); ~LL() { Node *temp = NULL; while (head != NULL) { temp = head; head = head->next; delete temp; } } }; void mergeAlternate(LL LL1, LL LL2) { Node *head1 = LL1.head, *head2 = LL2.head; Node *temp1, *temp2; while ((head1 != NULL) && (head2 != NULL)) { temp1 = head1->next; temp2 = head2->next; head1->next = head2; head2->next = temp1; if (temp1 == NULL) break; head1 = temp1; head2 = temp2; } if (head2 != NULL) { head1->next = head2; } LL2.head = NULL; LL1.printLL(LL1.head); } int main() { LL newLL, newLL2; newLL2.printLL(NULL); mergeAlternate(newLL, newLL2); newLL2.printLL(NULL); }

I have a printLL function used to print the linked list.

The problem is that in my mergeAlternate I pass 2 Linked Lists by value. So, I expect the Linked list newLL and newLL2 to remain the same. But, in the main, after the execution of the mergeAlternate when I print the Linked List, I get a runtime error, and something like this prints.

155672576-->155672672-->155672592-->155672688-->155672608-->155672704-->155672624-->155672720-->155672640-->155672736-->155672656-->NULL

Though I expect the same input Linked List to print again. Why does this happen?? Is there something that I am missing?? Thanks for any help :)

ideone link :: http://ideone.com/apRCTw

Ediac · Accepted Answer · 2015-06-28 00:09:13Z

Your function void mergeAlternate(LL LL1, LL LL2) creates two new local variables LL and LL2 whose member head will also point to the same memory address that newLL and newLL2 respectively points to. Because LL1 and LL2 are local variables of the function, when the function ends, their respective destructors will be called. According to your destructor definition:

~LL() { Node *temp = NULL; while (head != NULL) { temp = head; head = head->next; delete temp; } }

It will de-allocate the Nodes of LL1 and LL2, however because these are the same memory addresses as newLL and newLL2 that means that when the function ends these last two objects will be having garbage values in their member head and subsequent references, which will cause errors when trying access their values.

They won't be NULL but they'll point to garbage hence the random values being printed. Still that's how the random values end up being printed.

aslg · Accepted Answer · 2015-06-28 00:09:30Z

I see a few pitfalls in there.

You're passing your lists by value, including their internal pointers. This means that the lists that are created by copy within the function point to the same data structures as the original lists. So any changes you make inside the function will be "seen" in the original lists.

You did what would be called a "shallow copy" of the list. You didn't copy the contents of the list.

To solve this you need to make a deep copy of your lists. Either make a function that creates a copy of a list or create copies of the nodes as you iterate over them. The first solution is probably less error prone though.

Daniel Jour · Accepted Answer · 2015-06-27 23:53:17Z

You pass LL by value, but since that class is only a wrapper around a pointer to your nodes you are actually passing two pointers to the heads of the respective lists.And since you're then modifying the nodes these pointers point to, which are the same nodes that the LL instances of the caller are using, you're effectively modifying the callers lists.Just think about how many different nodes there should be after calling your function:

LL1: 1->2->3 LL2: 4->5->6 Ans: 1->4->2->5->3->6

That's 2 times 3 nodes for LL1 and LL2 plus 6 for the answer, making a total of 12 nodes. When constructing LL1 and LL2 you allocated 6 nodes.

To solve this you need to make (allocate) copies of the nodes as you are merging the lists, modifying only these copies.

Collectives™ on Stack Overflow

Runtime error in Linked List

3 Answers 3

1 Comment

Comments

Comments

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

1 Comment

Comments

Comments

Related