3.21. Implementación de una lista no ordenada: Listas enlazadas

Con el fin de implementar una lista no ordenada, vamos a construir lo que comúnmente se conoce como una lista enlazada (encadenada o ligada). Recordemos que tenemos que estar seguros de que podemos mantener el posicionamiento relativo de los ítems. Sin embargo, no existe ningún requisito que mantenga ese posicionamiento en memoria contigua. Por ejemplo, considere la colección de elementos mostrados en la Figura 1. Parece que estos valores se han colocado al azar. Si podemos mantener alguna información explícita en cada ítem, es decir, la ubicación del ítem siguiente (véase la Figura 2), entonces la posición relativa de cada ítem puede expresarse simplemente siguiendo el enlace de un ítem al siguiente.

../_images/idea.png

Figura 1: Ítems no restringidos en su ubicación física

Figura 1: Ítems no restringidos en su ubicación física
../_images/idea2.png

Figura 2: Posiciones relativas mantenidas por enlaces explícitos

Figura 2: Posiciones relativas mantenidas por enlaces explícitos

Es importante tener en cuenta que la ubicación del primer ítem de la lista debe especificarse explícitamente. Una vez que sepamos dónde está el primer ítem, éste puede decirnos dónde está el segundo, y así sucesivamente. La referencia externa se conoce a menudo como la cabeza de la lista. Del mismo modo, el último ítem necesita saber que no hay ningún ítem siguiente.

3.21.1. La clase Nodo

El bloque constructivo básico para la implementación de la lista enlazada es el nodo. Cada objeto nodo debe contener al menos dos piezas de información. En primer lugar, el nodo debe contener el ítem de lista en sí mismo. Esto lo llamaremos el campo de dato del nodo. Además, cada nodo debe contener una referencia al siguiente nodo. El Programa 1 muestra la implementación en Python. Para construir un nodo, usted debe proporcionar el valor inicial del dato del nodo. La evaluación de la instrucción de asignación que aparece más abajo producirá un objeto nodo que contiene el valor 93 (véase la Figura 3). Tenga en cuenta que típicamente representaremos un objeto nodo como se muestra en la Figura 4. La clase Nodo también incluye los métodos habituales para acceder y modificar el dato y la siguiente referencia.

Programa 1

class Nodo:
    def __init__(self,datoInicial):
        self.dato = datoInicial
        self.siguiente = None

    def obtenerDato(self):
        return self.dato

    def obtenerSiguiente(self):
        return self.siguiente

    def asignarDato(self,nuevodato):
        self.dato = nuevodato

    def asignarSiguiente(self,nuevosiguiente):
        self.siguiente = nuevosiguiente

Creamos objetos Nodo de la manera habitual.

>>> temp = Nodo(93)
>>> temp.obtenerDato()
93

El valor de referencia especial de Python None desempeñará un papel importante en la clase Nodo y más tarde en la propia lista enlazada. Una referencia a None indicará el hecho de que no hay nodo siguiente. Fíjese en el constructor que un nodo se crea inicialmente con siguiente asignado a None. Puesto que esto a veces se denomina “puesta a tierra del nodo”, usaremos el símbolo estándar de tierra para designar una referencia que se refiere a None. Siempre es una buena idea asignar explícitamente None a los valores de referencia iniciales siguientes.

../_images/node.png

Figura 3: Un objeto de nodo contiene el ítem y una referencia al siguiente nodo

Figura 3: Un objeto de nodo contiene el ítem y una referencia al siguiente nodo
../_images/node2.png

Figura 4: Representación típica para un nodo

Figura 4: Representación típica para un nodo

3.21.2. La clase ListaNoOrdenada

