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)$.