clase 7 - listas enlazadas

8/19/2019 Clase 7 - Listas Enlazadas

http://slidepdf.com/reader/full/clase-7-listas-enlazadas 1/36



Las estructuras de datos lineales deelementos homogéneos utilizaban arrayspara implementar tales estructuras, siendo

los elementos de tipo primitivo (int, long,double...)

Esta técnica obliga a fjar por adelantado el

espacio a ocupar en memoria



Listas Enlazadas - Concepto

Una lista enlazada es una colección o secuenciade elementos dispuestos uno detrs de otro, en la!ue cada elemento se conecta al siguiente

elemento por un "enlace# o "re$erencia#% La idea es consiste en construir una lista cuyoselementos, llamados nodos, se componen de dospartes (campos) & la primera parte contiene la

in$ormación y es, por consiguiente, un valor de untipo genérico 'denominado (ato, )ipoElemento,*n$o , etc%+, y la segunda parte es una re$erencia'denominado enlace o sgte + !ue apunta 'enlaza+

al siguiente elemento de la lista%



Listas Enlazadas - Concepto



Listas Enlazadas - Clasifcación

Listas simplemente enlazadas% Cada nodo 'elemento+ contieneun nico enlace !ue lo conecta al nodo siguiente o nodosucesor% La lista es efciente en recorridos directos

Listas doblemente enlazadas% Cada nodo contiene dos enlaces,

uno a su nodo predecesor y otro a su nodo sucesor% La lista esefciente tanto en recorrido directo '"adelante#+ como enrecorrido inverso '"atrs#+

Lista circular simplemente enlazada% Una lista enlazadasimplemente en la !ue el ltimo elemento 'cola+ se enlaza al

primer elemento 'cabeza+ de tal modo !ue la lista puede serrecorrida de modo circular '"en anillo#+% Lista circular doblemente enlazada% Una lista doblemente

enlazada en la !ue el ltimo elemento se enlaza al primerelemento y viceversa% Esta lista se puede recorrer de modo

