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

4

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.

edited Jun 28, 2015 at 0:09

answered Jun 28, 2015 at 0:01

Ediac

8537 silver badges14 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

aslg Over a year ago

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

3

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.

edited Jun 28, 2015 at 0:09

answered Jun 27, 2015 at 23:53

aslg

1,9842 gold badges15 silver badges20 bronze badges

Comments

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

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

1 Comment

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related