What is the time complexity of enqueue and dequeue of a queue implemented with a singly linked 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)$.