Kdtyjb

I’m trying to understand the time complexity of a queue implemented with a linked list data structure. My book says that we can the implement a queue in O(1) time by:

• enqueueing at the back


• dequeueing at the head

and it also says

Note that although adding an element to the tail is constant time,
removing an element from the tail is O(n) as we have to find the new
tail

I know that adding a new node to my queue at the head (enqueue) takes O(1) since I have the head pointer. Similarly, removing a node at the head (dequeue) will take O(1) as well. But I don’t understand why adding an element at the back (enqueue) takes O(1), while removing it (dequeue) takes O(n). It would make more sense to me if enqueueing at the back took O(n) rather than O(1), since in both cases (adding/removing at the back) would need to find the tail pointer and therefore it would need to traverse the entire list.

Enqueueing

You don't need to traverse the entire list to find the new tail, you just need to add a new node where the current tail points to and set that node as the new tail.

Pseudocode (assuming that head != null and tail != null):

function enqueue(value) {

    node = new Node(value)     // O(1)

    tail.next = node           // O(1)

    tail = node                // O(1)

    size++                     // O(1)

}

From which we can conclude that the time complexity is $O(1)$.

Dequeueing

For dequeueing, we only need to set the next node of the current head as the new head and return the value of the old head.

Note: Don't forget that if the new head is set to null, the tail should be set to null as well:

Pseudocode (assuming that head != null and tail != null):

function dequeue() {

    value = head.value         // O(1)

    head = head.next           // O(1)

    size--                     // O(1)



    if (head == null) {        // O(1)

        tail = null            // O(1)

    }



    return value               // O(1)

}

All these operations have $O(1)$ time complexity, which makes the time complexity of the dequeue function $O(1)$ as well.

Searching

Searching for a value is done by traversing through all the items, starting from the head. In the worst case scenario, you would need to traverse the entire queue, which makes the worst-case time complexity $O(n)$.

For example, if you want to remove the tail, the time complexity would be $O(n)$. This is because you would need to find the new tail for the queue and since the tail does not have access to the previous element in a singly linked list, you would need to search the entire queue for the new tail.

Pseudocode (assuming that head != null and tail != null):

function removeLast() {



    // Edge case when there is only 1 element in the queue.

    if (head == tail) {                   // O(1)

        value = head.value                // O(1)

        head = null                       // O(1)

        tail = null                       // O(1)



        return value                      // O(1)

    }



    // Searching for the new tail.

    newTail = head                        // O(1)

    while (newTail.next != tail) {        // O(n)

        newTail = newTail.next            // O(1)

    }



    value = tail.value                    // O(1)

    newTail.next = null                   // O(1)

    tail = newTail                        // O(1)



    return tail                           // O(1)    

}

From which can be seen that the time complexity is indeed $O(n)$.

The comment in the book apparently assumes that your linked list implementation maintains two pointers, head that points to the first node in the list, and last that points to the last node.

With this design, appending to the list is simply:

list.last.next = newNode;

list.last = newNode;

But removing the last node requires finding the 2nd to last node, so you can clear its next link, and change the last pointer to point to it. This requires scanning the list to find the node where node.next == list.last.

You could conceivably also have a list.secondToLast pointer, but that doesn't solve the problem, because when you remove the last node you need to change this to point to the previous third to last node, and this problem recurses to the entire list.