哪个更好的存储ANSI C链表?通过使用*头或使用其他结构

Question

我正在学习链表(单&从我读过的许多基础教程来看，教程平均有两种存储链表的方法。如:

<
1. 使用*头/gh>

struct ListItem *head;
struct ListItem *a = (struct ListItem *) malloc(sizeof(struct ListItem));
a->data = 10;
a->next = NULL;
struct ListItem *b = (struct ListItem *) malloc(sizeof(struct ListItem));
b->data = 25;
b->next = NULL;
// Link it!
head = a;
a->next = b;

使用其他结构(struct jsw_list)作为代码示例:

struct jsw_list {
    struct jsw_node *head;
    struct jsw_node *tail;
    size_t size;
};
struct jsw_list *new_list(int has_dummy_head, int has_dummy_tail)
{
    struct jsw_list *rv = (struct jsw_list *) malloc(sizeof(struct jsw_list));
    //.
    //.
    //.
}
struct jsw_list *list = new_list(1,1);
struct jsw_node *node;
node = insert_after(list, list->head, 10000);
node = insert_after(list, node, 5000);

哪个更好?

请启蒙运动

谢谢

Answer 1

简短的回答:没有更好的办法。

但是…这可能取决于你打算做什么。假设您想使用单个链表，只是为了存储而不需要花哨的操作。

您将只需要列表项，并保留第一个如下;

typedef struct listItem{
    void * content;
    struct * listItem next;
}ListItem;
ListItem first;

或者如果你想要一个双链表:

typedef struct listItem{
    void * content;
    struct * listItem previous;
    struct * listItem next;
}ListItem;
ListItem first;

另一方面，如果你想跟踪大小和其他东西，比如列表中某些类型的数量，那么有一个新的数据结构来跟踪它们可能是一个不错的选择。

typedef struct listItem{
    void * content;
    struct * listItem previous;
    struct * listItem next;
}ListItem;
typedef struct list{
    ListItem * first, * last;
    int quantity;
}List;
List myList;

不需要有指向列表的指针。但是你可以。在第二种实现中，您可以在必须遍历列表才能获得的东西(例如数量)上获得性能。但是现在你必须在每次添加或删除一个项目时不断更新数量。

Answer 2

一个版本还跟踪尾指针和列表的大小，因此它具有额外的功能。在您的特定情况下，这些功能是有用的补充还是无用的膨胀，这取决于您。

哪个版本更好取决于具体的用例。