Guía Listas Enlazadas en Java PDF

Preview

Summary

Download Guía Listas Enlazadas en Java PDF

Description

UNIVERSIDAD DE CUNDINAMARCA FACULTAD DE INGENIERÍA INGENIERÍA DE SISTEMAS GUÍA – LISTAS SIMPLEMENTE ENLAZADAS

PAGINA 1 DE 13

Listas simplemente enlazadas Al contrario de las estructuras de datos estáticas (arrays - vectores y tablas), cuyo tamaño en memoria permanece inalterable durante la ejecución del programa, las estructuras de datos dinámicas crecen y se contraen a medida que se ejecuta el programa. La estructura de datos que se estudiará en esta guía es la lista enlazada; una colección de elementos (denominados nodos) dispuestos uno a continuación de otro, cada uno de ellos conectado al siguiente por un “enlace” o “referencia”. Se desarrollan métodos para insertar, buscar y borrar elementos en listas enlazadas. De igual modo, se muestra el tipo abstracto de datos (TAD) que representa las listas enlazadas. Las listas enlazadas son estructuras muy flexibles y con numerosas aplicaciones en el mundo de la programación. Una lista enlazada es una colección o secuencia de elementos dispuestos uno detrás de otro, en la que cada elemento se conecta al siguiente elemento por un “enlace” o “referencia”. La idea básica consiste en construir una lista cuyos elementos, llamados nodos, se componen de dos partes (campos): la primera parte contiene la información y es, por consiguiente, un valor de un tipo genérico (denominado Dato, TipoElemento, Info, etc.), y la segunda parte es una referencia (denominado enlace o siguiente, etc) que apunta (enlaza) al siguiente elemento de la lista.

Figura No. 1 La representación gráfica más conocida es aquella que utiliza una caja (un rectángulo) con dos secciones en su interior. En la primera sección se escribe el elemento o valor del dato, y en la segunda sección, el enlace o referencia mediante una flecha que sale de la caja y apunta al nodo siguiente.

ESTRUCTURAS DE INFORMACIÓN ING. MAGALY PÁEZ OVIEDO

UNIVERSIDAD DE CUNDINAMARCA FACULTAD DE INGENIERÍA INGENIERÍA DE SISTEMAS GUÍA – LISTAS SIMPLEMENTE ENLAZADAS

PAGINA 2 DE 13

Figura No. 2

Los enlaces se representan por flechas para facilitar la comprensión de la conexión entre dos nodos e indicar que el enlace tiene la dirección en memoria del siguiente nodo. Los enlaces también sitúan los nodos en una secuencia. En la gráfica No.2, los nodos forman una secuencia desde el primer elemento (e1) al último elemento (en). El primer nodo se enlaza al segundo, éste se enlaza al tercero, y así sucesivamente hasta llegar al último nodo, que debe ser representado de forma diferente para significar que este nodo que no se enlaza a ningún otro. A continuación, se muestran diferentes representaciones gráficas utilizadas para dibujar el campoenlace del último nodo.

Figura No. 3 Una lista simplemente enlazada es una estructura de datos lineal, dinámica, formada por una colección de elementos llamados nodos. Cada nodo está formado por dos partes: la primera de ellas se utiliza para almacenarla información

ESTRUCTURAS DE INFORMACIÓN ING. MAGALY PÁEZ OVIEDO

UNIVERSIDAD DE CUNDINAMARCA FACULTAD DE INGENIERÍA INGENIERÍA DE SISTEMAS GUÍA – LISTAS SIMPLEMENTE ENLAZADAS

PAGINA 3 DE 13

(razón de ser de la estructura de datos), y la segunda se usa para guardar la dirección del siguiente nodo (apuntador). La siguiente presenta un esquema de un nodo. Cabe destacar, que de cada nodo sólo conoce la dirección del nodo que le sucede.

Figura No. 4 A continuación, se muestra la representación gráfica de una lista simplemente enlazada.

Figura No. 5 La lista está formada por una colección de nodos, cada uno de los cuales apunta al siguiente nodo, excepto el último que en la posición dedicada a la dirección de su vecino tiene el valor NULL. Además, se puede observar que se requiere de un apuntador (referencia) al primer elemento de la lista. Como éste no tiene predecesor, es indispensable que una variable tipo referencia (apuntador) almacene su dirección.

ESTRUCTURAS DE INFORMACIÓN ING. MAGALY PÁEZ OVIEDO

