Probabilidad

esListas enlazadas. Una lista enlazada es una estructura enlazada en la que cada objeto hace referencia al siguiente, creando una ordenación lineal de los objetos de la lista, además de ser un TDA que nos permite almacenar datos de una forma organizada, al igual que los vectores pero, a diferencia de estos, esta estructura es dinámica, ya que se puede expandir o contraer su tamaño. En las listasenlazadas existe un nodo especial: el primero. Normalmente diremos que nuestra lista es un puntero a ese primer nodo y llamaremos a ese nodo la cabeza de la lista. Eso es porque mediante ese único puntero podemos acceder a toda la lista. Cuando el puntero que usamos para acceder a la lista vale NULL, diremos que la lista está vacía. Los elementos de una lista suelen recibir el nombre de nodos dela lista. Cada nodo contienen el dato a almacenar y un enlace al siguiente elemento, por lo tanto en una lista enlazada cada nodo apunta a otro nodo, con excepción del ultimo nodo que no tiene sucesor y el valor del enlace es NULL. La Figura 1 muestra gráficamente estos conceptos.

Figura 1. Esquema de un nodo y una lista enlazada.

Operaciones Descripción Dato Representa el dato a almacenar.Puede ser de cualquier tipo; en este ejemplo se trata de una lista de enteros. Enlace Es un puntero al siguiente elemento de la lista; con este puntero enlazamos con el sucesor, de forma que podamos construir la lista.

Para que esta estructura sea un TDA lista enlazada, debe tener unos operadores asociados que permitan la manipulación de los datos que contiene. Los operadores básicos de unalista enlazada son:
•

• • • •

Insertar: inserta un nodo con dato x en la lista, pudiendo realizarse esta inserción al principio o final de la lista o bien en orden. Eliminar: elimina un nodo de la lista, puede ser según la posición o por el dato. Buscar: busca un elemento en la lista. Localizar: obtiene la posición del nodo en la lista. Vaciar: borra todos los elementos de la lista

Listasdoblemente enlazadas. El TDA lista doblemente enlazada, al igual que la lista enlazada, es un TDA dinámico lineal pero, a diferencia de este, cada nodo de la lista doblemente enlazada contiene dos punteros, de forma que uno apunta al siguiente nodo y el otro al predecesor. Esta característica, permite que se pueda recorrer la lista en ambos sentidos, cosa que no es posible en las listas simples.Figura 2. Esquema de un nodo y una lista doblemente enlazada.

Operación Dato siguiente anterior

Descripción Representa el dato a almacenar, que puede ser de cualquier tipo. En este ejemplo se trataría de una lista de enteros. Se trata de un puntero al siguiente elemento de la lista. Con este puntero se enlaza con el sucesor, de forma que podamos construir la lista. Es un puntero al elementoanterior de la lista. Este puntero enlaza con el elemento predecesor de la lista y permite recorrerla en sentido inverso.

Sobre este TDA se definen los mismos operadores básicos que en las listas simples.

Pilas La pila es una estructura de datos donde las inserciones y recuperaciones/borrados de datos se hacen en uno de los finales, que es conocido como el top de la pila. Como el últimoelemento insertado es el primero en recuperarse/borrarse, los desarrolladores se refieren a estas pilas como pilas LIFO (last-in, first-out). Los datos se insertan (push) dentro y se recuperan-borran(pop) de la parte superior de la pila. La siguiente figura ilustra una pila con tres String cada uno insertado en la parte superior de la pila:

Como muestra la figura anterior, las pilas se construyenen memoria. Por cada dato insertado, el ítem superior anterior y todos los datos inferiores se mueven hacia abajo. Cuando llega el momento de sacar un ítem de la pila, se recupera y se borra de la pila el ítem superior (que en la figura anterior se revela como "third"). Las operaciones para un TDA de tipo pila se indican en la tabla siguiente. En la terminología de las pilas, insertamos (push)...