Una estructura de datos es una forma de organizar y almacenar datos en memoria para que puedan ser accedidos y modificados eficientemente. Un tipo de datos abstracto (ADT) es el modelo lógico — las operaciones y su comportamiento — independientemente de cómo se implemente.
El ADT describe operaciones existen; la estructura de datos decide se almacenan y qué tan rápido se ejecutan.
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)
| Aspecto | Pregunta a hacer |
|---|---|
| Patrón de acceso | ¿Acceso aleatorio o secuencial? |
| Mutaciones | ¿Inserciones/eliminaciones frecuentes en el medio? |
| Ordenamiento | ¿Ordenado, FIFO, LIFO, o ninguno? |
| Búsquedas | ¿Por índice o por clave? |
La opción correcta es aquella cuyas operaciones comunes sean económicas para tu carga de trabajo.
Elegir la estructura equivocada convierte una operación O(1) en O(n), lo que puede hacer que el código sea miles de veces más lento a escala.
Pensar en términos de ADT's te permite razonar sobre el comportamiento primero, y luego intercambiar implementaciones después sin reescribir los llamadores.