CODEWITHSUNDEEP
c++pointerslinked-listsingly-linked-list
Xriuk
Xriuk

Reputation: 487

Pointers in linked lists

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?

Upvotes: 0

Views: 320

Answers (3)

Vlad from Moscow
Vlad from Moscow

Reputation: 310980

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.

Upvotes: 1

Mike Nakis
Mike Nakis

Reputation: 61993

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.)

Upvotes: 2

Pedro Sassen Veiga
Pedro Sassen Veiga

Reputation: 174

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

Upvotes: 1

Related Questions