Capitulo IV: Listas

Definicion

Una lista es una colección de elementos homogéneos entre los cuales existe una relación lineal en donde cada elemento indica la dirección donde se encuentra el siguiente elemento de la lista.

Una lista se puede represtentar de dos formas:

• Estática: su tamaño se limita en tiempo de compilación. Ejemplo: arreglos
• Dinámica: su tamaño puede crecer indefinidamente en tiempo de ejecución. Ejemplos: listas enlazadas simples, listas enlazadas dobles, lisas circulares, pilas, colas.

Características

• Cada elemento o nodo de la lista, a excepción del primero, tiene un único predecesor que debe indicar donde se encuentra el siguiente elemento.
• Cada elemento de la lista a excepción del último tiene un único sucesor.
• Las listas son flexibles y permiten cambios en la implementación

Representación de la estructura en memoria

Una lista se compone de nodos y estos a su vez están compuestos por dos partes:

1. Campo dato o información
2. Campo de enlace

En la implementación por los general un nodo de la lista se abstrae de un clase:

class Nodo:
    dato = None
    siguiente = None

    def __init__(sig):
        self.siguiente = sig

Operaciones

• Insertar( ): agregar un nuevo nodo a la lista
• Eliminar( ): quitar un nodo de la lista
• Buscar( ): encontrar un nodo dentro de la lista
• Modificar( ): actualizar la informaciónde un determinado nodo dentro de la lista

Lista Simplemente Enlazadas

Se refieren a una colección de elementos cuya relación lineal es determinada por la posición del elemento en la lista.

Características

• En cada nodo existe un solo enlace o referencia hacia el siguiente.
• Solo el úlimo nodo de la lista contendrá una referencia nula (apuntará a Nulo)
• Una lista de este tipo está dada en sun solo sentido

Implementación de operaciones

Operación Inserción

Caso 1: Cuando la lista enlazada simple no existe

1. Leer valor
2. Se crea un nodo y se asigna su referencia a top
3. Fijar su campo de información
4. Se asigna el valor nulo al campo de enlace

SINOPSIS:
Utilidad: añadir un elemento al inico de la lista L
Datos de entrada: la lista L y el nuevo elemento
Datos de salida: la lista L con el nuevo elemento al inicio
Precondición: ninguna
Poscondición: la lista L contiene el elemento nuevo al inicio

Caso 2: Cuando el nodo se debe insertar antes del primero

1. Leer el valor
2. Crear un nuevo nodo temporal
3. Inicializar el campo de información del nodo temporal
4. Asignar la referencia de inicio de la lista (top) al

Caso 3: Cuando el nodo se debe insertar después del último nodo

1. Leer el valor
2. Crear un nuevo nodo temporal
3. Crear una variable de referencia auxiliar que almacene la referencia del inicio de la lista (top)
4. Inicializar el campo de información del nodo temporal
5. Asignar nulo al campo de enlace del nuevo nodo
6. Recorrer la lista hasta el final
7. Asignar la referencia del nodo temporal al campo de enlace del último nodo de la lista.

SINOPSIS:
Utilidad: añadir un elemento al final de la lista L
Datos de entrada: la lista L y el nuevo elemento
Datos de salida: la lista L con el nuevo elemento al final
Precondición: ninguna
Poscondición: la lista L contiene el elemento nuevo al final

Caso 4: Cuando el nodo debe insertarse entre nodos

1. Leer el valor
2. Leer el valor del nodo predecesor
3. Crear un nodo temporal
4. Crear una variable de referencia auxiliar que almacene la referencia del inicio de la lista (top)
5. Inicializar el campo de información del nodo temporal
6. Recorrer la lista hasta encontrar el nodo predecesor
7. Asignar al campo de enlace del nodo temporal la referencia del nodo sucesor
8. Asignar la referencia del nodo temporal al campo de enlace del nodo predecesor

