TAD y estructuras lineales

Un tipo abstracto de datos (TAD) es un modelo matemático: dice qué operaciones existen y qué efecto tienen, pero no dice cómo se consiguen. Una estructura de datos es la implementación concreta: la forma real en que los datos se colocan en memoria para que esas operaciones funcionen.

El ejemplo más claro es la pila. Como TAD, una pila es «algo donde el último que entra es el primero que sale», y con eso basta para programar contra ella. Como estructura, esa pila puede estar hecha con un array o con una lista enlazada, y el programa que la usa no tiene por qué enterarse.

El tipo abstracto responde al qué y el comportamiento; la estructura de datos responde al cómo. Un mismo TAD admite varias implementaciones, y cada una tiene costes distintos.

La pila es un almacén con una sola puerta. Todo entra y sale por el mismo extremo, llamado cima, de modo que el último elemento en entrar es el primero en salir. Esa regla se abrevia LIFO, de «last in, first out».

• push: apila un elemento sobre la cima.
• pop: saca el elemento de la cima y lo devuelve, con lo que la pila se queda con uno menos.
• peek o top: mira qué hay en la cima sin sacarlo. Es la diferencia que más se pregunta respecto a pop.
• isEmpty: dice si la pila está vacía, que es lo que hay que comprobar antes de hacer pop.

pila = [ ]

push(pila, "A")   ->  [A]
push(pila, "B")   ->  [A, B]
push(pila, "C")   ->  [A, B, C]

peek(pila)        ->  devuelve "C", la pila no cambia
pop(pila)         ->  devuelve "C"  ->  [A, B]
pop(pila)         ->  devuelve "B"  ->  [A]
isEmpty(pila)     ->  falso

Se usa siempre que haga falta deshacer en orden inverso: la pila de llamadas a funciones de cualquier programa, el botón de deshacer de un editor, el botón de atrás del navegador o la evaluación de expresiones con paréntesis.

La cola tiene dos puertas: se entra por una y se sale por la otra. El primero que llega es el primero en salir, regla que se abrevia FIFO, de «first in, first out». Es la cola del supermercado, y por eso es la estructura natural de las listas de espera: trabajos de impresión, peticiones a un servidor o mensajes pendientes de procesar.

• enqueue: mete un elemento por el final.
• dequeue: saca el elemento del principio y lo devuelve.
• peek o front: consulta el primero sin sacarlo.
• isEmpty: indica si la cola está vacía.

La bicola o cola doblemente terminada (deque) relaja la regla: permite insertar y extraer por los dos extremos. Con ella se pueden simular tanto una pila como una cola, y por eso su implementación típica es una lista doblemente enlazada, que llega a los dos extremos en tiempo constante.

La cola de prioridad se llama cola pero no es FIFO: no sale el que lleva más tiempo esperando, sino el de mayor prioridad. Su implementación habitual es el montículo, que se ve más adelante.

Pila LIFO, cola FIFO. La bicola trabaja por los dos extremos y la cola de prioridad rompe el orden de llegada.

La lista es una secuencia de elementos en la que cada uno ocupa una posición. Admite repetidos y, a diferencia del conjunto, el orden importa: la lista formada por 5, 2, 5 no es la misma que la formada por 2, 5, 5.

• insertarDelante e insertarDetrás: añaden un elemento por la cabeza o por la cola de la secuencia.
• head: devuelve el primer elemento de la lista.
• tail: devuelve la lista entera menos su primer elemento. Ojo, no devuelve el último elemento: devuelve el resto.
• isEmpty: indica si la lista está vacía.

Ese par head y tail es lo que explica el punto que más se pregunta: la lista es posicional pero no tiene una primitiva para saltar directamente al elemento número n. Para llegar al tercero hay que quitar dos veces la cabeza y quedarse con la del resto, es decir, encadenar tail sobre tail y aplicar head al final. Eso obliga a recorrer, y recorrer cuesta tiempo lineal.

En un array el elemento n se alcanza de un salto; en una lista enlazada hay que atravesar los n−1 anteriores. Esa es la diferencia práctica entre las dos implementaciones del mismo tipo abstracto.

El array reserva memoria contigua: los elementos están pegados unos a otros, así que la dirección de cualquiera se calcula con una multiplicación y una suma. Eso da acceso inmediato por índice, pero insertar en medio obliga a desplazar todo lo que viene detrás, y crecer obliga a pedir un bloque mayor y copiarlo entero.

La lista enlazada guarda cada elemento en un nodo suelto con un puntero al siguiente. Insertar o borrar es cambiar un par de punteros, pero no hay forma de calcular dónde está el elemento n: hay que recorrer desde el principio. Además cada nodo gasta memoria extra en sus punteros.

La búsqueda binaria no se puede aplicar a una lista enlazada aunque esté ordenada, porque necesita saltar al elemento central en tiempo constante y ahí no se puede.