Listas enlazadas








CA 15






Estructuras de datos definidas por programador





CONTENIDO
15.1. Listas.
15.2. Implementación de una lista.
15.3. Lista ordenada.
15.4. Listas genéricas y uso de interfaces.
15.5. Listas doblemente enlazadas.
15.6. Pilas.
15.7. Colas.
15.8. Colas circulares.










41 1
Java 2. Manual de programación


Java,como los restantes lenguajes de programación, suministra una serie de de datos básicos y una serie de operaciones para su manipulación. En ocasiones, estos tipos de datos no son los adecuados para resolver un problema y es necesario crear nuevos tipos de datos, que será preciso definir especificando tanto sus datos componentes como las operaciones que los manipulan. Estos tipos de datos sedefinen mediante clases y proporcionan una de las características más importantes de la (Pro- gramación Orientada a Objetos), la reutilización de componentes. Las colecciones de datos organizados y a las que se accede de forma perfectamente definida constituyen una estructura de datos. Existe un cierto número de estructuras de datos de reconocida uti- lidad, cuyo uso se repitefrecuentemente en los programas, y que pueden llegar a considerarse como una extensión de los tipos básicos del lenguaje; estas estructuras tienen un nombre y unas características establecidas y entre ellas destacan: listas, pilas, colas, árboles y Las tres primeras son estructuras de datos lineales, puesto que en ellas cada elemento tiene un único prede- cesor y un Único sucesor, mientras que las dosÚltimas son estruc- turas no lineales. En este capítulo se describen estructuras de datos lineales, ya que las estructuras de datos no lineales quedan fuera de los objetivos de este libro.
Dada la importancia de las estructuras de datos, Java ofrece clases que implementan algunas de ellas: java. .vector,






15.1. LISTAS


Una lista es una secuencia de elementos del mismo tipo o clasealmacenados en me- moria. 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. número de elementos de una lista se denomina longitud. En una lista es posible añadir nuevos elementos o suprimirlos en cualquier posición.
Existen dos tipos de listas: contiguas yenlazadas. En una lista contigua los ele-
mentos 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 ele- mento. Se implementan a través de arrays. En este tipo de listas la inserción o eli- minación de un elemento, excepto en la cabecera o final de la lista necesitará una traslación de parte de loselementos de la misma (Fig. 15.1). Una lista enlazada se caracteriza porque los elementos se almacenan en posiciones de memoria que no son contiguas (adyacentes), por lo que cada elemento necesita almacenar la refe- rencia al siguiente elemento de la lista.



Las listas enlazadas son mucho más flexibles y potentes que las listas contiguas y, en ellas, la inserción o eliminación (supresión) de unelemento no requiere el des- plazamiento de otros elementos de la misma.
Las listas enlazadas (Fig. 15.3) se suelen construir vinculando nodos (objetos que contienen al menos un miembro que es una referencia a otro objeto de su mismo tipo, Fig. 15.2). 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 arraypara almacenar una serie o colección de elementos; en el caso de que el número de elementos exceda 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 tras- paso de la información del viejo al nuevo array. Se ha de tener en...