Choosing data structures from operation costs

≈ 45 min

Choosing data structures from operation costs

Data structures are trade-offs. An array gives direct indexed access, while inserting near the front may require shifting later values. A linked structure can insert a known node cheaply, while indexed access requires following links. A stack and queue deliberately limit operations to support particular orders. The right choice begins with the operations the program performs most often.

Complexity statements need assumptions. Adding to the end of a dynamic array is often amortised constant time, but resizing can occasionally copy many items. Removing from the front of a simple array list can be linear because elements shift. A queue implemented with a deque avoids repeated front shifting. These distinctions matter when inputs become large.

Worked reasoning. A print service receives jobs and repeatedly serves the oldest pending job. It does not need random access by position. A queue gives the required first-in, first-out contract and can perform each enqueue/dequeue efficiently. An ArrayList used as a front-removing queue may work for ten jobs but shift many items for thousands.

Exam lens. Name the dominant operation, its required order and the likely cost. Do not choose a structure only because it was used in a previous question.

Which statement is the most defensible principle for Choosing data structures from operation costs?

Choose a data structure by the operations the problem needs, their order and their cost.

Treat an implementation detail as more important than the stated rule.

Assume one successful run proves the system is correct in every case.

Avoid recording assumptions, limits or failure conditions.

Enter the key term for Choosing data structures from operation costs. What term describes how an operation’s cost grows as the amount of data grows?

A program repeatedly removes the oldest item and adds new items at the end. Which structure avoids front-shifting work?

A queue or deque matches the first-in, first-out workload and avoids using a simple array list as a front-removing queue.

Use a larger class or broader permission without stating a rule.

Trust the first output and skip a boundary or failure check.

Hide the decision so affected people cannot inspect it.

Name the concise safeguard or principle that completes this lesson’s scenario: A program repeatedly removes the oldest item and adds new items at the end. Which structure avoids front-shifting work?