UNIVERSIDAD DE CUNDINAMARCA FACULTAD DE INGENIERÍA INGENIERÍA DE SISTEMAS GUÍA – LISTAS SIMPLEMENTE ENLAZADAS

PAGINA 4 DE 13

Tipo abstracto De datos (TAD) lista Una lista se utiliza para almacenar información del mismo tipo, con la característica de que puede contener un número indeterminado de elementos y que estos elementos mantienen un orden explícito. Este ordenamiento explícito implica que cada elemento (un nodo de la lista) contiene la dirección del siguiente elemento. Una lista es una estructura de datos dinámica. El número de nodos puede variar rápidamente en un proceso, aumentando por inserciones o disminuyendo por eliminación de nodos. Las inserciones se pueden realizar por cualquier punto de la lista: por la cabeza (inicio), por el final, a partir o antes de un nodo determinado de la lista. Las eliminaciones también se pueden realizar en cualquier punto; además, se eliminan nodos dependiendo del campo de información o dato que se desea suprimir de la lista. Operaciones En listas enlazadas La implementación del TAD Lista requiere, en primer lugar, declarar la clase Nodo, en la que se combinarán sus dos partes: el dato (entero, real, doble, carácter o referencias a objetos) y un enlace. Además, la clase Lista con las operaciones y el atributo con la cabeza de la lista. Las operaciones tendrán las siguientes funciones: • Inicialización o creación. • Insertar elementos en la lista. • Eliminar elementos de la lista. • Buscar elementos de la lista. • Recorrer la lista enlazada. • Comprobar si la lista está vacía. Inserción al principio de la lista Se presenta un esquema de la inserción de un nuevo elemento al inicio de la lista.

Figura No. 6 ESTRUCTURAS DE INFORMACIÓN ING. MAGALY PÁEZ OVIEDO

UNIVERSIDAD DE CUNDINAMARCA FACULTAD DE INGENIERÍA INGENIERÍA DE SISTEMAS GUÍA – LISTAS SIMPLEMENTE ENLAZADAS

PAGINA 5 DE 13

Inserción al final de la lista Otro caso frecuente de inserción es cuando interesa agregar un nuevo elemento al final de la lista. Se presenta en la Figura No. 7 esta operación. Se crea un nuevo nodo, apuntado por P, y se establece un enlace entre el último nodo de la lista y éste. Para llegar al último elemento es necesario recorrer toda la lista, desde el primero hasta dicho nodo. Si la lista es definida con un apuntador al inicio y otro al final, el recorrido hasta el último nodo se omite. Sin embargo, según la definición previa de la lista, se requiere hacer la operación auxiliar mencionada.

Figura No. 7 Inserción antes de un nodo dado como referencia En la figura No. 8 se presenta un esquema de la inserción de un nuevo elemento antes de un nodo que almacena cierto dato dado como referencia. Este caso es útil para el manejo de listas cuya información está ordenada. Para llevar a cabo este tipo de inserción, primero se busca el nodo dado como referencia guardando la dirección del anterior (apuntado por Ant). Si se encuentra el nodo, entonces se crea otro (cuya dirección es almacenada en la variable P) estableciéndose el enlace entre éste y el dado como referencia, y entre el anterior y el nuevo.

Figura No. 8

ESTRUCTURAS DE INFORMACIÓN ING. MAGALY PÁEZ OVIEDO

UNIVERSIDAD DE CUNDINAMARCA FACULTAD DE INGENIERÍA INGENIERÍA DE SISTEMAS GUÍA – LISTAS SIMPLEMENTE ENLAZADAS

PAGINA 6 DE 13

Inserción después de un nodo dado como referencia En la figura No. 9 se presenta un esquema de la inserción de un nuevo elemento después de un nodo que almacena cierto dato dado como referencia, Este caso, lo mismo que el anterior, es usado cuando se trabaja con listas cuya información está ordenada. Se empieza buscando el nodo que guarda el dato dado como referencia. Sí se encuentra, entonces se crea un nodo cuya dirección queda en la variable P. Luego se establecen los enlaces requeridos para relacionar el nuevo elemento con el dado como referencia y con el sucesor de este último.

Figura No. 9

ESTRUCTURAS DE INFORMACIÓN ING. MAGALY PÁEZ OVIEDO

UNIVERSIDAD DE CUNDINAMARCA FACULTAD DE INGENIERÍA INGENIERÍA DE SISTEMAS GUÍA – LISTAS SIMPLEMENTE ENLAZADAS

