How to create a linked list without dynamic memory allocation as template in c++

I started working through the book Hands-On System Programming in C++ and I tried to create the following linked list with a template without dynamic memory allocation. But every time I try to build the linked list a find no other way than having to assign memory with new - how else would I create a new node?

As I understand the author there is a way to replace the need for creating a new node by using c++ templates since allocating dynamic memory is considered slow. And so far that doesn't mean using static memory allocation or an array nor macro programming at compile time but the same flexibility at runtime? Or is that a misunderstanding?

What am I missing? Thanks upfront for any hint on how can I create a linked list dynamically without dynamic memory allocation with c++ templates?.

"There are several implementations of these types of linked lists (and other data structures) floating around on the internet, which provide a generic implementation of a linked list without the need for dynamically allocating data." I didn't find any in C++ :(

and

"In the preceding example, not only are we able to create a linked list without macros or dynamic allocations (and all the problems that come with the use of void * pointers), but we are also able to encapsulate the functionality, providing a cleaner implementation and user API."

That is what I tried to do but every way I puzzle I have to allocate memory dynamically:

template<typename T>
class MyLinkedList
{
    struct node
    {
        T data;
        node* next = nullptr;
    };

private:
    node m_head;

public:


    void setData(T value)
    {
        if(m_head.next == nullptr){
        m_head.data = value;
        }
    }

    T getData()
    {
        return m_head.data;
    }


};

int main()
{
    MyLinkedList<int> list;
    list.setData(4);
    std::cout << list.getData() << std::endl;



    return 0;
}

The Whole text from this book about C++ Templates: Hands-On System Programming in C++

Templates used in C++

Template programming is often an undervalued, misunderstood addition to C++ that is not given enough credit. Most programmers need to look no further than attempting to create a generic linked list to understand why.

C++ templates provides you with the ability to define your code without having to define type information ahead of time.

One way to create a linked list in C is to use pointers and dynamic memory allocation, as seen in this simple example:

struct node  {
    void *data;
    node next; };

void add_data(node *n, void *val);

In the preceding example, we store data in the linked list using void *. An example of how to use this is as follows:

node head; add_data(&head, malloc(sizeof(int)));
*(int*)head.data = 42;

There are a few issues with this approach:

This type of linked list is clearly not type-safe. The use of the data and the data's allocation are completely unrelated, requiring the programmer using this linked list to manage all of this without error. A dynamic memory allocation is needed for both the nodes and the data. As was discussed earlier, memory allocations are slow as they require system calls. In general, this code is hard to read and clunky.

Another way to create a generic linked list is to use macros. There are several implementations of these types of linked lists (and other data structures) floating around on the internet, which provide a generic implementation of a linked list without the need for dynamically allocating data. These macros provide the user with a way to define the data type the linked list will manage at compile time.

The problem with these approaches, other than reliability, is these implementations use macros to implement template programming in a way that is far less elegant. In other words, the solution to adding generic data structures to C is to use C's macro language to manually implement template programming. The programmer would be better off just using C++ templates.

In C++, a data structure like a linked list can be created without having to declare the type the linked list is managing until it is declared, as follows:

template<typename T> class mylinked_list {
    struct node 
    {
        T data;
        node *next;
    };

public:

    ...

private:

    node m_head; };

In the preceding example, not only are we able to create a linked list without macros or dynamic allocations (and all the problems that come with the use of void * pointers), but we are also able to encapsulate the functionality, providing a cleaner implementation and user API.

One complaint that is often made about template programming is the amount of code it generates. Most code bloat from templates typically originates as a programming error. For example, a programmer might not realize that integers and unsigned integers are not the same types, resulting in code bloat when templates are used (as a definition for each type is created).

Even aside from that issue, the use of macros would produce the same code bloat. There is no free lunch. If you want to avoid the use of dynamic allocation and type casting while still providing generic algorithms, you have to create an instance of your algorithm for each type you plan to use. If reliability is your goal, allowing the compiler to generate the code needed to ensure your program executes properly outweighs the disadvantages.

What am I missing? Thanks upfront for any hint on how can I create a linked list dynamically without dynamic memory allocation with c++ templates?.

a find no other way than having to assign memory with new - how else would I create a new node?

You can declare a variable. Or, you can create a dynamic object into non-dynamic memory using placement-new.

Here is minimal example of linked list using node variables:

template<class T>
struct node
{
    T data;
    node* next = nullptr;
};

// some function
node<int> n3{3, nullptr};
node<int> n2{2, &n3};
node<int> n1{1, &n2};

Reusing non-dynamic storage for dynamic objects is quite a bit more complicated. I recommend a structured approach of using a pre-existing implementation such as std::list with a custom allocator.