问题描述
这是一个锻炼的的 CLRS 3 的：
10.2-3一个单向链表L的操作入队和出队还是应该采取O（1）时间。
这并不难实现使用一个单向链表队列。我的问题是关于时间复杂度。如何实现入队和DEQUEQUE称取O（1）？
It's not hard to implement a queue using a singly linked list. My problem is about the time complexity. How to implement ENQUEUE and DEQUEQUE that take O(1)?
我发现在谷歌是一样的东西用指针来跟踪头部和尾部。现在的问题变成了如何追踪头部和尾部使用O（1）时间单链表？恕我直言，这需要O（n）的跟踪尾巴。我对吗？
What I found on google is something like using pointers to track both head and tail. Now the problem becomes how to track head and tail on a singly linked list using O(1) time? IMHO it takes O(n) to track the tail. Am I right?
推荐答案
这将需要O（1）时间管理的头部和尾部指针。
It will take O(1) time to manage the head and tail pointers.
排队：
tail -> next = newNode;
newNode -> next = NULL;
tail = newNode;
出列：
output_node = head;
head = head -> next;
// do whatever with output_node;
注意：您还可以进行指针赋值之前执行边界检查和内存分配/解除分配
这篇关于如何实现一个单向链表队列中，使得其入队和DEQUEUE取O（1）？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！