c - 在循环链表的开头插入

Question

我最近一直在研究循环链表，大多数人编写代码的方式如下:

#include<stdio.h>
#include<stdlib.h>

/* structure for a node */
struct Node
{
    int data;
    struct Node *next;
};

/* Function to insert a node at the begining of a Circular
   linked list */
void push(struct Node **head_ref, int data)
{
    struct Node *ptr1 = (struct Node *)malloc(sizeof(struct Node));
    struct Node *temp = *head_ref;
    ptr1->data = data;
    ptr1->next = *head_ref;

    /* If linked list is not NULL then set the next of last node */
    if (*head_ref != NULL)
    {
        while (temp->next != *head_ref)
            temp = temp->next;
        temp->next = ptr1;
    }
    else
        ptr1->next = ptr1; /*For the first node */

    *head_ref = ptr1;
}

/* Function to print nodes in a given Circular linked list */
void printList(struct Node *head)
{
    struct Node *temp = head;
    if (head != NULL)
    {
        do
        {
            printf("%d ", temp->data);
            temp = temp->next;
        }
        while (temp != head);
    }
}

/* Driver program to test above functions */
int main()
{
    /* Initialize lists as empty */
    struct Node *head = NULL;

    /* Created linked list will be 11->2->56->12 */
    push(&head, 12);
    push(&head, 56);
    push(&head, 2);
    push(&head, 11);

    printf("Contents of Circular Linked List\n ");
    printList(head);

    return 0;
}

但是，在循环链表的开头插入时，有一点永远无法理解。如果我们的最后一个节点总是指向第一个节点，这也意味着最后一个节点 *next 指针与 *first 指针具有相同的地址，那么为什么要在第一个节点之后插入项目，我们必须遍历整个列表并更新最后一个节点的 *next 指针以指向新添加的节点的开头。为什么我们不能简单地这样做而不是 while 循环:

节点*新增 新添加->下一个=第一个->下一个 首先=新增

因为 *first 指针具有第一个节点的地址，所以如果我们更新 *first 指针，那么已经指向第一个指针的最后一个指针也应该更新自身。 为什么要遍历整个列表？

Answer 1

由于列表是循环的，因此列表的最后一个元素需要指向列表的第一个元素。当将新元素插入列表的开头时，列表的第一个元素已更改为不同的元素。为了保持循环性，您必须找到最后一个元素并使其指向新的第一个元素。

使操作更高效的一种方法是维护循环链表的尾部，而不是头部。然后插入到尾部和头部都可以在恒定时间内完成。

Demo