Why can't a singly-linked list remove its last node in $O(1)$, even with a tail reference?

Removing the last node means the second-to-last node must become the new tail, and a singly-linked node has no reference back to its predecessor — you have to walk from the head to find it, which is $O(n)$.

tail points to the last node, but what removeLast has to change is the node before it: that node's next must become null, and tail must move to it. In a singly-linked list the only links point forwards, so there is no way to step back from tail. The only way to find the predecessor is to start at head and follow next until you reach the node whose next is tail, which takes $n-1$ steps.

This is the core weakness of singly-linked lists: you always start at the head and can only move in one direction. Two consequences follow:

• A singly-linked list with head and tail is fine for a stack (all work at the head) and a queue (add at the tail, remove at the head).
• It is not enough for a deque, which must also remove at the tail in $O(1)$. That needs a doubly-linked list.