In an implementation of a stack based on a singly-linked list,it is most efficient to add a new item so that
A) the new item has the highest index of all items in the list
B) the new item has the lowest index of all items in the list
C) the new item is not duplicated by any other item already in the stack
D) the items in the stack stay sorted in ascending order

Question

Quizplus · Accepted Answer

In a stack, we always add the new element at the top, which is the head of the linked list. Therefore, it is most efficient to add a new item with the lowest index of all items in the list, so that we can insert the new item at the head of the list in constant time. Adding an item to the end of the list (i.e., with the highest index) would require iterating over the entire list to find the last item, which would take O(n) time. The fact that the new item is not duplicated or sorted is irrelevant to the efficiency of adding it to the stack.

In an Implementation of a Stack Based on a Singly-Linked