Home > database >  Cannot iterate a temp NODE to iterate in a Linked List of nodes but if I do parent->child->nex
Cannot iterate a temp NODE to iterate in a Linked List of nodes but if I do parent->child->nex

Time:08-13

I have a problem that I cannot introduce a temp NODE* and iterate to find the next NODE that is NULL (I marked it in the code with comment).

But, if I do:

parent->child->next->next = result

It works completely fine.

Any help?

typedef struct tNODE {
    char* inner_text;
    char* tag;
    struct tNODE* parent;
    struct tNODE* child;    
    struct tNODE* next;

}NODE;


NODE* new_node(NODE* parent){
    
    NODE* result = (NODE*)malloc(sizeof(NODE));
    result->inner_text = NULL;
    result->tag = NULL;
    result->parent = parent;
    result->child = NULL;
    result->next = NULL;
    if (parent != NULL){
        if (parent->child == NULL){
            parent->child = result;
        } else {
            if (parent->child->next == NULL){
                parent->child->next = result;
                return result;
            }  else {
                //HERE IS THE PROBLEM. A TEMP NODE DOES NOT WORK
                //BUT parent->child->next->next = result works. WHY ? what should i do
                NODE* temp = parent->child->next;
                while(temp != NULL){
                    temp = temp->next;
                }
                temp = result;
            }              
        }  
    }

    return result;
}

CodePudding user response:

If the parent has no children, you set the new node as the 1st child. OK.

If the parent has 1 child, you set the new node as the 2nd child. OK.

But, if the parent has more than 2 children, you are looping to the end of the child list, which is where you are going wrong. You are setting temp to point at each child in the list, and break the loop only when temp becomes NULL, meaning it is not pointing at any node at all, as you went beyond the end of your list. You lost track of the last child in the list. And then you are setting temp to point at the new node, but temp does not refer to the last child's next pointer in the list, so assigning it a value does not update the list at all.

Your logic needs to look more like this instead:

NODE* new_node(NODE* parent){

    NODE* result = (NODE*) malloc(sizeof(NODE));
    if (!result)
        return NULL;

    // in C  , use this instead:
    // NODE* result = new NODE;

    result->inner_text = NULL;
    result->tag = NULL;
    result->parent = parent;
    result->child = NULL;
    result->next = NULL;

    if (parent){
        // if no children yet, assign the
        // new node as the first child ...
        if (!parent->child){
            parent->child = result;
        } else {
            // find the last child ...
            NODE *temp = parent->child;
            while (temp->next){
                temp = temp->next;
            }
            // ... and set it to point at the
            // new node as the next child ...
            temp->next = result;
        }  
    }

    return result;
}

That being said, the logic can be simplified a bit more. Try this instead:

NODE* new_node(NODE* parent){
    
    NODE* result = (NODE*) malloc(sizeof(NODE));
    if (!result)
        return NULL;

    result->inner_text = NULL;
    result->tag = NULL;
    result->parent = parent;
    result->child = NULL;
    result->next = NULL;

    if (parent){
        // find the last NODE* pointer that is NULL ...
        NODE **temp = &(parent->child);
        while (*temp) {
            temp = &((*temp)->next);
        }
        // ... and set it to point at the new node ...
        *temp = result;
    }

    return result;
}

And, if you are free to add another member to your NODE type, the logic becomes even simpler as the entire loop can then be eliminated completely, eg:

typedef struct tNODE {
    char* inner_text;
    char* tag;
    struct tNODE* parent;
    struct tNODE* first_child;
    struct tNODE* last_child;
    struct tNODE* next;

}NODE;

NODE* new_node(NODE* parent){
    
    NODE* result = (NODE*) malloc(sizeof(NODE));
    if (!result)
        return NULL;

    result->inner_text = NULL;
    result->tag = NULL;
    result->parent = parent;
    result->first_child = NULL;
    result->last_child = NULL;
    result->next = NULL;

    if (parent){
        NODE **temp = (parent->last_child)
            ? &(parent->last_child->next)
            : &(parent->first_child);
        *temp = result;
        parent->last_child = result;
    }

    return result;
}

CodePudding user response:

The assignment to temp can never change the linked list. To modify the linked list you need to dereference temp when it still points to the tail node, and then assign to its next member.

So that means you need to stop the loop one iteration earlier:

                NODE* temp = parent->child;
                while (temp->next != NULL) {
                    temp = temp->next;
                }
                temp->next = result;

Note that you don't need the innermost if as a special case. The case where parent->child->next == NULL can be dealt with using the code above.

CodePudding user response:

Look at the two alternatives, they are quite different

parent->child->next->next = result;

and

NODE* temp = parent->child->next;
while(temp != NULL){
    temp = temp->next;
}
temp = result;

The first one assigns to the next field of parent->child->next. The second assigns to the temp variable. These are not the same thing, it doesn't matter where the temp variable is pointing to when you make the assignment, the temp variable is not any part of your linked list.

Here is what your code should look like

NODE* temp = parent->child;
while(temp->next != NULL){
    temp = temp->next;
}
temp->next = result;

In this code temp points to the node whose next field you want to change.

  • Related