Abstract data types versus implementations

An abstract data type (ADT) is a promise about behavior. An implementation is the code that keeps the promise. Keeping the two apart is what lets you swap a structure later without rewriting the code that uses it.

A stack is an ADT: push, pop, peek, isEmpty, and a rule that the last thing in is the first thing out. Nothing in that description says how the items are stored.

// Two implementations, one contract.
class ArrayStack {
  #items = [];
  push(value) { this.#items.push(value); }
  pop() { return this.#items.pop(); }
  peek() { return this.#items.at(-1); }
  get size() { return this.#items.length; }
}

class LinkedStack {
  #head = null;
  #size = 0;
  push(value) { this.#head = { value, next: this.#head }; this.#size++; }
  pop() {
    if (!this.#head) return undefined;
    const { value, next } = this.#head;
    this.#head = next;
    this.#size--;
    return value;
  }
  peek() { return this.#head?.value; }
  get size() { return this.#size; }
}

Both are stacks. Code written against the contract does not care which one it receives.

Where they differ

The array version has better cache behaviour and occasionally pays to resize. The linked version never resizes but allocates a node per item and scatters them across memory. In practice the array version wins for most workloads — but that is an implementation argument, not a stack argument.

Why the distinction pays

• Testing. Test the contract once, then run those tests against every implementation.
• Substitution. Swap in a faster structure when profiling says so, with no caller changes.
• Interviews. "Which data structure?" usually means the ADT: a queue. "How would you implement it?" is the follow-up, and that is where arrays and linked lists come in.

The rest of this course names the ADT first and the implementation second, deliberately.