Como sugerimos anteriormente, la lista no ordenada se construirá a partir de una colección de nodos, cada uno vinculado al siguiente mediante referencias explícitas. Siempre y cuando sepamos dónde encontrar el primer nodo (que contiene el primer ítem), cada ítem posterior se puede encontrar sucesivamente siguiendo los enlaces subsiguientes. Con esto en mente, la clase ListaNoOrdenada debe mantener una referencia al primer nodo. El Programa 2 muestra el constructor. Tenga en cuenta que cada objeto de la lista mantendrá una sola referencia a la cabeza de la lista.

Programa 2

class ListaNoOrdenada:

    def __init__(self):
        self.cabeza = None

Inicialmente, cuando construimos una lista, no hay ítems. La instrucción de asignación

>>> milista = ListaNoOrdenada()

crea la representación de lista enlazada que se muestra en la Figura 5. Como hemos comentado en el apartado sobre la clase Nodo, la referencia especial None será utilizada nuevamente para indicar que la cabeza de la lista no se refiere a nada. Eventualmente, la lista de ejemplo dada anteriormente será representada por una lista enlazada como se muestra en la Figura 6. La cabeza de la lista se refiere al primer nodo que contiene el primer ítem de la lista. A su vez, ese nodo contiene una referencia al siguiente nodo (el siguiente ítem) y así sucesivamente. Es muy importante tener en cuenta que la clase lista en sí misma no contiene ningún objeto nodo. Contiene, en cambio, una sola referencia únicamente al primer nodo de la estructura enlazada.

../_images/initlinkedlist.png

Figura 5: Una lista vacía

Figura 5: Una lista vacía
../_images/linkedlist.png

Figura 6: Una lista enlazada de enteros

Figura 6: Una lista enlazada de enteros

El método estaVacia, que se muestra en el Programa 3, simplemente comprueba si la cabeza de la lista es una referencia a None. El resultado de la expresión booleana self.cabeza == None sólo será verdadero si no hay nodos en la lista enlazada. Dado que una lista nueva está vacía, el constructor y la comprobación de estar vacía deben ser coherentes entre sí. Esto muestra la ventaja de usar la referencia None para denotar el “final” de la estructura enlazada. En Python, None puede compararse con cualquier referencia. Dos referencias son iguales si ambas se refieren al mismo objeto. Usaremos esto con frecuencia en nuestros métodos restantes.

Programa 3

def estaVacia(self):
    return self.cabeza == None

Entonces, ¿cómo incluiremos ítems en nuestra lista? Tenemos que implementar el método agregar. Sin embargo, antes de que podamos hacer eso, necesitamos enfrentar la importante cuestión de dónde ubicar el nuevo ítem en la lista enlazada. Dado que esta lista no está ordenada, no es importante la ubicación específica del nuevo ítem con respecto a los otros elementos que ya están en la lista. El nuevo ítem puede ubicarse en cualquier parte. Con esto en mente, tiene sentido poner el nuevo ítem en la ubicación más fácil posible.

Recuerde que la estructura de lista enlazada nos proporciona sólo un punto de entrada, la cabeza de la lista. Todos los demás nodos sólo pueden ser alcanzados accediendo al primer nodo y luego siguiendo los enlaces subsiguientes. Esto significa que el lugar más fácil para agregar el nuevo nodo está justo en la cabeza, o al principio, de la lista. En otras palabras, haremos que el nuevo ítem sea el primer ítem de la lista y los elementos existentes tendrán que enlazarse a este nuevo primer ítem de modo que estarán a continuación de él.

La lista enlazada mostrada en la Figura 6 fue construida llamando al método agregar varias veces.

>>> milista.agregar(31)
>>> milista.agregar(77)
>>> milista.agregar(17)
>>> milista.agregar(93)
>>> milista.agregar(26)
>>> milista.agregar(54)

Note que, como 31 es el primer ítem agregado a la lista, eventualmente será el último nodo en la lista enlazada ya que cada uno de los otros ítems es agregado adelante de él. Además, puesto que 54 es el último ítem añadido, se convertirá en el dato del primer nodo de la lista enlazada.

