Yue Wang Yue Wang - 2 months ago 29
C Question

How to implement a queue with a singly linked list, such that its ENQUEUE and DEQUEUE take O(1)?

It's an exercise from CLRS 3rd:


10.2-3 Implement a queue by a singly linked list L. The operations ENQUEUE and DEQUEUE should still take O(1) time.


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)?

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?

Answer

It will take O(1) time to manage the head and tail pointers.

Enqueue:

tail -> next = newNode;
newNode -> next = NULL;
tail = newNode;

Dequeue:

output_node = head;
head = head -> next;
// do whatever with output_node;

Note: You will also have to perform bounds checking and memory allocation / de-allocation before carrying out pointer assignments