Las Listas

LISTAS

Las listas no son arreglos (arrays), aunque ambos representan secuencias de elementos de un tipo, los arreglos tienen longitud fija; las listas, no; es decir, las listas son flexibles y permiten cambio de implementación.

Operaciones básicas sobre listas

- Inserción al comienzo de una lista:

Es necesario utilizar una variable auxiliar, que se utiliza para crear el nuevo nodo mediante la reserva de memoria y asignación de la clave. Posteriormente es necesario reorganizar los enlaces, es decir, el nuevo nodo debe apuntar al que era el primer elemento de la lista y a su vez debe pasar a ser el primer elemento.

- Recorrido de una lista.

La idea es ir avanzando desde el primer elemento hasta encontrar la lista vacía. Antes de acceder a la estructura lista es fundamental saber si esa estructura existe, es decir, que no está vacía. En el caso de estarlo o de no estar inicializada es posible que el programa falle y sea difícil detectar donde, y en algunos casos puede abortarse inmediatamente la ejecución del programa, lo cual suele ser de gran ayuda para la depuración. Como se ha dicho antes, la lista enlazada es una estructura recursiva, y una posibilidad para su recorrido es hacerlo de forma recursiva.

Usos de las listas

Las listas son más apropiadas cuando se trabaja con datos dinámicos. En otras palabras, inserciones y borrados con frecuencia. Por el contrario, los arrays son más apropiados cuando los datos son estáticos (las inserciones y borrados son raras). De todas formas, no olvide que si se queda sin espacio cuando añade ítems a un array, debe crear un array más grande, copiar los datos del array original el nuevo array mayor y eliminar el original. Esto cuesta tiempo, lo que afecta especialmente al rendimiento si se hace repetidamente.

Mezclando una lista de enlace simple con un array uni-dimensional para acceder a los nodos mediante los índices del array no se consigue nada. Gastará más memoria, porque necesitará los elementos del array más los nodos, y tiempo, porque necesitará mover los ítems del array siempre que inserte o borre un nodo.

Tipos de listas

Listas simples

Se definen como un conjunto de nodos uno detrás de otro, del cual siempre se puede conocer al nodo inicial y al final, de cada nodo de la lista, se conoce un contenido, que es la información que almacena dentro puede ser de cualquier tipo de dato un sucesor único excepto el ultimo nodo de la lista.

Operaciones de las listas simples

• Creación de una lista

crearLista (nombreLista)

• Comprobación del estado

listaVacia(nombreLista) → Booleano

listaVacia(referenciaNodo) → Booleano

listaLlena(nombreLista) → Booleano

• Inserción de nodos

insertar(nombreLista, valorInfo, posición)

insertar(nombreLista, valorInfo)

• Borrado de nodos

borrar(nombreLista, valorInfo)

• Búsqueda de un nodo

buscar(nombreLista, dato)→información

buscar(nombreLista, dato)→referenciaNodo

pertenece(nombreLista,informacion) → Booleano

• Recorrido de la lista

recorrer(nombreLista)

• Acceso a los nodos

info(referenciaNodo) → Informacion

siguiente(referenciaNodo) → enlace

• Modificación de nodos

asignarInfo(referenciaNodo, valorInformacion)

asignarEnlace(referenciaNodo, valorEnlace)

• Acotación sobre las operaciones

ListaLlena sólo tiene sentido si lista es acotada.

Acceso y modificación serán métodos get y put.

Listas ordenadas

Son las que la posición de cada nodo viene determinada por el valor de uno o más campos obligatorios de información del nodo denominados clave No se permite tener dos nodos con la misma clave.

Operaciones de las listas ordenadas

• Creación de una lista

crearLista (nombreLista)

• Comprobación del estado

listaVacia(nombreLista) → Booleano

listaVacia(referenciaNodo) → Booleano

listaLlena(nombreLista) → Booleano

• Inserción de nodo

insertar(nombreLista, valorClave, valorInfo)

• Borrado de nodos

borrar(nombreLista, valorClave)

• Búsqueda de un nodo

buscar(nombreLista, valorClave) → Información

buscar(nombreLista, valorClave)→ReferenciaNodo

pertenece(nombreLista,valorClave) → Booleano

• Acceso a los nodos

clave(referenciaNodo) → Clave

info(referenciaNodo) → Información

siguiente(referenciaNodo) → enlace

• Modificación de los nodos

asignarClave(referenciaNodo, valorClave)

asignarInfo(referenciaNodo, valorInformacion)

asignarEnlace(referenciaNodo, valorEnlace

Listas enlazadas

Al contrario que las pilas y las colas las listas enlazadas pueden acceder a una zona de memoria de forma aleatoria, ya que cada trozo de información lleva un enlace al siguiente elemento de la cadena. Una lista enlazada requiere una estructura de datos compleja, al contrario que las colas o las pilas, que pueden operar con elementos simples o complejos, además una operación de recuperación en una lista enlazada no elimina ni destruye el elemento de la lista. Para poder eliminar un elemento de una lista es necesario utilizar una operación especifica de eliminación.

Las listas enlazadas se utilizan principalmente para dos propósitos, crear arrays de un tamaño desconocido en memoria, y los archivos de almacenamiento en disco para bases de datos, las listas enlazadas permiten insertar y eliminar nuevos elementos.

Las listas pueden ser simplemente enlazadas o doblemente enlazadas, las simplemente enlazadas contienen un enlace al elemento siguiente, las doblemente enlazadas tanto al siguiente elemento como al elemento anterior del la lista.

...