如何在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

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

你错了。列表中的所有节点都将具有 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;
}

但在这种情况下，您需要再声明一个确实会描述列表的结构。您当前的结构实际上只声明了列表的一个节点。

如何在ADT中创建一个双向链表并且不使用指针？

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

c

struct

linked-list

doubly-linked-list

function-declaration