Why this code works well in Linux but failed in Windows?

Question

I write some code of linked list: The definition of linked list:

struct Node {
    // data is used to store an integer value in this node
    int data;
    // a pointer points to the next node
    Node* link;
    // inializes the node with a 0 value in data and a null pointer in link
    Node() : data(0), link(NULL) {};
    // destructor release space allocated to the linked list
    ~Node() {delete link;}
};

display linked list:

void display_and_count(Node* aLink) {
    cout << "Entries: ";
    int nodeNumber = 0;                         // elements number of linked list
    for(Node* iterator = aLink; iterator->link != NULL; iterator=iterator->link) {
        cout << iterator->data << ", ";
        nodeNumber++;
    }
    cout << "contans " << nodeNumber << " nodes." << endl;
}// end display_and_count

Now I write a function split one linked list to two ones LESS and MORE based on a threshold and remove nodes in original linked list:

void split_them_up(Node* aLink, Node* less, Node* more, int threshold) {
    Node* lessHead = less;                              // head of less
    Node* moreHead = more;                              // head of more
    bool isThresholdInALink = false;                    // store if threshold is an element of aLink
    for(Node* iterator = aLink; iterator->link != NULL; iterator = iterator->link) {
        if(iterator->data < threshold) {
            less->data = iterator->data;
            less->link = new Node;
            less = less->link;
        }
        else if(iterator->data > threshold) {
            more->data = iterator->data;
            more->link = new Node;
            more = more->link;
        }
        else {
            isThresholdInALink = true;
        }
    } // end for(Node* iterator = aLink; iterator->link != NULL; iterator = iterator->link)

    less = lessHead;
    more = moreHead;

    delete aLink;
    // If threshold is an element of aLink, then the new linked list contains the only threshold.
    // If threshold isn't in aLink, then the new linked list contains nothing
    aLink = new Node;
    if(isThresholdInALink) {
        aLink->data = threshold;
        aLink->link = new Node;
    } // end if(isThresholdInALink)*/
} // end split_them_up

Then this is main function:

int main() {
    Node* ENTRIES = new Node;           // define a linked list

    get_input(ENTRIES);
    display_and_count(ENTRIES);

    Node* less = new Node;              // define less list
    Node* more = new Node;              // define more list
    cout << "Enter a threshold: ";
    int thd;                            // threshold
    cin >> thd;
    split_them_up(ENTRIES, less, more, thd);

    cout << "Less list: " << endl;
    display_and_count(less);
    cout << "More list: " << endl;
    display_and_count(more);
    cout << "ENTRIES: " << endl;
    display_and_count(ENTRIES);
}

get_input function get some integer from user and -1 to end:

void get_input(Node* aLink) {
    Node* head = aLink;                 // head of linked list
    int capacity=1;                     // the capacity of intArray
    int* intArray = new int[capacity];  // an array stores user input
    int size=0;                         // actual number of elements stored in the intArray

    cout << "Input some integers, -1 to end: ";
    while(true) {
        int input;
        cin >> input;
        if(input == -1) break;
        if(!isContained(intArray, size, input)) {
            intArray[size]=input;
            size++;
            // if size meets capacity, double capacity
            if(size >= capacity) {
                int* temp = new int[capacity];
                int oldCapacity = capacity;
                for(int i=0; i < oldCapacity; i++) temp[i]=intArray[i];
                delete[] intArray;
                capacity = 2*capacity;
                intArray = new int[capacity];
                for(int i=0; i < oldCapacity; i++) intArray[i]=temp[i];
                delete[] temp;
            } // end if(size >= capacity)
        } // end if(!contained(intArray, size, input))
    } // end while(true)

    for(int i=0; i<size; i++) {
        aLink->data = intArray[i];
        aLink->link = new Node;
        aLink = aLink->link;
    }
    delete[] intArray;
    aLink = head;
} // end get_input

isContained:

bool isContained(int* array, int aSize, int n) {
    for(int i=0; i<aSize; i++) {
        if(array[i] == n) return true;
    }
    return false;
} // end isContained

When executing in Linux system everything is OK. But in windows it will show a random value in ENTRIES after split_them_up and program will crash giving a "Access violation reading location".

Answer 1

Of course you'll crash when manipulating ENTRIES; the split_them_up function deleted the Node object that it points to.

From the looks of it, you intended to declare aLink as pointer-to-pointer so that you can actually change the value of ENTRIES to point to the newly declared Node (which at the moment you are leaking).

Alternatively, instead of deleting aLink you could delete the child node and reuse aLink, i.e., replace this:

delete aLink;
aLink = new Node;
if(isThresholdInALink) {
    aLink->data = threshold;
    aLink->link = new Node;
}

with this:

delete aLink->link;
if(isThresholdInALink) {
    aLink->data = threshold;
    aLink->link = new Node;
} else {
    aLink->data = 0;
    aLink->link = NULL;
}

Why does the bad code work on Linux? At a guess, the newly declared Node is coincidentally created in the same location as the original deleted node, so ENTRIES accidentally points to the right place.

I'll also comment that you don't need lessHead or moreHead; they're not doing anything useful. Remove them completely. Just like aHead, since less and more are not declared as pointers-to-pointers, the values in the calling function won't be affected by anything that happens inside split_them_up.

Additional: the destructor,

~Node() {delete link;}

is liable to overflow the stack if the link is large. Recursion is a fine thing, but not when carried to extremes. :-)

Answer 2

I don't know if this will solve the problem, but i'm pretty sure you do not want a destructor like that for the node.

1. There's no new, so there's no need for a delete.
2. How are you going to implement deletion of a certain node of a list if it triggers deletion of the next node, and the next, and the next...?