How to create a bi-directional linked list and do not use pointer in ADT?

Question

Now I am trying to define an ADT and use it to create a linked list, and I want to let it fit the function List newList(void);. I know what should I do if it's like List* newList(void);. If I am trying to do fit List* newList(void);, then I will define this ADT like

typedef struct List{
    struct List *next;
    struct List *prev;
    int number;
} List;

But If I define in this way, the nodes in linked list will be all pointers, which I don't want to use. Now I try to define linked list in the way below.

typedef struct List{
    struct List next;
    struct List prev;
    int number;
} List;

But I received the error message:

List.h:4:17: error: field ‘next’ has incomplete type
    4 |     struct List next;
      |                 ^~~~
List.h:5:17: error: field ‘prev’ has incomplete type
    5 |     struct List prev;
      |                 ^~~~

I tried to move typedef into .c file (now it's in header file), but it still not work. Can someone help me please?

Answer 1

But If I define in this way, the nodes in linked list will be all pointers, which I don't want to use

You are mistaken. All nodes in the list will have the type struct List. But they will be allocated dynamically.

As for this function

List newList(void);

then it just does not make a sense.

You need to declare the function like

List * newList( int number );

For example

List * newList( int number )
{
    List *node = malloc( sizeof( List ) );

    if ( node != NULL )
    {
        node->next = NULL;
        node->prev = NULL;
        node->number = number;
    }

    return node;
}

If you do not want to allocate nodes dynamically when you can use for example the approach when a list is defined as an array. In this case you can add nodes to the list using the function

List newList( int number )
{
    List node = { .next = NULL, .prev = NULL, .number = number };
    return node;
}

But in this case you need to declare one more structure that indeed will describe a list. Your current structure in fact declares just a node of a list.