链表逻辑

Question

我在理解链表的流程时遇到了一点困难。

我的列表及其节点有这些类型定义。

typedef struct node node_t;
struct node{
    data_t data;
    node_t *next;
};
typedef struct {
    node_t *head;
    node_t *foot;
} list_t;
list_t *insert_at_foot(list_t *list, data_t value) {
    node_t *new;
    new = malloc(sizeof(*new));
    assert(list!=NULL && new!=NULL);
    new->data = value;
    new->next = NULL;
    if(list->foot==NULL){
        //this is the first insertion into the list
        list->head = list->foot = new;
    }else{
        list->foot->next = new;
        list->foot = new;
    }
    return list;
}

具体来说，这个代码低于

if(list->foot==NULL){
    //this is the first insertion into the list
    list->head = list->foot = new;
}else{
    list->foot->next = new;
    list->foot = new;
}

我知道我们将头和脚分配给节点"new"，因为它是第一个节点，但我不理解下面的行。在我看来，如果我们将这个新节点分配到列表的末尾（脚部），

list->foot->next = new;

应该是，

list->foot->next = NULL;

我只是不明白把脚指针和它的下一个指针都分配给同一个节点（新的）的意义

这一直困扰着我，因为这个概念很容易理解。

Answer 1

您所了解的是简单的链表和称为循环链表

简单的答案有两个。（1） 它允许在列表的开头或末尾添加节点的永久引用，并且（2）它们提供了在列表中迭代的起点和终点。但是，你必须让他们来实现一个链表吗否

循环链表使end->next指向first，从而无需保留任何HEAD,TAIL指针（因此名称为循环链表。我同时使用了这两个列表，并很快放弃了HEAD,TAIL简单列表，转而使用环形链表。为了获得这两个的好处，您可以添加一个额外的指针HEAD0，并使该列表成为圆形双链表

循环列表比简单列表更难实现吗？->否，它只需要一个不同的add_node函数。让我们来看看。显示简单和循环列表之间的关系和差异的图表有助于（显示双链接列表）：

             Tail                 Current                Head
         (node->prev)              node              (node->next)
        +------------+        +------------+        +------------+
        |   payload  |        |   payload  |        |   payload  |
        +------------+        +------------+        +------------+
+<------|   prev     |<-------|   prev     |<-------|   prev     |<------+
|       +------------+        +------------+        +------------+       |
|  +--->|   next     |------->|   next     |------->|   next     |--->+  |
|  |    +------------+        +------------+        +------------+    |  |
|  |                                                                  |  |
|  +<--------------------<---------------------<----------------------+  |
|                                                                        |
+------------------------>--------------------->------------------------>+

如果仔细观察，您会发现简单和循环列表在所有实际用途上都是完全相同的，但是，在简易的情况下，您必须跟踪HEAD,TAIL指针，但对于环形，实现逻辑会为您跟踪它们。这就是区别，这就是为什么你的问题的答案：分配HEAD,TAIL指针的意义？只是提供新节点的插入以及迭代的起点和终点。如果你在实现中很聪明，那么你就不必担心分配它们，你的列表逻辑会为你跟踪它们。考虑到这一点，这里有一个实现循环列表而不需要跟踪HEAD,TAIL的示例。

对于您的数据结构，您通常会有：

typedef struct list {
    char *data;
    struct list *prev;
    struct list *next;
} list;

然后您就有了create node和insert node的函数注意：insert node函数调用create node，但如果您选择，可以全部在HEAD, TAIL0中完成。：

list *create_node (char *str) {
    list *node = NULL;
    node = malloc (sizeof (struct list));   /* allocate memory for new node      */
    node-> data = strdup (str);             /* allocate and save payload data    */
    return node;                            /* return node poiter to add to list */
}
list *insert_at_end (list **ll, char *str) {
    /* create the node and allocate memory for node and payload
    if no list, then create and assign as list address
    else, insert new node at end of list */
    list *node = NULL;              // create a new node pointer for list
    node = create_node (str);       // allocate new node and fill payload
        /* now just Wire/Rewire list pointers to accept node */
    if (!*ll) {                     // this is the first node
        node-> next = node;            // circular linked-list
        node-> prev = node;            // set next, prev = node
        *list = node;                  // set *list = node (adding node to list)
    } else {                        // add - insert new node at end
        node->next = *ll;              // set node->next to list
        node->prev = (*ll)->prev;      // set node->prev to list->prev
        node-> prev-> next = node;     // set (old end)->next to this node
        (*ll)-> prev = node;           // set list->prev to node
    }
    return node;                    // return pointer to current node for convenience
                                    // (immediate reference) and to test success
}

在你的main()中，你只需要有类似的东西：

list *mylist = NULL;
int i = 0;
// add data to your list (example using argv entries)
for (i = 0; i < argc; i++)
    insert_at_end (&mylist, argv[i]);
...

希望这能帮助你理解。无论您使用简单还是循环、单或双链表，只要确保您理解逻辑以及为什么要进行每个分配。这只是一场得分游戏。它们都是简单的数据结构，但确实需要一条陡峭但短暂的学习曲线。花点时间学习一次，从那时起，它们会为你提供很好的服务。网上有很多简单和循环列表的教程和指南。现在知道了区别，这将使你更容易找到你需要的东西。

Answer 2

如果我们没有列表的尾部，那么在链接列表的末尾插入是O（n）。如果我们只有列表的头，我们应该遍历列表，找到末尾并在列表的末尾插入项（以防我们想保留插入顺序）。为了避免这种情况，人们通常会把名单排在后面。例如，如果您的列表是1->2->3，并且您想在列表中添加4。在这种情况下，头部为1，尾部为3。所以

list->foot->next = 4

意味着我们的列表将是1->2->3->4，下一行list->foot = new;将尾部（脚部）分配给4，以确保对于另一个插入，我们有更新的尾部（脚部（foot））。