Questions: List Abstract Data Type: Interface and Semantics

Question 1

You're building a text editor that inserts characters at the cursor position frequently (near the beginning of large documents) and rarely reads by index. Which List ADT implementation should you choose?

• A. Array-backed list, because O(1) random access makes cursor positioning fast
• B. Linked-list-backed list, because front insertions are O(1) rather than O(n)
• C. Either implementation — they both support insert(), so performance is identical
• D. Array-backed list, because contiguous memory is always faster

Answer: (B)

The key insight of the List ADT is that the same interface hides very different performance characteristics. Array-backed lists require O(n) shifting for every front insertion — a serious cost for frequent edits to large documents. A linked-list-backed list makes front insertions O(1) by redirecting a pointer. Option C is the classic misconception: supporting the same interface does not mean equal performance. Option D is wrong because 'always faster' is never true for data structures — it depends entirely on the operation mix.

Question 2

A software library exports a List interface with get(), insert(), remove(), and size(). What does the ADT guarantee to code that uses it?

• A. The implementation uses an array internally for maximum performance
• B. All operations run in O(1) time
• C. The operations behave as specified regardless of the internal implementation
• D. The implementation can be swapped without recompiling client code

Answer: (C)

An ADT guarantees behavioral contracts — what operations do — not how they are implemented or how fast they run. Option A is wrong because the ADT is explicitly implementation-agnostic. Option B is wrong because different implementations have different complexities; no List ADT guarantees O(1) for all operations. Option D describes a language-level detail, not what an ADT guarantees conceptually. The core promise is semantic: operations fulfill their behavioral contracts.

Question 3

Two classes both implement a List ADT. Since they support the same operations, a program using either one will behave identically regardless of which is chosen.

• T. True
• F. False

Answer: False

This is the central misconception the ADT abstraction can create. Two implementations satisfy the same interface — operations exist and have the same semantics — but their time and space complexity can differ dramatically. insert(0, x) is O(1) in a linked-list implementation and O(n) in an array implementation. A program on a small list may behave equivalently; the same program on a million-element list may be thousands of times slower with one implementation. Correct behavior and good performance are different guarantees.

Question 4

The power of the ADT abstraction is that it lets you switch implementations without changing the code that uses the data structure.

• T. True
• F. False

Answer: True

This is the primary practical benefit of the ADT pattern. Code that depends only on the interface — calling get(), insert(), size() without knowledge of internals — can be handed an array-backed or linked-list-backed list interchangeably. Correctness is preserved because the interface contract is fulfilled either way. Important caveat: performance may change significantly. The ADT enables substitutability for correctness; performance analysis still requires knowing which implementation is used.

Question 5

Why is it useful to think in terms of ADTs even when you already know which implementation you'll use?

Model answer: Thinking in ADTs forces you to separate 'what operations does this structure need to support?' from 'how should it do it?' — preventing premature optimization, clarifying requirements, and making it easier to compare or swap implementations later. It also reveals which operations your code actually depends on, keeping the coupling to implementation details explicit and narrow.

The ADT mindset is a design discipline, not just a code-organization technique. By specifying the interface first, you identify what operations are truly needed and avoid building unused complexity. Even if you use an array from day one, framing it as 'a List that supports these operations' keeps your thinking portable and your code loosely coupled to the implementation — which matters when profiling reveals you need to switch.