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

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

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

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

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

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

Create a queue linked list in linear time

c

time-complexity

singly-linked-list