listas enlazadas

Listas Enlazadas

GeneralidadesO Es una colección lineal de elementos

llamados nodos.O Cada nodo se divide en 2 partes: la

primera es la información asociada al elemento y la segunda el enlace o puntero al siguiente elemento de la lista

GeneralidadesO A los componentes de un nodo se les

llama también campos: el campo de valor y el campo de enlace.

O Al campo de enlace del último nodo de la lista se le representa con la palabra null, también puede ser una barra inclinada o el símbolo eléctrico de tierra.

GeneralidadesO Se cuenta con un acceso inicial que

apunta a un elemento de la lista, el cual puede reconocerse como el primero y el orden está dado por los enlaces de cada elemento que apunta al que le sigue.

GeneralidadesO A diferencia de una arreglo, el acceso a

un elemento de una lista enlazada se realiza mediante el puntero (enlace).

O Mientras que en un arreglo los elementos están continuos en la memoria, en una lista enlazada los elementos están dispersos

Tipos de Listas Enlazadas1) Lista enlazada simple

2) Lista doblemente enlazada

3) Lista circular

NotacionesO L :Puntero externo al primer nodo

de listaO Ptr :Puntero a un nodo de la listaO Ptr.Info :Campo dato del nodo apuntado

por PtrO Ptr.Enlace :Campo puntero que apunta al

sgt. Nodo

O CrearNodo(aux):Asigna la dirección aux de un nodo

O QuitarNodo(aux):Libera el espacio de memoria asignado a aux

Operaciones (Métodos)1) Creación().- Inicializa la lista al estado

vacío.a) Diseñamos la clase cNodo con un campo

de valor (tipo de dato) y otro campo de tipo cNodo que será el enlace.

b) Diseñamos la clase cLista con campo de tipo cNodo que es el acceso inicial a la lista y un constructor que asigne a null su estado (L apunta a null, no tiene una dirección en memoria).

Operaciones (Métodos)2) ListaVacía().- Determinamos si la lista está

vacía.a) Creamos el método ListaEmpty() de tipo booleano

para la clase cLista, donde verificamos si L apunta a null.

3) Recorrido():Accede y procesa cada elemento de la lista.

a) Diseñamos el método vacío Recorre(), Ptr (auxiliar) apunta al nodo inicial, y si no esta vacío (no es el último nodo) apunta al enlace del siguiente nodo.

Operaciones (Métodos)

Ptr

Utilizamos un puntero

auxiliar(Ptr)

Af100 Am400

Af100 Am400

Operaciones (Métodos)

Ptr

Af100 Am400

Af100 Am400

Operaciones (Métodos)

Ptr

Af100 Am400

Af100 Am400

4) Inserción(): Añade un nuevo elemento al inicio de la lista.

a) Diseñamos en la clase cLista, el método vacío Insert_Inicio(int item) con un parámetro item de tipo entero, declaramos una variable auxiliar de tipo cNodo a la cual le colocamos el valor del nuevo item (nuevo nodo). Verificamos si la lista está vacía, de estarlo, L que apuntaba a null apunta ahora al auxiliar (que se convierte en el primer elemento de la lista) y el enlace del auxiliar apunta a null, de lo contrario, el enlace del auxiliar apunta a L y L apunta al auxiliar.

Está vacía: *) L null

**) L

***)

Operaciones (Métodos)

auxiliar

auxiliar

Operaciones (Métodos)No está vacía:

auxiliar

L 45 56 49

78

L 45 56 4978

5) Inserción(): Añade un nuevo elemento al final de la lista.

a) Diseñamos en la clase cLista, el método vacío Insert_Final(int item) con un parámetro item de tipo entero, declaramos una variable auxiliar de tipo cNodo a la cual le colocamos el valor del nuevo item (nuevo nodo). Verificamos si la lista está vacía; de estarlo, L que apuntaba a null apunta ahora al auxiliar (que se convierte en el primer elemento de la lista) y el enlace del auxiliar apunta a null, de lo contrario, verificamos si los enlaces son diferentes de null los recorremos y cuando encontramos el último el Ptr apunta al auxiliar y el enlace del auxiliar apunta a null.

Operaciones (Métodos)

Operaciones (Métodos)No está vacía:

Ptr

!=null

Ptr

!=null

auxiliar

Ptr

6) Eliminación(): Elimina un elemento al inicio.a) Diseñamos en la clase cLista, el método vacío

Eliminar_Iniciol(), declaramos una variable auxiliar de tipo cNodo (nuestro puntero Ptr) y apuntamos a L. Verificamos si el enlace de L es igual a null, de serlo L apunta a null (queda vacía); de lo contrario L apuntará al siguiente enlace eliminando el nodo que se pueda encontrar en la cabecera.

Operaciones (Métodos)

6) Eliminación(): Elimina un elemento al final.a) Diseñamos en la clase cLista, el método vacío Eliminar_Final(),

declaramos una variable auxiliar de tipo cNodo (nuestro puntero Ptr) y otra variable del mismo tipo, Ptr apunta a L. Verificamos si el enlace de L es igual a null(es el último nodo), de serlo L apunta a null (queda vacía); de lo contrario mientras el enlace de Ptr(el siguiente nodo) sea diferente de null, la segunda variable apunta a Ptr y Ptr apunta al enlace del siguiente nodo, una vez que la condición sea falsa el enlace de la segunda variable apunta a null.

Operaciones (Métodos)

Main