# Abstract Data Types and Interfaces

Computer Science I · Data Structures · https://tryals.app/learn/computer-science-i/abstract-data-types-and-interfaces

## ADTs vs Data Structures

A **data structure** is a concrete way of organizing data in memory, while an **abstract data type (ADT)** is the **behavior** that organization provides, described independently of how it is built.

The ADT acts as the **interface**—a set of operations and promised behavior. The data structure is one **implementation** of that interface. For example, a **List** ADT promises operations like **get(i)**, **add(x)**, **remove(i)**, and **size()**.

A List can be implemented by a contiguous array or a chain of linked nodes. Both honor the exact same List interface while offering very different internal performance characteristics.

## Choosing the Right Fit

Because callers depend on the **interface**, not the implementation, you can swap one data structure for another to change performance without rewriting client code.

| Concept | Definition | Role |
| --- | --- | --- |
| **ADT** | Abstract behavior | The **interface** |
| **Structure** | Memory organization | The **implementation** |

> **Common pitfall:** Conflating the ADT with a particular implementation, thinking a list **is** an array. Keeping interface and implementation separate lets you reason about behavior first and performance second.

## Practice questions

5 of this lesson's 11 practice questions, with answers. The full set is in the app.

### 1. A List ADT is being documented. Sort each statement by whether it belongs to the interface or describes one implementation.

**Answer:**

- Part of the List interface: get(i) returns the element currently at position i, size() returns how many elements the list holds
- Part of one implementation: The elements are held in one contiguous block of memory, Each element is a node carrying a pointer to the next node

**Why:** get, size and remove describe behaviour that both an array-backed and a node-backed list must honour, so they are the interface. Contiguity, pointers and reallocation are the machinery of one choice or the other. Because callers depend only on the first group, the second can be swapped out to change performance without touching a single caller.

Page: https://tryals.app/practice/computer-science-i/abstract-data-types-and-interfaces/a-list-adt-is-being-documented-sort-each-statement-by-whether-it

### 2. A program uses a List ADT backed by an array. The implementation is swapped for a linked one and not a single line of calling code changes - yet the program becomes noticeably slower. How can both facts be true at once?

A. Because the swap must have been done incorrectly.
B. Because linked lists are slower for every operation.
C. Because the calling code needs recompiling to regain speed.
D. Because the interface guarantees operations, not costs.

**Answer:** D. Because the interface guarantees operations, not costs.

**Why:** An ADT is a contract about behaviour, what operations exist and what they return, and cost is not in it, which is exactly why the swap compiles and why it can wreck performance. Indexing is the clearest case: `list[500]` is one multiplication and a read in an array, and five hundred pointer follows in a linked list. Neither structure dominates, which is why the choice is a design decision.

Page: https://tryals.app/practice/computer-science-i/abstract-data-types-and-interfaces/a-program-uses-a-list-adt-backed-by-an-array-the-implementation-is

### 3. A program uses a List ADT. Its array implementation is replaced by a linked one, and every published operation still behaves as documented. Select every statement that remains true afterwards.

A. get, add, remove and size behave as before
B. get(i) may take substantially longer
C. Code assuming contiguous storage may break
D. The published operations mean something new
E. The memory layout of the elements has changed

**Answer:** A. get, add, remove and size behave as before; B. get(i) may take substantially longer; C. Code assuming contiguous storage may break; E. The memory layout of the elements has changed

**Why:** Behaviour is preserved but performance and layout are not, that is the entire trade being made. The one false statement is that the operations mean something different: if they did, the swap would not be legal. Code that reached past the interface to assume contiguity was never protected, and it is exactly such code that breaks.

Page: https://tryals.app/practice/computer-science-i/abstract-data-types-and-interfaces/a-program-uses-a-list-adt-its-array-implementation-is-replaced-by-a

### 4. A team swaps a `List` implementation from array-backed to linked, changes no calling code, and the nightly batch job takes six hours instead of twenty minutes. Every test passes. What did the interface fail to promise?

A. Correctness, since the linked implementation must contain a bug
B. Cost, which the ADT's contract never mentioned
C. Nothing, the slowdown must come from elsewhere in the system
D. Thread safety, which the array version happened to provide

**Answer:** B. Cost, which the ADT's contract never mentioned

**Why:** The contract covered behaviour and said nothing about cost, so indexing went from one address computation to walking five hundred pointers, correct every time, and catastrophically slower. It is why real libraries publish complexity as part of the interface, accepting the constraint that creates.

Page: https://tryals.app/practice/computer-science-i/abstract-data-types-and-interfaces/a-team-swaps-a-list-implementation-from-array-backed-to-linked

### 5. Documenting a List ADT by writing down the array implementation's exact timings makes the documentation more useful, because callers know what to expect.

**Answer:** False

**Why:** False. It converts an implementation detail into a promise. Callers write code that relies on O(1) indexing, and swapping in a linked list, still a correct List, silently makes them quadratic. Document the *contract* (asymptotic bounds the ADT guarantees), not the timings one implementation happens to have.

Page: https://tryals.app/practice/computer-science-i/abstract-data-types-and-interfaces/documenting-a-list-adt-by-writing-down-the-array-implementations