PAGINA 7 DE 13

IMPLEMENTACIONES EN JAVA CLASE Nodo. Tiene la finalidad de definir las características de los elementos (nodos) de la lista, de tal forma que al crear un objeto de esta clase se permita almacenar un dato y la referencia el siguiente elemento de la lista.

ESTRUCTURAS DE INFORMACIÓN ING. MAGALY PÁEZ OVIEDO

UNIVERSIDAD DE CUNDINAMARCA FACULTAD DE INGENIERÍA INGENIERÍA DE SISTEMAS GUÍA – LISTAS SIMPLEMENTE ENLAZADAS

PAGINA 8 DE 13

CLASE Lista. Tiene la finalidad de definir las características de la lista y las operaciones que se podrán realizar. El objeto de esta clase contiene, a su vez, objetos de la clase Nodo, que representan a cada uno de los elementos de la lista.

Agregar nodos al inicio de la lista la implementación del siguiente método (agregarInicio), permite enlazar elementos al inicio de la lista.

ESTRUCTURAS DE INFORMACIÓN ING. MAGALY PÁEZ OVIEDO

UNIVERSIDAD DE CUNDINAMARCA FACULTAD DE INGENIERÍA INGENIERÍA DE SISTEMAS GUÍA – LISTAS SIMPLEMENTE ENLAZADAS

PAGINA 9 DE 13

La siguiente implementación crea 4 nodos.

ESTRUCTURAS DE INFORMACIÓN ING. MAGALY PÁEZ OVIEDO

UNIVERSIDAD DE CUNDINAMARCA FACULTAD DE INGENIERÍA INGENIERÍA DE SISTEMAS GUÍA – LISTAS SIMPLEMENTE ENLAZADAS

PAGINA 10 DE 13

Listar los nodos de la lista Para mostrar la lista es necesario crear un método que realice la operación en la clase Lista.

Ajustando la clase CrearLista que crea la lista:

ESTRUCTURAS DE INFORMACIÓN ING. MAGALY PÁEZ OVIEDO

UNIVERSIDAD DE CUNDINAMARCA FACULTAD DE INGENIERÍA INGENIERÍA DE SISTEMAS GUÍA – LISTAS SIMPLEMENTE ENLAZADAS

PAGINA 11 DE 13

Agregar un nodo al final de la lista La implementación del siguiente método (agregarFinal) en la clase Lista, permite enlazar elementos al final de la lista.

Agregar nodo por referencia La implementación del siguiente método (agregarPorReferencia) en la clase Lista, permite enlazar elementos en una parte intermedia de la lista después de un nodo enviado por referencia.

ESTRUCTURAS DE INFORMACIÓN ING. MAGALY PÁEZ OVIEDO

UNIVERSIDAD DE CUNDINAMARCA FACULTAD DE INGENIERÍA INGENIERÍA DE SISTEMAS GUÍA – LISTAS SIMPLEMENTE ENLAZADAS

PAGINA 12 DE 13

Eliminar un nodo La implementación del siguiente método (eliminarNodo) en la clase Lista, permite retirar un elemento de la lista.

Actividad Listas Simplemente Enlazadas Implemente un algoritmo en java que disponga a través de un menú los siguientes requerimientos funcionales: A. B. C. D. E. F. G.

Agregar un nodo al inicio de la lista. Agregar un nodo al final de la lista. Agregar un nodo en una parte intermedia de la lista. Buscar un dato almacenado en un nodo dentro de la lista. Listar todos los elementos de la lista. Suprimir un nodo de la lista. Ordenar los elementos de la lista. ESTRUCTURAS DE INFORMACIÓN ING. MAGALY PÁEZ OVIEDO

UNIVERSIDAD DE CUNDINAMARCA FACULTAD DE INGENIERÍA INGENIERÍA DE SISTEMAS GUÍA – LISTAS SIMPLEMENTE ENLAZADAS

PAGINA 13 DE 13

Bibliografía Estructuras de datos en java. Luis Joyanes Aguilar, editorial Mc Graw Hill Programación en C++, Luis Joyanes Aguilar, editorial Mc Graw Hill. C++ para ingeniería y ciencias. Gary J. Bronson, Thomson Editores C++ Como programar. Deitel & Deitel. Editorial Pearson Prentice Hall

ESTRUCTURAS DE INFORMACIÓN ING. MAGALY PÁEZ OVIEDO...