How should I initialize linked list in C++?

Question

I have an array which I have to initialize into a list What I try to do

#include <stdio.h>
#include <string.h>

struct data_t 
{
    unsigned int id_;
    char name_ [50];
};

struct node_t
{
    node_t * next_;
    data_t data_;
};

void initialize(node_t **, const char **, const unsigned int);

int main()
{
    node_t * first = NULL;
    const char * data [3] = {"Alpha", "Bravo", "Charlie"};

    initialize(&first, data, 3);

    return 0;
}

void initialize(node_t ** head, const char ** data, const unsigned int n) {
    node_t * current = NULL;
    node_t * previous = NULL;
    for (size_t i = 0; i < n; i++)
    {
        current = new node_t;
        current->next_ = previous;
        current->data_.id_ = i+1;
        strcpy(current->data_.name_, data[i]);

        if (i == 1)
        {
            *head = previous;
            previous->next_ = current;
        } else {
            previous = current;
        }     
    }
};

next_ just loops and changes between 2 values. I tried many different options but nothing works. Please help. Why is this happening?

Think about `if (i == 1)` and what happens if `i == 2` for example (which it will be in your loop). — Some programmer dude, Feb 24 '22 at 18:51
you are getting downvotes because you didnt supply all the code so we cant test it out — pm100, Feb 24 '22 at 18:53
ask yourself , why am I doing something special on the second node. That `if (i == 1)` is very odd — pm100, Feb 24 '22 at 18:55
I would consider writing a C++ linked list and not a C linked list. — sweenish, Feb 24 '22 at 19:00
@SilverMoon17 you have added code, but what you show here [still does not compile](https://godbolt.org/z/vbGPz6z8T). — Drew Dormann, Feb 24 '22 at 19:08
Echoing Sweenish's comment in a way, but if you are learning the C++ languages, your educational materials seem to be pushing the C language hard. You may to [get some different materials](https://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list) — user4581301, Feb 24 '22 at 19:21
Are you allowed to use `std::string` instead of `char` arrays? — Ted Lyngmo, Feb 24 '22 at 19:23
One of the best ways to [grok](https://en.wikipedia.org/wiki/Grok) a linked list is to draw pictures. Follow the coded instructions exactly, stepping through the function with a debugger to see what really happens with your code will help a lot here, and see if you can draw the list. If you cannot, you'll know where the code went wrong and probably have a really good idea what you should have done instead. — user4581301, Feb 24 '22 at 19:26
@SilverMoon17 Ok, too bad. Anyway, I would try to break it down in smaller pieces. Make an `insert` function that inserts _one_ `data_t` into the list. You can then loop in `initialize` and call that repeatedly. [example](https://godbolt.org/z/v9xhPfYsz) — Ted Lyngmo, Feb 24 '22 at 19:30
@user4581301 Yes, I've been doing this for about two hours, but nothing comes out, I kind of understand how it should work, but I can't translate it into code correctly — SilverMoon17, Feb 24 '22 at 19:30
@SilverMoon17 Sure, but are you _forbidden_ to create helper functions? If you are, you could still simplify it: [example](https://godbolt.org/z/Y9reraq74) — Ted Lyngmo, Feb 24 '22 at 19:33
The way I initialize a linked list is to set the head pointer and the tail pointer to `nulptr`. — Thomas Matthews, Feb 24 '22 at 21:06

pm100 · Accepted Answer · 2022-02-24T21:05:08.390

You need to do something special in the case of 'first' vs 'not first', you knew this but had it wrong.

On the first one (i==0) you need to set head so the caller gets the pointer to the first node
on subsequent ones you have to set the prior ones next pointer to point at current. For the first one there is no prior

Plus you set the current->next to point to previous, thats wrong too, that made your loop

So this is what you need

for (size_t i = 0; i < n; i++)
{
    current = new node_t;
    current->next_ = NULL; <<<======
    current->data_.id_ = i + 1;
    strcpy(current->data_.name_, data[i]);
    if (i == 0)
        *head = current;
    else
        previous->next_ = current;
    previous = current;
   
}

Yeah, it works, thank you, I understood my mistake – SilverMoon17 Feb 24 '22 at 19:54 — SilverMoon17, Feb 24 '22 at 19:54

score 1 · Answer 2 · answered Feb 24 '22 at 20:00

Since you can't use std::strings, I suggest that you add a constructor to data_t that can copy the char array:

struct data_t {
    data_t(unsigned id, const char* name) :
        id_{id} // can be copied automatically
    {
        // the char array needs to be copied manually:
        std::strncpy(name_, name, sizeof name_ - 1);
        name_[sizeof name_ - 1] = '\0';
    }

    unsigned int id_;
    char name_[50];
};

With that, your initialize function could be simplified to

// last in `data`, first in the list:
void initialize(node_t*& head, const char** data, const unsigned int n) {
    for (unsigned int i = 0; i < n; i++) {
        // create a new `node_t` with `next_` pointing at the current `head`
        // `data_` will be initialized by calling the added constructor
        // assign the returned `node_t` to `head`
        head = new node_t{head, {i + 1, data[i]}};
    }
}

or

// first in `data`, first in the list:
void initialize(node_t*& head, const char** data, const unsigned int n) {
    for (unsigned int i = n; i > 0; --i) {
        head = new node_t{head, {i, data[i - 1]}};
    }
}

Note that initialize takes head by reference (&) to make calling it simpler:

int main() {
    node_t* first = nullptr;
    const char* data[3] = {"Alpha", "Bravo", "Charlie"};

    initialize(first, data, 3); // not &first here
}

Demo

How should I initialize linked list in C++?

2 Answers2