El método agregar se muestra en el Programa 4. Cada ítem de la lista debe residir en un objeto nodo. La línea 2 crea un nuevo nodo y hace que el ítem sea su dato. Ahora debemos completar el proceso uniendo el nuevo nodo a la estructura existente. Esto requiere dos pasos como se muestra en la Figura 7. El paso 1 (línea 3) cambia la referencia siguiente del nuevo nodo para que se refiera al primer nodo antiguo de la lista. Ahora que el resto de la lista ha sido correctamente adjuntado al nuevo nodo, podemos modificar la cabeza de la lista para hacer referencia al nuevo nodo. La instrucción de asignación en la línea 4 asigna la cabeza de la lista.

El orden de los dos pasos descritos anteriormente es muy importante. ¿Qué sucede si se invierte el orden de las líneas 3 y 4? Si la modificación de la cabeza de la lista ocurre primero, el resultado se puede ver en la Figura 8. Dado que la cabeza era la única referencia externa a los nodos de lista, todos los nodos originales se pierden y ya no se puede acceder.

Programa 4

def agregar(self,item):
    temp = Nodo(item)
    temp.asignarSiguiente(self.cabeza)
    self.cabeza = temp
../_images/addtohead.png

Figura 7: Agregar un nuevo nodo es un proceso de dos pasos

Figura 7: Agregar un nuevo nodo es un proceso de dos pasos
../_images/wrongorder.png

Figura 8: Resultado de invertir el orden de los dos pasos

Figura 8: Resultado de invertir el orden de los dos pasos

Los siguientes métodos que implementaremos–tamano, buscar y remover–están basados en una técnica conocida como recorrido de listas enlazadas. Recorrido se refiere al proceso de visitar sistemáticamente cada nodo. Para ello utilizamos una referencia externa que comienza en el primer nodo de la lista. A medida que visitamos cada nodo, movemos la referencia al siguiente nodo “recorriendo” la siguiente referencia.

Para implementar el método tamano, necesitamos recorrer la lista enlazada y mantener un recuento del número de nodos que aparecieron. El Programa 5 muestra el código en Python para contar el número de nodos en la lista. La referencia externa se llama actual y se inicializa en la cabeza de la lista en la línea 2. Al comienzo del proceso no hemos visto ningún nodo, por lo que la cuenta se fija en \(0\). Las líneas 4-6 implementan realmente el recorrido. Mientras la referencia actual no haya visto el final de la lista (None), nos trasladaremos a través del siguiente nodo por medio de la instrucción de asignación en la línea 6. De nuevo, es muy útil la capacidad de comparar una referencia con None. Cada vez que actual se mueve a un nuevo nodo, agregamos \(1\) a contador. Finalmente, contador es devuelto cuando termina la iteración. La Figura 9 muestra este proceso a medida que avanza en la lista.

Programa 5

1
2
3
4
5
6
7
8
def tamano(self):
    actual = self.cabeza
    contador = 0
    while actual != None:
        contador = contador + 1
        actual = actual.obtenerSiguiente()

    return contador
../_images/traversal.png

Figura 9: Recorrido de una la lista enlazada desde la cabeza hasta el final

Figura 9: Recorrido de una la lista enlazada desde la cabeza hasta el final

La búsqueda de un valor en una implementación de lista enlazada de una lista no ordenada también utiliza la técnica de recorrido. A medida que visitamos cada nodo en la lista enlazada nos preguntaremos si los datos almacenados allí coinciden con el elemento que estamos buscando. En este caso, sin embargo, es posible que no tengamos que recorrer todo el camino hasta el final de la lista. De hecho, si llegamos al final de la lista, eso significa que el ítem que estamos buscando no debería estar presente. También, si encontramos el ítem, no hay necesidad de continuar.

