Ing. Sistemas

Listas
Una lista es una secuencia de elementos del mismo tipo o clase almacenados en memoria.
Las listas son estructuras lineales, donde cada elemento de la lista, excepto el primero, tiene un único predecesor y cada elemento de la lista, excepto el último tiene un único sucesor.
El número de elementos de una lista se denomina: longitud.
En una lista es posible añadir nuevos elementos osuprimirlos en cualquier posición.
Existen dos tipos de listas: contiguas y enlazadas. En una lista contigua los elementos son adyacentes en la memoria de la computadora y tienen unos límites, izquierdo y derecho, que no pueden ser rebasados cuando se añade un nuevo elemento. Se implementan a través de arrays. En este tipo de listas la inserción o eliminación de un elemento, excepto en lacabecera o final de la lista necesitará una traslación de parte de los elementos de la misma. Una lista enlazada se caracteriza porque los elementos se almacenan en posiciones de memoria que no son contiguas, por lo que cada elemento necesita almacenar la referencia al siguiente elemento de la lista.
Las listas enlazadas son mucho más flexibles y potentes que las listas contiguas y, en ellas, lainserción o eliminación de un elemento no requiere el desplazamiento de otros elementos de la misma.
Las listas enlazadas se suelen construir vinculando nodos. Esta forma de organización resulta la más adecuada si el número de elementos a almacenar en un momento dado es impredecible. Si se utiliza un array para almacenar una serie o colección de elementos; en el caso en que el número de elementosexceda el tamaño establecido para el citado array en el momento de su creación, los nuevos elementos no se podrán almacenar en dicho array y la posible solución será la creación de un nuevo array de las dimensiones adecuadas y el traspaso de la información del viejo al nuevo array. Se ha de tener en cuenta que la clase Vector de Java permite crear estructuras de datos de tipo array de objetosredimencionables durante la ejecución del programa. En el caso de utilizar nodos vinculados para almacenar la información, éstos se crean y destruyen conforme se requieran , de esta manera la lista aumenta o disminuye de tamaño dinámicamente y solo se llena cuando se agota la memoria disponible. El acceso a la lista se realiza mediante una referencia al primer nodo de la misma y, para marcar su fin, seestablece la referencia de enlace del último nodo a null.


Estructura Lineal
Una lista enlazada consta de un número de elementos (llamados NODOS) y cada elemento tiene dos componentes como mínimo: una referencia a un elemento de la lista (siguiente) y un campo que tiene un valor (Nombre).

Se subdividen en:
1. Listas simplemente enlazadas
2. Listas doblemente enlazadas
3. Listas simplementeenlazadas circulares
4. Listas doblemente enlazadas circulares

1. Listas simplemente enlazadas
Se llama así porque cada modo tiene un único enlace que conecta a ese modo con uno siguiente. Esta lista es eficiente cuando se hacen recorridos directos (secuenciales)

2. Listas doblemente enlazadas

Cada modo contiene dos enlaces, uno a sus predecesores y otro a su nuevo sucesor. Eseficiente tanto en su recorrido directo como inverso.

Se caracterizan porque su recorrido puede realizarse tanto desde frente a final como desde frente a final. Este tipo de listas se puede construir vinculando nodos. Cada nodo de dichas listas consta de un campo con información y otros dos campos (ant y sig) que referencian que referencian el nodo antecesor y el sucesor respectivamente. Además en unalista doblemente enlazada, cada nodo, excepto el primero y el último, se encuentra referenciado por otros dos, su sucesor y su antecesor.

En la operación de inserción será necesario será necesario tener en cuenta si se trata del primer elemento de la lista; en caso contrario, el nuevo elemento ha de colocarse por delante del primero, en una posición intermedia o al final. La supresión debe...