Consider an implementation of unsorted single linked list. Suppose it has its…

Selected operation: Deletion of the last node of the linked list.

Reasoning summary: In a singly linked list that stores head and tail pointers, most operations that update only one end can be done in constant time by updating a few pointers. Removing the last node is the exception because there is no direct pointer to the node before the tail, so finding that predecessor requires traversal from the head.

• Insertion at the front of the linked list. Implementation: allocate new node, set new->next = head, head = new; if the list was empty, set tail = new. Time: O(1).

• Insertion at the end of the linked list. Implementation: allocate new node with next = null; if the list is empty set head = tail = new, else set tail->next = new and tail = new. Time: O(1) because the tail pointer gives direct access to the last node.

• Deletion of the front node of the linked list. Implementation: if list non-empty, set temp = head, head = head->next, free temp; if head becomes null set tail = null. Time: O(1).

• Deletion of the last node of the linked list. Explanation: to remove the last node you must update the previous node so its next becomes null and set tail to that previous node. Because the list is singly linked, you do not have a direct pointer to the previous node, so you must traverse from head to find it. This traversal takes O(n) in the worst case, so deletion of the last node is not O(1) in the general case. Special case: if the list contains exactly one node, deletion is O(1) because head == tail; to make deletion of the last node always O(1) you need a doubly linked list or additional backward pointers.