链表添加到尾部，混乱 [英] linked list adding to the tail, confusion

问题描述

Visual Studio 2008 C

Visual Studio 2008 C

关于这个链表，我无法理解的是在 if 语句的 else 部分添加尾部.

What I can't understand about this linked list is the adding to the tail in the else part of the if statement.

当head和tails被分配node_temp的内存地址时，tail和head都指向同一个内存位置.

When the head and tails is assigned the memory address of the node_temp to both tail and head both point to the same memory location.

然而，在 else 部分，头部实际上仍然指向尾部.关于 else 部分，有什么我无法解释和不理解的地方?

However, in the else part is the head in fact still pointing to the tail. There is just something I can't explain and don't understand about the else part?

我希望有人能更好地为我解释.

I hope some one can explain better for me.

static struct convert_temp
{
    size_t cel;
    size_t fah;
    struct convert_temp *next;
} *head = NULL, *tail = NULL;

/** Add the new converted temperatures on the list */
void add(size_t cel, size_t fah)
{
    struct convert_temp *node_temp = NULL; /* contain temp data */

    node_temp = malloc(sizeof(*node_temp));

    if(node_temp == NULL)
    {
        fprintf(stderr, "Cannot allocate memory [ %s ] : [ %d ]
",
            __FUNCTION__, __LINE__);
        exit(0);
    }

    /* Assign data */
    node_temp->cel = cel;
    node_temp->fah = fah;
    node_temp->next = NULL;

    if(head == NULL)
    {
        /* The list is at the beginning */
        head = node_temp;   /* Head is the first node = same node */
        tail = node_temp;   /* Tail is also the last node = same node */
    }
    else
    {
        /* Append to the tail */
        tail->next = node_temp;
        /* Point the tail at the end */
        tail = node_temp; 
    }
}

推荐答案

第一次向列表中添加元素(我们称之为 A)时，head 是null 并通过 if 部分.这意味着在添加第一个元素时 head 和 tail 都被设置为指向 A.

The first time you add an element (let's call it A) to the list, head is null and you go through the if part. That means that both head and tail are set to point to A when adding that first element.

现在让我们添加另一个元素 B.这一次，head 不为空，所以它通过了 else 部分，设置 tail 指向 B 但离开 head 指向 A.

Now let's add another element B. This time, head is not null so it goes through the else part, setting tail to point to B but leaving head pointing at A.

正如预期的那样，您现在有 head 指向 A，A 指向 B，B 不指向任何内容(空)，tail 指向 B.

This is as expected, you now have head pointing to A, A pointing to B, B pointing to nothing (null) and tail pointing to B.

让我们一步一步来.

Initial state:  head -+-> null
                      |
                tail -+

Insert item A:  head -+-> A ---> null
                      |
                tail -+

Insert item B:  head ---> A -+-> B ---> null
                             |
                tail --------+

Insert item C:  head ---> A ---> B -+-> C ---> null
                                    |
                tail ---------------+

你可以看到在每个阶段(除了初始阶段)当前尾部被设置为指向新节点(它的下一个节点已经指向 NULL)然后尾部指针被更新为指向 new 最后一个节点.

You can see at each stage (other than the initial) that the current tail is set to point to the new node (which already points to NULL for its next node) then the tail pointer is updated to point to the new last node.

事实上，让我们以更多的细节(逐行)来查看 C 的添加，这样您就可以看到每行代码在做什么(我已将 node_temp 到 node 只是为了帮助格式化):

In fact, let's go through the addition of C in even more detail (line by line) so you can see what each line of code is doing (I've renamed node_temp to node just to help with formatting):

Starting state:                head ---> A -+-> B ---> null
                                            |
                               tail --------+

node = malloc(sizeof(*node));  node ---> C ----------> ?
 (allocate node C)             head ---> A -+-> B ---> null
                                            |
                               tail --------+

node->next = NULL;             node ---> C --------+
 (ignore payload cel/fah                           |
  for now since it's not       head ---> A -+-> B -+-> null
    relevant to the list                    |
               structure)      tail --------+

tail->next = node;             node ---------------+
 (first in else clause)                            |
                               head ---> A -+-> B -+-> C ---> null
                                            |
                               tail --------+

tail = node;                   node ---------------+
 (second in else clause)                           |
                               head ---> A ---> B -+-> C ---> null
                                                   |
                               tail ---------------+

然后最终 node 消失了，因为它是一个局部变量并且你有你的最终状态:

Then eventually node disappears since it's a local variable and you have your final state:

                               head ---> A ---> B -+-> C ---> NULL
                                                   |
                               tail ---------------+

在单向链表中维护 tail 指针的优点是避免在尝试向末尾添加项时必须遍历整个列表才能找到末尾.

The advantage of maintaining a tail pointer in a singly-linked list is to avoid having to step through the entire list to find the end when you're trying to add an item to the end.

遍历整个列表使得在末尾插入一个 O(n) 时间操作(花费的时间取决于列表中的项目数).tail 指针的使用使得 O(1) 时间操作(无论列表大小如何，时间都相同).

Traversing the entire list makes insertion at the end an O(n) time operation (time taken is dependent on the number of items in the list). The use of the tail pointer makes that an O(1) time operation (same amount of time irrespective of the list size).

顺便说一句，双向链表还有一个tail指针的额外用途——它提供了使用快速开始从列表末尾到开头的遍历的能力tail 和 prev 指针代替 head 和 next 指针.

As an aside, a doubly linked list has an extra use for a tail pointer - it gives the ability to quickly begin a traversal from the end of the list to the start, using tail and the prev pointers in lieu of head and the next pointers.

这篇关于链表添加到尾部，混乱的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！