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

Question

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?

Solution 1

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

Solution 2

it is easy, simply enque at the end and deque at the front, and setup 2 pointer(or unique_ptrs) pointing to end and front, that will do. like this:

struct queue{
    Node *head;
    Node *tail;
    int node_cnt; // well, you can put this in if you like
};

Node *enque(Node *head, int data)
{
    Node *p = new Node(Node data);
    if (head)
    {
        head->next = p;
        head = p;
    }
    else
        head = p;
    ++ q.node_cnt;
    return head;
}

int deque(Node *tail)
{
    Node *p = tail;
    int x = tail->data;
    tail = tail.next();
    delete p;
    -- q.node_cnt;
    return x;
}

Above is only a demonstration code, yet you can see that you don't need to iterate through the entire list to enque or deque.

Solution 3

std::list is what you're looking for if you're allowed to use std containers.

If not (I assume that's the case), try answering the question: why do you need to perform n operations? Can you just store the pointer to the end?

Say, you have a signly linked list and a pointers head and tail A list item has next pointer.

• If you enqueue a new item, you just add a new item, amend the former "first" item's next pointer and repoint the head pointer to the new item. That's 3 operations = O(1)
• If you dequeue an item, you move the last pointer to the one pointed on by the last item's next pointer` and delete the item - 2 operations = O(1)

Comments

[Yue Wang]

Looks good! Just wondering, what is the x in the statement head = x;? Is it p?

[dguan]

Thanks for pointing out, I just wrote the code by hand, and did not do any checking, sorry about that. I am assuming Node is a structure with this signature: struct Node { int data; Node *next; Node(int a):data(a){} }; so, it should be x = p->data; something like that.