Pointers in linked lists

0
votes

I'm studying lists currently (trying to recreate them) and I came across a weird problem. Here's my struct:

struct listNode{
    listNode(int n, listNode* ne = NULL){
        value = n;
        next = ne;
    }
    int value;
    listNode* next;
};
listNode* head = NULL;

Now I made a function to add an element to the bottom:

void add(int n){
    if(head == NULL){
        head = new listNode(n);
        return;
    }
    listNode* n1 = head;
    while(n1 != NULL){ //Should be: while(n1->next != NULL){
        n1 = n1->next;
    }
    n1 = new listNode(n); //Should be: n1->next = new listNode(n);
}

But this isn't adding any element past the head. Now, I already figured out the solution (see comments above) my problem is that I do not understand why my first function didn't work.
I'll explain what I understood with a scheme:

The Beginning
HEAD = NULL;

I add 1
HEAD = [1, NULL];

I add 2
The while loop arrives at the last element (where "next" is NULL) and creates in it the new element
HEAD = [1, new listNode(2)];
Result
HEAD = [1, POINTER] [2, NULL];

Now, why n1 after the while loop isn't what I wan't it to be?

3
c++pointerslinked-listsingly-linked-list
Never title a question "How pointers work?". The title should be something related to LinkedLists - asimes
@asimes Didn't know really what to write, sorry. Anyway, silent downvoters, care to explain? - Xriuk
Let's say you have int n = 5; int m = n; m = 7. Do you expect n should become 7? Don't think so. But nevertheless you say n1 = n1->next; n1 = new listNode(n); and expect the next member of previous n1 to change. Weird, huh? - n. 1.8e9-where's-my-share m.
@n.m. If after n1 = n1->next; n1 is null I want it to point to the new element - Xriuk
Then you should assign the new element to the attribute next of the last element. Before saying "but n1 is the attribute next of the last element", look again at m = n; m = 7. Are you assigning 7 to n? - n. 1.8e9-where's-my-share m.

3 Answers

2
votes

You can think of it this way: no matter what you used to do within the while loop, the condition of the while loop was such that the loop would only terminate once n1 became null. So, the value of n1 was guaranteed to be null after the loop.

However, the value of n1 after the while loop was irrelevant, because you were not using it after the while loop.

On the other hand, your last instruction was n1 = new listNode(n); so you were creating a new listNode, and assigning it to n1, which you were then forever forgetting by leaving the function. (So, the new node was being leaked.)

1
votes

Is is simple, 

while(n1 != NULL){
    n1 = n1->next;
}

// n1 here is null
// head here is [1, NULL]

n1 = new listNode(n);

// n1 here is something
// head here is [1, NULL]

so unless you set the previous element's next pointer of the head to your new element, it won't work

1
votes

The function does not work becuase n1 is a local variable of the function. Any changes of the variable do not influence on other nodes of the list.

You should change the original nodes of the list. The function can be written the following way

void add( int value )
{
    listNode **node = &head;

    while ( *node ) node = &( *node )->next;

    *node = new listNode( value );
}

In this case because variable node points to the actual fields of the list it indeed changes them.