El Programa 6 muestra la implementación del método buscar. Como en el método tamano, el recorrido se inicializa para comenzar en la cabeza de la lista (línea 2). También usamos una variable booleana que se llama encontrado para recordar si hemos localizado el ítem que estamos buscando. Puesto que no hemos encontrado el ítem al principio del recorrido, encontrado puede ser inicializado en False (línea 3). La iteración en la línea 4 tiene en cuenta ambas condiciones discutidas anteriormente. Mientras haya más nodos por visitar y no hayamos encontrado el ítem que estamos buscando, seguiremos comprobando el siguiente nodo. La pregunta de la línea 5 averigua si el ítem de datos está presente en el nodo actual. En caso afirmativo, encontrado puede ser puesto en True.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
def buscar(self,item):
    actual = self.cabeza
    encontrado = False
    while actual != None and not encontrado:
        if actual.obtenerDato() == item:
            encontrado = True
        else:
            actual = actual.obtenerSiguiente()

    return encontrado

Por ejemplo, considere la invocación al método buscar averiguando por el ítem 17.

>>> milista.buscar(17)
True

Dado que 17 está en la lista, el proceso de recorrido necesita moverse solamente al nodo que contiene el 17. En ese punto, la variable encontrado es cambiada a True y la condición del while fallará, llevando al valor devuelto indicado arriba. Este proceso se puede ver en la Figura 10.

../_images/search.png

Figura 10: Búsqueda exitosa del valor 17

Figura 10: Búsqueda exitosa del valor 17

El método remover requiere dos pasos lógicos. En primer lugar, necesitamos recorrer la lista buscando el ítem que queremos eliminar. Una vez que encontramos el ítem (recuerde que asumimos que está presente), debemos eliminarlo. El primer paso es muy similar a buscar. Comenzando con una referencia externa puesta en la cabeza de la lista, recorremos los enlaces hasta que descubrimos el ítem que buscamos. Dado que suponemos que el ítem está presente, sabemos que la iteración se detendrá antes de que actual obtenga el valor None. Esto significa que en la condición podemos usar simplemente la variable booleana encontrado.

Cuando encontrado toma el valor True, actual será una referencia al nodo que contiene el ítem a ser removido. Pero, ¿cómo lo eliminamos? Una posibilidad sería reemplazar el valor del ítem con algún marcador que sugiera que el ítem ya no está presente. El problema con este enfoque es que el número de nodos ya no coincidirá con el número de ítems. Sería mucho mejor remover el ítem mediante la eliminación completa del nodo.

Para remover el nodo que contiene el ítem, necesitamos modificar el enlace en el nodo anterior para que se refiera al nodo que sigue después de actual. Desafortunadamente, no hay manera de retroceder en la lista enlazada. Dado que actual se refiere al nodo delante de aquél donde queremos hacer el cambio, es demasiado tarde para hacer la modificación necesaria.

La solución a este dilema es usar dos referencias externas a medida que recorremos la lista enlazada. actual se comportará igual que antes, marcando la ubicación actual del recorrido. La nueva referencia, que llamaremos previo, siempre estará un nodo detrás de actual. De esta forma, cuando actual se detenga en el nodo que se va a eliminar, previo se referirá al lugar adecuado en la lista enlazada para la modificación.

El Programa 7 muestra el método remover completo. Las líneas 2-3 asignan valores iniciales a las dos referencias. Observe que actual comienza en la cabeza de la lista como en los otros ejemplos de recorrido. previo, sin embargo, se supone que va siempre un nodo detrás de actual. Por esta razón, previo comienza con un valor de None ya que no hay ningún nodo antes de la cabeza (ver la Figura 11). La variable booleana encontrado se volverá a utilizar para controlar la iteración.

En las líneas 6-7 preguntamos si el ítem almacenado en el nodo actual es el ítem que queremos remover. En caso afirmativo, encontrado puede ser puesto en True. Si no encontramos el ítem, previo y actual deben moverse un nodo hacia adelante. Una vez más, el orden de estas dos instrucciones es crucial. previo debe moverse primero un nodo hacia adelante a la ubicación de actual. En ese momento, actual se puede mover. Este proceso se conoce a menudo como “avance de oruga” ya que previo debe alcanzar a actual antes que actual se pueda mover hacia adelante. La Figura 12 muestra el movimiento de previo y actual a medida que avanzan en la lista buscando el nodo que contiene el valor 17.

