Singly Linked List, insert at end

Question

Due to reasons beyond my control, the function declaration must not change. I'm not very good with pointers, so the NODE** declaration really throws me off.

I know the basic gist is more or less correct. I just keep getting errors due to the pointers and don't know how to solve it.

There is currently an error in this line of the else statement:

NODE* last = data;

//a value of type "NODE **" cannot be used to initialize an entity of type "NODE *"

Yet I don't know if I've been handling the pointers correctly.

class NODE {
  public:
    string firstname;
    string lastname;
    string email;
    NODE* next;
};

void add_node_tail(NODE** data, string firstname,string lastname, string email) {
    NODE* temp = new NODE;
    temp->firstname = firstname;
    temp->lastname = lastname;
    temp->email = email;
    temp->next = NULL;

    if(!data) { // empty list becomes the new node
        data = &temp;
        return;
    } else { // find last and link the new node
        NODE* last = data;
        while(last->next) {
            last=last->next;
            last->next = temp;
        }
    }
}

If you could give me a rundown of how the pointers would work in the correct implementation, that would be the perfect answer.

"Due to reasons out of my control" = "This is a school assignment", isn't it? Please be sure to check whether your school's policy allows you to ask questions about homework. — Nikita Demodov, Mar 22 '21 at 16:34
Do you have an example of how `add_node_tail` is called, and why it is called that way? — 1201ProgramAlarm, Mar 22 '21 at 16:34
@NikitaDemodov I did check! There is no mention about any rules on asking questions. So why not? — Agustin, Mar 22 '21 at 16:41

score 2 · Accepted Answer · answered Mar 22 '21 at 16:34

NODE** data is a pointer to NODE*, so you should dereference the pointer like *data to get the value of NODE*.

void add_node_tail(NODE** data, string firstname,string lastname, string email) {
    NODE* temp = new NODE;
    temp->firstname = firstname;
    temp->lastname = lastname;
    temp->email = email;
    temp->next = NULL;

    // *** dereference data to get the value ***
    if(!*data) { // empty list becomes the new node
        // *** dereference data to set the value ***
        // also remove the extra & not to save a pointer to local variable
        *data = temp;
        return;
    } else { // find last and link the new node
        // *** dereference data to get the value ***
        NODE* last = *data;
        while(last->next) {
            last=last->next;
            last->next = temp;
        }
    }
}

Note there is a neat trick you can use to skip the first test and reduce the amount of code needed. The [**Community Addition** here](https://stackoverflow.com/a/22122095/4581301) shows how to remove a node using a pointer to a pointer, but the insertion logic is similar. — user4581301, Mar 22 '21 at 16:41

user4581301 · Answer 2 · 2021-03-22T23:24:54.623

A slightly different way to look at the problem.

data is (or better be because the asker's code and all of the answers won't work if it is not) pointer to a next pointer. The head pointer is a next pointer by another name; think of it as the first next pointer. There's nothing special about it, so if you abstract away the different name by taking a pointer to it, you can write much simpler code. data has already done this first step.

This means all you need to do is find the first null next pointer and point it at the new node.

void add_node_tail(NODE** data, string firstname,string lastname, string email) {
    while (*data) { // if data points at a non-null next
        data = &(*data)->next; // point at the pointer to the next node
    }
    *data = new NODE{ firstname, lastname, email, NULL }; // insert at last next
}

Note: new NODE{ firstname, lastname, email, NULL }; is making use of aggregate initialization to make the initialization easier to write.

Singly Linked List, insert at end

2 Answers2