C Linked List creation-CodePudding

I was looking through the code for creating a linked list and almost everywhere I have observed that a function to add a node is given even if the number of nodes are known and then add operation for node is executed one by one for each element.

Why can't one simply create an array of nodes with new operator and assign the values from simple raw values array and just connect the links?

Something like this:

Node* create_list(unsigned int n, unsigned int arr[]) {
    Node* head = new node[n];

    for (unsigned int i = 0; i < n; i  ) {
        head[i].data = arr[i];

        if (i != n - 1)
            head[i].next = head[i   1];
        else
            head[i].next = NULL;
    }
}

Is this a valid code to create a linked list from array?

CodePudding user response：

May be helpful to add your Node definition as well, but i think that can be inferred as having a next and data member / field.

What you've made is an array, where each element has a pointer to the next element in the array, and a data value.. could accomplish the same with an array of unsigned ints.

How do you add an element to the "linked list"? how do you remove it? Try to understand the concept of a linked list in natural language before putting it to code.

As an aside, in your for-loop, you have a check that's false n-1 times and only true at the end.. could make the small optimization by doing that NULL assignment after the loop. as in:

for (unsigned i = 0; i < n-1;   i){
  head[i].data = arr[i] ;
  head[i].next = head[i 1]; // this is just extra space with a linked list as an array
}
head[n-1].data = arr[n-1];
head[n-1].next = NULL;

you're doing one assignment an extra time to save yourself a few lines of code and a condition checked n-1 times (compiler may optimize out)

Finally, once you do have a solid understanding of linked lists, avoid using raw pointers in C , you have smart pointers available to you as a huge QoL upgrade from C.

CodePudding user response：

In a multi-threaded embedded environment, it's pretty common to use arrays to do a one time creation of linked lists, which in turn are used as queues or stacks or pools of pre-allocated fixed sized objects. Example code:

NODE * CreateList(size_t count){
    NODE *pList;
    NODE *pNode;
    pList = new(std::nothrow) NODE[count]; // embedded code may have alternative to new
    if(!pList)
        return pList;
    pNode = pList;    // create list
    for(size_t i = 0; i < count; i  ){
        pNode->data = ...   // for empty pool, data usually not initialized
        pNode->next = pNode 1;
        pNode  ;
    }
    (--pNode)->next = NULL;
    return pList;

// ...
DeleteList(NODE * pList){
    delete[] pList;
}