Programa 7

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
def remover(self,item):
    actual = self.cabeza
    previo = None
    encontrado = False
    while not encontrado:
        if actual.obtenerDato() == item:
            encontrado = True
        else:
            previo = actual
            actual = actual.obtenerSiguiente()

    if previo == None:
        self.cabeza = actual.obtenerSiguiente()
    else:
        previo.asignarSiguiente(actual.obtenerSiguiente())
../_images/removeinit.png

Figura 11: Valores iniciales para las referencias previo y actual

Figura 11: Valores iniciales para las referencias previo y actual
../_images/prevcurr.png

Figura 12: previo y actual se mueven por la lista

Figura 12: previo y actual se mueven por la lista

Una vez que se ha completado el paso de búsqueda de remover, necesitamos eliminar el nodo de la lista enlazada. La Figura 13 muestra el enlace que debe modificarse. Sin embargo, hay un caso especial que necesita ser abordado. Si resulta que el ítem a ser eliminado es el primer ítem de la lista, entonces actual hará referencia al primer nodo de la lista enlazada. Esto también significa que previo será None. Hemos dicho anteriormente que previo se referiría al nodo cuya próxima referencia necesita ser modificada para completar la eliminación. En este caso, no es previo, sino la cabeza de la lista la que necesita ser cambiada (ver la Figura 14).

../_images/remove.png

Figura 13: Eliminación de un ítem intermedio de la lista

Figura 13: Eliminación de un ítem intermedio de la lista
../_images/remove2.png

Figura 14: Remoción del primer nodo de la lista

Figura 14: Remoción del primer nodo de la lista

La línea 12 nos permite comprobar si estamos tratando con el caso especial descrito anteriormente. Si previo no se movió, seguirá teniendo el valor None cuando la variable booleana encontrado se vuelva True. En ese caso (línea 13), la cabeza de la lista se modifica para referirse al nodo después del nodo actual, eliminando en efecto el primer nodo de la lista enlazada. Sin embargo, si previo no es None, el nodo que se va a quitar está en algún lugar de la estructura de la lista enlazada. En este caso la referencia previo nos proporciona el nodo cuya próxima referencia debe ser cambiada. La línea 15 utiliza el método asignarSiguiente de previo para realizar la eliminación. Note que en ambos casos el destino del cambio de referencia es actual.obtenerSiguiente(). Una pregunta que surge a menudo es si los dos casos mostrados aquí también considerarán la situación en la que el elemento que se va a eliminar está en el último nodo de la lista enlazada. Dejamos ese caso para que usted lo considere.

Pruebe la clase ListaNoOrdenada en el ActiveCode 1.

Los métodos restantes anexar, insertar, indice y extraer se dejan como ejercicios. Recuerde que cada uno de estos debe tener en cuenta si el cambio se lleva a cabo en la cabeza de la lista o en algún otro lugar. Además, insertar, indice y extraer requieren que nombremos las posiciones de la lista. Asumiremos que los nombres de las posiciones son números enteros que comienzan con 0.

Autoevaluación

Parte I: Implementar el método anexar para ListaNoOrdenada. ¿Cuál es la complejidad de tiempo del método que usted creó?

Parte II: En el problema anterior, usted probablemente creó un método anexar que era \(O(n)\). Si usted agrega una instancia a la clase ListaNoOrdenada puede crear un método anexar que sea \(O(1)\). Modifique su método anexar para que sea \(O(1)\) ¡Sea cuidadoso! Para realmente hacer esto correctamente tendrá que considerar un par de casos especiales que pueden requerir que usted realice también una modificación al método agregar.

Next Section - 3.22. El tipo abstracto de datos Lista Ordenada