LISTAS

LISTAS

Es una colección de elementos llamados Generalmente nodos. Él orden entre los nodos se establece por medio de punteros, es decir, direcciones o referencias a otros nodos.

En general un nodo consta de 2 partes:

• Información que será de tipo de datos que se quiera almacenar en la lista.

• Liga, de tipo puntero, que se utiliza para establecer la liga o el enlace con otro nodo de la lista. Si este nodo fuera el último de la lista, este campo tendrá como valor: NIL(vacío)

OPERACIONES CON LISTAS

• Recorrido de la lista

• Inserción de un elemento

• Borrado de un elemento

RECORRIDO DE LA LISTA

Consiste en visitar cada uno de los nodos que forman parte de la lista. La visita de un nodo puede definirse por medio de una operación muy simple (la impresión de la información del mismo), o por medio de operaciones muy complejas.

Para recorrer los nodos se comienza con el primero. Tomando el valor del campo LIGA de este avanza al segundo y así sucesivamente. La dirección de un nodo, excepto el primero, esta dada por el campo LIGA de su predecesor.

Inserción de un elemento

Consiste en agregar un nuevo nodo a la lista. Considerará el caso de lista vacía, la lista en la cual se va a insertar el nuevo nodo ya existe. Se pueden presentar tres casos en la operación de inserción

• Insertar un nodo al inicio de la lista

• Insertar un nodo al final de la lista

• Insertar un nodo antes/después que otro

BORRADO DE UN ELEMENTO

Quitar un nodo de la lista, redefiniendo las ligas que correspondan. Se pueden presentar cuatro cosas en esta operación.

• Eliminar el primer nodo

• Eliminar el ultimo nodo

• Eliminar in nodo con información X.

• Eliminar el nodo anterior/posterior al nodo con información X.

LISTAS CIRCULARES

Las listas circulares tienen la característica de que el último elemento de la misma apunta al primero. Las listas circulares son similares a las operaciones en listas lineales.

Los recorridos de las listas circulares es necesario aclarar que se debe considerar algún criterio para detectar cuándo se han visitado todos los nodos para evitar caer en ciclos infinitos. La solución es usar un nodo extra, llamado nodo de cabecera, para indicar el inicio de la lista. Contendrá información especial, así podrá hacer referencia al principio de la lista.

LISTAS DOBLEMENTE LIGADAS CIRCULARES

El campo liga izquierda del primer nodo de la lista apunta al último y el campo liga derecha de este apunta al primero. Lo mismo que en el caso de listas lineales suelen usarse un nodo de cabecera. Este nodo tendrá las características descritas anteriormente y servirá como referencia para detectar cuando se ha recorrido totalmente la lista.

...