circular '"en anillo#+ tanto en dirección directa '"adelante#+como inversa '"atrs#+%



)( Lista

Una lista se utiliza para almacenar in$ormación delmismo tipo, con la caracter.stica de !ue puedecontener un nmero indeterminado de elementos y!ue estos elementos mantienen un orden e/pl.cito%

Cada elemento 'un nodo de la lista+ contiene ladirección del siguiente elemento%

Las inserciones se pueden realizar por cual!uier puntode la lista& por la cabeza 'inicio+, por el fnal, a partir o

antes de un nodo determinado de la lista% Laseliminaciones también se pueden realizar en cual!uierpunto0 adems, se eliminan nodos dependiendo delcampo de in$ormación o dato !ue se desea suprimir de

la lista%



1peraciones

Listavacia(L): *nicializa la lista L como lista vac.a Esvacia(L): (etermina si la lista L est vac.a Insertar(L,x,p): *nserta en la lista L un nodo con el

campo dato / , delante del nodo de dirección p Localizar(L,x): (evuelve la posición2dirección donde

est el campo de in$ormación x Suprimir(L,x): Elimina de la lista el nodo !ue contiene

el dato x % Anterior(L,p): (evuelve la posición2dirección del nodo

anterior a p % Primero(L): (evuelve la posición2dirección del primer

nodo de la lista L % Anula(L): 3ac.a la lista L %



1peraciones

Anula(L): 3ac.a la lista L inserPrimero(L,x): *nserta un nodo con el

dato / como primer nodo de la lista L% inserinal(L,x): *nserta un nodo con el dato

/ como ltimo nodo de la lista L%



(eclaración de un nodo



Ejemplo

La clase 4unto , representa un punto en el plano decoordenadas '/, y+% La clase 5odo con un campo datore$erencia a objetos de la clase 4unto % Estas clases$ormarn parte del pa!uete Lista4untos%



Ejemplo

Crear una lista enlazada de elementos !uealmacenen datos de tipo entero%



Ejemplo

El método crea una lista iterativamente hasta leer elvalor clave !" % Los valores de los nodos se leen delteclado, con llamadas al método leerEntero() % Elmétodo crearLista() devuelve una re$erencia al

objeto lista creado (t#is) %



*56E7C*85 (E U5 ELE9E5)1 E5 U5 L*6)

El nuevo elemento !ue se desea incorporara una lista se puede insertar de distintas$ormas, segn la posición o punto de

inserción& En la cabeza de la lista 'elemento primero+% En el fnal de la lista 'elemento ltimo+% ntes de un elemento especifcado% (espués de un elemento especifcado



*nserción en la cabeza de lalista:% Crear un nodo e inicializar el campo dato al nuevo

elemento% La re$erencia del nodo creado se asigna anuevo , variable local del método%

;% <acer !ue el campo enlace del nuevo nodo apunte ala cabeza 'primero+ de la lista original%

=% <acer !ue primero apunte al nodo !ue se ha creado%

Ejemplo&. Una lista enlazada contiene tres elementos, :>, ;? y

@>% *nsertar un nuevo elemento, @, en cabeza de lalista%



4aso :



4aso ;

El campo enlace del nuevo nodo apunta alnodo primero actual de la lista%



4aso =

6e cambia la re$erencia de primero para !ue apunteal nodo creado0 es decir, primero apunta al mismonodo al !ue apunta nuevo%



Código $uente método *nsertarCabezaLista



Ejercicio

Crear una lista de nmeros aleatorios% *nsertar losnuevos nodos por la cabeza de la lista% Un vezcreada la lista, se recorren los nodos para mostrarlos nmero pares% 6e crea una lista enlazada con nmeros enteros 6e defne la clase nodo y la clase lista 6e defnen los métodos insertarCabezaLista'+ y

visualizar'+ (esde el método main'+ se crea un objeto

Lista , se llama iterativamente al método !ueaAade nuevos elementos, y por ltimo se

llama a visualizar'+



*nserción al fnal de la lista

Es menos efciente ultimo%enlace B ne 5odo'entrada+0 ultimo B ultimo%enlace0

La primera sentencia crea un nodo, inicializandosu dato

El campo enlace del ltimo nodo !ueda

apuntando al nodo creado y as. se enlaza 6e pone la variable ultimo al nuevo ltimo nodode la lista

d d d l



*nsertar entre dos nodos de lalista Crear un nodo con el nuevo elemento y el

campo enlace a null % La re$erencia al nodo seasigna a nuevo

<acer !ue el campo enlace del nuevo nodoapunte al nodo r; , ya !ue el nodo creado seubicar justo antes de r;

La variable re$erencia anterior tiene ladirección del nodo r:, y eso e/ige hacer !ueanterior%enlace apunte al nodo creado%



4aso :

6e crea un nodo con el dato D? % La variableanterior apunta al nodo r: %



4aso ;

El campo enlace del nodo creado debeapuntar a r; % La dirección de r; se consiguecon anterior %enlace:



4aso =

4or ltimo, el campo enlace del nodo r:'anterior+ debe apuntar al nodo creado



9étodo

F6GUE( E5 L*6)6



F6GUE( E5 L*6)6E5LH(6 7ecorre la lista hasta encontrar el nodo con

el elemento% El algoritmo !ue se utiliza para localizar un

elemento en una lista enlazada, una vezencontrado el nodo, devuelve la re$erencia aese nodo



Utiliza la re$erencia .ndice para recorrer lalista, nodo a nodo%

La bs!ueda inicializa .ndice al nodo cabeza

'primero+ compara el nodo re$erenciado por.ndice con el elemento buscado si coincidela bs!ueda, termina, en caso contrario0.ndice avanza al siguiente nodo%

La bs!ueda termina cuando se encuentra elnodo, o bien cuando se ha recorrido la lista,y entonces indice toma el valor null



Código



Ejemplo

Escribir un método de bs!ueda alternativopara encontrar la dirección de un nodo dadasu posición en una lista enlazada%



Eliminación de un nodo

:% s!ueda del nodo !ue contiene el dato% 6eha de obtener la dirección del nodo aeliminar y la dirección del anterior%

;% El enlace del nodo anterior !ue apunte alsiguiente nodo del cual se elimina%

=% 6i el nodo a eliminar es el cabeza de la lista(primero) , se modifca primero para !uetenga la dirección del siguiente nodo%

@% 4or ltimo, la memoria ocupada por el nodose libera% Es el propio sistema el !ue libera el

nodo, al dejar de estar re$erenciado%

clase 7 - listas enlazadas

Documents