A data structure is a way of organizing and storing data in memory so it can be accessed and modified efficiently. An abstract data type (ADT) is the logical model — the operations and their behavior — independent of how it is implemented.
The ADT describes operations exist; the data structure decides they are stored and how fast they run.
ADT: Stack → push, pop, peek (LIFO behavior)
Implementations: → array-backed OR linked-list-backed
ADT: List → get(i), insert, remove
Implementations: → dynamic array OR linked list
# Both satisfy the "Stack" ADT, but have different cost profiles
stack = [] # list-backed stack
stack.append(10) # push -> amortized O(1)
top = stack[-1] # peek -> O(1)
stack.pop() # pop -> O(1)
| Concern | Question to ask |
|---|---|
| Access pattern | Random access or sequential? |
| Mutations | Frequent insert/delete in the middle? |
| Ordering | Sorted, FIFO, LIFO, or none? |
| Lookups | By index or by key? |
The right pick is the one whose common operations are cheap for your workload.
Picking the wrong structure turns an O(1) operation into O(n), which can make code thousands of times slower at scale.
Thinking in terms of ADTs lets you reason about behavior first, then swap implementations later without rewriting callers.