在线性时间内创建队列链表

Question

我想出了这种在 C: 中创建链表的方法:

void queue(Node ** head, Node * object)
{
    Node * tmp = (Node *)malloc(sizeof(Node));
    *tmp = *object;
    Node *last = get_Last((*head));
    if (last) {
        last->next = tmp;
        tmp->next = NULL;
    }
    else {
        (*head) = tmp;
        tmp->next = NULL;
    }
}

这个想法相当简单，将一个指向对象的指针传递给queue(...)，然后遍历列表以找到最后一个节点，然后编辑一些指针。然而我不太喜欢的是 get_Last(...) 函数:

Node * get_Last(Node * head)
{

    if (!head) {
        return NULL;
    }
    while (head->next) {
        head = head->next;
    }
    return head;
}

这个函数意味着如果 queue(...) 发现自己处于循环中，那么我想出的算法具有 O(n²) 时间复杂度，这对于简单的事情来说太多了就像创建一个链接列表一样。可以采取什么措施将复杂性降低到 O(n)？我猜 queue(...) 仍然需要最后一个节点的地址，但是如何在不循环的情况下获取它？

Answer 1

您确定需要在列表末尾插入项目吗？在链表的前面插入/删除是免费的O(1)。

如果您确实想要一个高效的 FIFO 列表，到目前为止最好的方法是保留尾部元素的地址。它只需要常量内存，并允许 O(1) 插入到尾部。

实现此目的的最清晰方法可能是创建一个 Queue 结构体，该结构体保留指向头部和尾部的指针，并使用实用函数接受指向 Queue 的指针以进行入队和出队操作。