In the Deque implementation using singly linked list, what would be the time…

In a Deque built on a plain singly linked list, every node stores only a forward (next) pointer — there is no pointer back to a node's predecessor. Any operation that needs the node just before a given node must therefore start scanning from the head, because there is no way to jump backward from the end.

1. To delete the rear element, the node that becomes the new tail — the second-to-last node — must have its next pointer set to null.

2. Since the list only links forward, the only way to find that second-to-last node is to start at the head and walk forward, checking at each step whether the next node is the last one.

3. For example, consider the list head → A → B → C → D, where D is the current tail. Starting at the head, the traversal moves A → B → C, stopping at C because C's next pointer points to D, the current tail. C's next pointer is then set to null and C becomes the new tail.

4. In the worst case (an n-node list) this walk visits n-1 nodes before reaching the one just before the tail — one full pass over the list.

5. This single linear pass gives the operation O(n) time complexity.

• Deleting from the FRONT needs no traversal — the head pointer is already known, so that operation is O(1).

• In a doubly linked list Deque, each node also keeps a previous pointer, so the tail's predecessor is reached directly and rear-deletion is O(1) there.

• The singly linked list's lack of a backward link is exactly what forces the O(n) cost for this specific operation.