SINOPSIS:
Utilidad: añadir un nuevo nodo en un orden específico dentro de la lista L
Datos de entrada: la lista L, el nuevo elemento y el nodo predecesor
Datos de salida: la lista L con el nuevo elemento insertado en el lugar que le corresponde
Precondición: ninguna
Poscondición: la lista L contiene al elemento nuevo en el orden que le corresponde

Operación Eliminación

Caso 1: Borrar el primer nodo

1. Asignar el enlace del campo siguiente del nodo apuntado por Top a top.

SINOPSIS:
Utilidad: quitar un elemento del inicio de la lista L
Datos de entrada: la lista L
Datos de salida: la lista L con un nodo menos y el valor del nodo eliminado
Precondición: las lista L no está vacía
Poscondición: la lista L con un nodo menos (el del inicio)

Caso 2: Borrar cualquier nodo que no sea el primero

1. Leer el valor
2. Localizar el nodo predecesor al nodo que se desea eliminar
3. Asignar al campo de enlace del nodo predecesor, la referencia del nodo que le sucede al que se desea eliminar. Si el nodo a eliminar es el último asignar nulo al campo de enlace del nodo predecesor.

SINOPSIS:
Utilidad: quitar un nodo de un orden específico de la lista L
Datos de entrada: la lista L y el elemento a eliminar
Datos de salida: la lista L con un elemento menos
Precondición: las lista L no esté vacía y que contenga el nodo a eliminar
Poscondición: la lista L contiene un elemento menos y corresponde al que se eliminó

Operación Búsqueda

Buscar un nodo

1. Leer el valor
2. Recorrer la lista hasta encontrar el valor

SINOPSIS:
Utilidad: recorrer la lista L hasta encontrar un determinado nodo dentro de la misma
Datos de entrada: la lista L y el elemento a buscar
Datos de salida: verdadero si se ha encontrado el nodo, caso contrario falso
Precondición: las lista L no esté vacía
Poscondición: ninguna

Modelado UML

Ejercicio:

Codificar en el lenguaje de programación establecido la definición de la clase Lista Simple.

class ListaSimple:
    # Atributo de la Clase
    top = None

    def __init__(self):
        # Inicialización del campo de información y de la referencia
        self.dato = None
        self.sig = None

    def es_vacia(self):
        if ListaSimple.top is None:
            return True
        else:
            return False

    def insertar_vacia(self, dato):
        if self.es_vacia():
            ListaSimple.top = ListaSimple()
            ListaSimple.dato = dato
            print("El nodo insertado es el primero")
        else:
            print("La lista ya contiene elementos")

    def insertar_inicio(self, dato):
        """
        Inserta el elemento en el inicio de la lista
        """
        if not self.es_vacia():
            tmp = ListaSimple()
            tmp.dato = dato
            tmp.sig = ListaSimple.top
            ListaSimple.top = tmp
        else:
            print("No puede insertarse al final ... lista no contiene nodos")

    def insertar_final(self, dato):
        """
        Inserta el elemento al final de la lista
        """
        if not self.es_vacia():
            tmp = ListaSimple()
            tmp.dato = dato
            auxtop = ListaSimple.top
            # Se recorre la lista
            while auxtop.sig is not None:
                auxtop = auxtop.sig
            auxtop.sig = tmp
        else:
            print("No puede insertarse al final ... lista no contiene nodos")

    def insertar_entre_nodos(self, refdato, dato):
        # El campo refdato determina el nodo luego del cual debe insertarse
        if not self.es_vacia():
            tmp = ListaSimple()
            tmp.dato = dato
            auxtop = ListaSimple.top
            # Se recorre la lista
            while auxtop.dato is not dato:
                auxtop = auxtop.sig
                # Si se llega al nodo referencia
                if auxtop.dato == refdato:
                    tmp.sig = auxtop.sig
                    tmp.sig = auxtop
        else:
            print("No puede insertarse al final ... lista no contiene nodos")

    def presentar(self):
        if self.es_vacia():
            print("No existen nodos en la lista")
        else:
            auxtop = ListaSimple.top
            while auxtop is not None:
                print("[{0}]".format(auxtop.dato), end='->')
                auxtop = auxtop.sig