Arrays y Listas Enlazadas

Los arrays y las listas enlazadas son las dos formas básicas de almacenar una secuencia ordenada de elementos: los arrays los colocan en memoria contigua para un acceso indexado en tiempo constante, mientras que las listas enlazadas los encadenan mediante punteros para una inserción y eliminación de bajo costo.

Definition

Un array almacena elementos en ubicaciones de memoria contiguas indexadas por posición, lo que permite un acceso aleatorio en tiempo constante; una lista enlazada almacena elementos en nodos separados, cada uno de los cuales contiene una referencia al nodo siguiente (y posiblemente al anterior), lo que permite una inserción o eliminación en tiempo constante dada una referencia de nodo.

Scope

Este tema abarca las estructuras lineales basadas en secuencias y los tipos de datos abstractos construidos sobre ellas —arrays estáticos y dinámicos, listas enlazadas simples y dobles, y los ADT de pila y cola. Contrasta sus costos de acceso, inserción y eliminación, cubre el redimensionamiento de arrays dinámicos y su análisis amortizado, y explica las consecuencias del diseño de la memoria, como la localidad de caché. Excluye las estructuras asociativas y jerárquicas cubiertas en las tablas hash y los árboles de búsqueda.

Core questions

• ¿Cuándo el almacenamiento contiguo (array) supera al almacenamiento enlazado por punteros (lista)?
• ¿Cómo logra un array dinámico un tiempo de adición amortizado constante a pesar del redimensionamiento ocasional?
• ¿Cuáles son las compensaciones de costos de los arrays frente a las listas enlazadas para la inserción, eliminación y acceso?
• ¿Cómo se implementan las pilas y las colas sobre estas estructuras?
• ¿Cómo afecta el diseño de la memoria al rendimiento en el mundo real a través del comportamiento de la caché?

Key concepts

• memoria contigua
• acceso indexado
• redimensionamiento de array dinámico
• listas enlazadas simples y dobles
• pilas (LIFO)
• colas (FIFO)
• costo amortizado
• localidad de caché

Key theories

Acceso aleatorio versus enlace secuencial

Los arrays soportan acceso indexado O(1) pero inserción o eliminación O(n) en el medio, mientras que las listas enlazadas soportan empalme O(1) dado un nodo pero acceso O(n) por posición; la elección correcta depende de la combinación de operaciones.

Crecimiento amortizado de arrays dinámicos

Un array dinámico que duplica su capacidad cuando está lleno realiza copias O(n) ocasionales, pero se amortiza a O(1) por adición sobre cualquier secuencia de operaciones, mediante el método agregado o potencial.

Clinical relevance

Los arrays y las listas son el sustrato de casi todos los programas: los arrays dinámicos implementan los tipos de lista/vector predeterminados en la mayoría de los lenguajes, las colas sustentan la programación y la búsqueda en amplitud, las pilas sustentan la gestión de llamadas a funciones y la evaluación de expresiones, y la compensación entre array y lista es una decisión de diseño práctica rutinaria que afecta el rendimiento.

History

Los arrays se encuentran entre las estructuras de datos más antiguas, presentes en los primeros lenguajes de programación, y las listas enlazadas se introdujeron para el procesamiento simbólico y de listas (notablemente en IPL de Newell, Shaw y Simon y posteriormente en Lisp) a finales de la década de 1950. El tratamiento sistemático de Knuth en The Art of Computer Programming estableció su análisis canónico.

Key figures

• Donald Knuth
• Robert Sedgewick

Seminal works

• knuth1997vol1
• cormen2009

Frequently asked questions

¿Por qué usar una lista enlazada si los arrays permiten un acceso aleatorio rápido?

Las listas enlazadas permiten la inserción o eliminación en tiempo constante dada una referencia a un nodo, sin desplazar otros elementos, lo que los arrays no pueden hacer en el medio. Son útiles cuando la secuencia cambia con frecuencia y no se necesita un acceso aleatorio posicional.

¿Por qué las adiciones a arrays se consideran de tiempo constante si el redimensionamiento copia todo?

El redimensionamiento ocurre raramente porque la capacidad generalmente se duplica, por lo que el trabajo total de copia en n adiciones es proporcional a n. Distribuido entre todas las adiciones, esto da un costo constante amortizado por adición, aunque los redimensionamientos individuales sean O(n).