Data-structure interfaces and operation costs
An interface defines operations; an implementation determines costs.
Key knowledge
A stack removes the most recently added item; a queue removes the earliest. A dictionary supports key lookup, insertion and deletion. Arrays offer constant-time indexed access in a word-RAM model, while linked-list traversal to an arbitrary index takes linear time.
Conditions and scope
- Specify representation, input size and machine-cost assumptions.
- Worst-case, expected and amortized operation bounds are distinct.
Sources · 1
References
Sources retain their recorded scope. A source link alone does not establish verification of every statement.
Evidence and review
Interface/implementation distinction, sequence/set operations, stack/queue and array/linked-list operation costs.
2026-10-10 · Basic abstract operations and two representation cost examples.
Entry details
Permanent link to this entry ↗- Record identity
- info-data-structures
- Revision
- university-reference.1
- Structured reference record
- University reference