如何创建双向链接列表，并且不使用ADT中的指针？

Question

现在我试图定义一个ADT并用它来创建一个链表，我想让它适合函数List newList(void);。我知道如果像 List* newList(void); 那样我该怎么办。如果我试图拟合List* newList(void);，那么我将像这样定义这个ADT，

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

但是如果我以这种方式定义，链表中的节点将都是指针，我不这样做不想用。现在我尝试用下面的方式定义链表。

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

但我收到错误消息：

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;
      |                 ^~~~

我尝试将 typedef 移动到 .c 文件中（现在它在头文件中），但它仍然不起作用。有人可以帮我吗？

Answer 1

但是，如果我以这种方式定义，链接列表中的节点将全部
指针，我不想使用

你是错误的。列表中的所有节点都将具有类型struct List。但是它们将动态分配。

至于此功能

List newList(void);

，这是没有意义的。

您需要声明该函数，

List * newList( int number );

例如，

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

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

    return node;
}

如果您不想在可以使用列表定义为数组时动态分配节点时，则可以动态分配节点。在这种情况下，您可以使用该功能将节点添加到列表中，

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

但是在这种情况下，您需要声明一个确实可以描述列表的结构。实际上，您当前的结构仅声明列表的节点。