Estructuras de Datos – Lista Enlazada

Get real time updates directly on you device, subscribe now.

Hoy abordaremos un nuevo algoritmo, aprenderemos a implementar una Lista Enlazada, una estructura de datos bien importante y de las más usadas. Pudiéramos clasificarla como clásica ya que forma parte de esas estructuras de datos que todo iOS Developer debe conocer, de hecho, con estas podemos implementar otras estructuras de datos.

[anuncio_b30 id=1]

Según Wikipedia:

“Consiste en una secuencia de nodos, en los que se guardan campos de datos arbitrarios y una o dos referencias, enlaces o punteros al nodo anterior o posterior. El principal beneficio de las listas enlazadas respecto a los vectores convencionales es que el orden de los elementos enlazados puede ser diferente al orden de almacenamiento en la memoria o el disco, permitiendo que el orden de recorrido de la lista sea diferente al de almacenamiento.”

Pero no te abrumes con esta explicación, vamos a crear nuestra propia definición poco a poco y mediante ejemplos. Comencemos por decir que una Lista Enlazada es una secuencia de elementos donde, a cada uno de estos se les llama nodos. Al mismo tiempo también existen diferentes tipos de listas enlazadas: listas enlazadas simples o de un solo enlace, listas doblemente enlazadas, listas enlazadas circulares y listas enlazadas doblemente circulares, aunque las más importantes o más usadas son las listas simples y las doblemente enlazadas:

Listas simples: Son aquellas donde cada nodo solamente cuenta con una referencia o enlace hacia el nodo siguiente.

Lista Enlazada Simple

Listas doblemente enlazadas: Son aquellas donde cada nodo cuenta con una referencia o enlace hacia el nodo anterior y otra hacia el siguiente.

Lista Doblemente Enlazada

También tenemos que llevar un registro de donde comienza y termina la lista, esto se logra con punteros a los que se les nombra como head (cabeza) para señalizar el inicio y tail (cola de perro / de dragón) para el final.

Lista Doblemente Enlazada - Head y Tail

Como podemos constatar en la imagen en el primer nodo el puntero Head apunta a este mientras que el Tail se establece a nil y en el último nodo el Head se iguala a nil mientras que el Tail apunta hacia este nodo.

[anuncio_b30 id=2]

En este artículo abordaremos las listas doblemente enlazadas ya que al ser más complejas que las simples usualmente son las que más interés generan. Espero que esto no desanime a ningún lector, ya que luego de leer y comprender este artículo seremos capaces de crear una lista enlazada simple sin problema alguno.

Implementando una Lista Enlazada

Como una Lista Enlazada está conformada por nodos, comenzaremos por crear la clase Node:

public class Node {


} // Node

Una estructura de datos necesita datos y los nodos de una lista representan esos datos así que añadimos ahora el valor que almacenará cada nodo:

public class Node {
    
    var value: String
    
    init(value: String) {
        
        self.value = value
    
    } // init
    
} // Node

Hemos creado una propiedad llamada value de tipo String. También declaramos un inicializador el cual es requerido en pos de inicializar todas las propiedades no opcionales de nuestra clase.

También necesitamos en cada nodo una referencia al nodo siguiente y al anterior:

public class Node {
    
    var value: String
    
    var next: Node?
    
    weak var previous: Node?
    
    init(value: String) {
        
        self.value = value
    
    } // init
    
} // Node

La clase Node va tomando forma, en las líneas 5 y 7 añadimos dos propiedades de tipo Node ya que evidentemente estas referencian a otros nodos en nuestra lista. Notemos que ambas son opcionales ya que como explicamos anteriormente, tanto al inicio como al final una de estas adoptan el valor nil. Importante comentar que la propiedad previous la hemos marcado como weak para evitar ciclos de referencias fuerte y con esto asegurar que la memoria asignada a cada nodo sea liberada correctamente.

Si deseas aprender más sobre la palabra clave weak te recomiendo nuestro artículo sobre el manejo de memoria en el lenguaje de programación Swift.

Ahora prosigamos creando la clase que representará a nuestra Lista Enlazada:

public class LinkedList {
    
    fileprivate var head: Node?
    
    private var tail: Node?

    public private(set) var count: Int = 0
    
    public var isEmpty: Bool {
        
        return head == nil
    
    } // isEmpty
    
    public var first: Node? {
        
        return head
    
    } // first
    
    public var last: Node? {
        
        return tail
    
    } // last
    
} // LinkedList

Esta clase llevará el registro de donde comienza y termina la lista, al igual que otras funciones que nos ayudarán a conocer si está vacía o con cuantos elementos cuenta esta lista doblemente enlazada. Una funcionalidad que también vamos a necesitar será la de añadir un nuevo nodo a la lista:

public func append(value: String) {

    let newNode = Node(value: value)

    if let tailNode = tail {
            
        newNode.previous = tailNode
            
        tailNode.next = newNode
            
    } else {
            
        head = newNode
            
    } // else

    tail = newNode

    count += 1
        
} // append

…y para esto crearemos una función de nombre append en la clase LinkedList.

En esta función recibimos como parámetro el nuevo valor que procederemos a convertir en un nuevo nodo y recordemos que la razón de ser de los nodos es que podamos encadenar un valor en nuestra lista de elementos. En la línea 5 verificamos que tailNode no sea nil en cuyo caso la lista ya contendría otros elementos y tendríamos que hacer que el nuevo nodo apunte a la cola de la lista y a su elemento previo, tal y como hemos hecho en las líneas 7 y 9. Por último y en cualquiera de los casos establecemos que la cola de la lista sea el nuevo nodo y aumentamos en una unidad el contador de elementos en la lista.

Imprimiendo la Lista Enlazada

Creo conveniente añadir la posibilidad de imprimir la lista no con un enfoque pleno en esta característica ya que en una aplicación real la manera en la que se imprimen o se muestran los datos en pantalla pueden variar mucho, mi intención es plenamente con fines didácticos y depuración.

[anuncio_b30 id=3]

Para lograr lo antes comentado adoptaremos el protocolo CustomStringConvertible el cual ya hemos visto en otros artículos y que nos obliga a implementar una propiedad computada de tipo String y de nombre description:

extension LinkedList: CustomStringConvertible {

    public var description: String {

        var text = "["
        var node = first

        while node != nil {
            
            text += "\(node!.value)"
            
            node = node!.next
            
            if node != nil {
                
                text += ", "
            
            } // if
            
        } // while

        return text + "]"
        
    } // description
    
} // LinkedList Extension

Lo primero que destaco del código es que hemos extendido la clase en pos de añadir la nueva funcionalidad. El motivo principal reside en que el modelo de datos de una aplicación real jamás imprimirá directamente en pantalla, por no mencionar que cada aplicación muestra los datos de maneras bien distintas. El enfoque correcto sería extender la clase y así añadimos nuestro propio formato, como acabamos de hacer. Hemos declarado una variable de nombre text la cual almacenará la cadena que nos disponemos a crear, en un inicio solamente almacena un corchete abierto ([) que es lo que da inicio a la cadena de texto. Luego de la línea 8 a la 20 iteramos sobre la lista agregando los valores de cada nodo a la cadena de texto y finalizamos en la línea 22 agregando el corchete cerrado (]).

Para probar que todo está funcionando correctamente agregaremos las siguientes líneas de código:

let dogBreeds = LinkedList()

dogBreeds.append(value: "Labrador")
dogBreeds.append(value: "Bulldog")
dogBreeds.append(value: "Beagle")
dogBreeds.append(value: "Husky")

print(dogBreeds)

…la salida en pantalla:

[Labrador, Bulldog, Beagle, Husky]

Accediendo a los Nodos

Aún cuando una lista enlazada funciona más eficiente cuando nos movemos en orden a través de los nodos haciendo uso de previous y next, en algunas ocasiones es oportuno acceder a un elemento haciendo uso de un índice.

Para lograr esto declararemos la función nodeAt(index:) la cual retornará el nodo asociado al índice específico:

public func nodeAt(index: Int) -> Node? {

    if index >= 0 {
            
        var node = head
            
        var i = index

        while node != nil {
                
            if i == 0 {
                    
                return node
                
            } // if
                
            i -= 1
                
            node = node!.next
                
        } // while
            
    } // if

    return nil
        
} // nodeAt

Esta función recibe un valor entero y lo primero que hacemos con este en la línea 3 es verificar que no sea negativo. En la siguiente línea creamos una variable que almacena el primer nodo en la lista y seguido a esto creamos otra variable que igualamos al valor pasado como parámetro a la función. De la línea 9 a la 21 tenemos un bucle de tipo while que toma como expresión de control node != nil, es decir mientras la variable node tenga asociado un valor el bucle continuará ejecutando el código que hemos definido dentro de él.  Lo primero que hacemos dentro del bucle es verificar si el índice solicitado es 0 ya que, de ser así, retornamos la variable node, recordemos que al definir var node = head estamos creando una referencia al primer elemento de la lista, el cual se encuentra en el indice 0, por lo que siendo este el caso ya tenemos el nodo correspondiente a ese índice y no tiene sentido continuar con el bucle. En la línea 17 restamos en uno a la variable i que funge de temporal para el valor del índice y esto lo hacemos con el objetivo de sincronizar este valor con el aumento del índice de la lista, ya que cuando se ejecuta la línea 19 la variable node ya no se encuentra apuntando al primer elemento de la lista y por ende el índice pasó de 0 a 1 y así van evolucionando ambos valores, mientras el índice de la lista aumenta, el valor de i disminuye  hasta llegar a 0, momento donde se retorna el nodo asociado o nil en caso de que se haya llegado al final de la lista.

En la siguiente tabla se puede visualizar mejor el proceso. Hemos asumido que el valor inicial de index es 3 y como node es igual a head pues su valor inicial es 0:

Variables Valores Iniciales Fin Primer Ciclo Fin Segundo Ciclo Fin Tercer Ciclo Inicio Cuarto Ciclo
i 3 2 1 0 i == 0
node 0 1 2 3 return node

Llegado el inicio del cuarto ciclo y final, la variable i es igual a 0 y acto seguido se ejecuta la línea 13 donde retornamos el nodo asociado al índice 3.

Para comprobar que nuestra función trabaja de la manera que hemos previsto, modifiquemos el siguiente código:

let dogBreeds = LinkedList()

dogBreeds.append(value: "Labrador")
dogBreeds.append(value: "Bulldog")
dogBreeds.append(value: "Beagle")
dogBreeds.append(value: "Husky")

print(dogBreeds)

print(dogBreeds.nodeAt(index: 3)!)

…agregándole la última línea. La salida en pantalla será:

[Labrador, Bulldog, Beagle, Husky]
LinkedList_Sources.Node

La primera línea tiene el formato que habíamos creado sin embargo la segunda no. La razón es evidente, cuando trabajamos el formato de salida lo hicimos sobre la clase LinkedList y en la línea 10 estamos imprimiendo una instancia de Node. La solución es la que seguramente ya han imaginado, tenemos que extender la clase Node para que también adopte el protocolo CustomStringConvertible:

extension Node: CustomStringConvertible {
    
    public var description: String {
        
        return String("[\(value)]")
        
    } // description
    
} // Node Extension

Cuando se vuelve a ejecutar todo el código, la salida en pantalla ya se muestra con el formato correcto:

[Labrador, Bulldog, Beagle, Husky]
[Husky]

Si ahora deseamos que nos devuelva el nodo correspondiente al indice 1:

print(dogBreeds.nodeAt(index: 1)!)

…la salida cambia a la siguiente:

[Labrador, Bulldog, Beagle, Husky]
[Bulldog]

¿Pero que sucedería si pasamos un índice negativo?

Pues obtendríamos el siguiente mensaje de error:

fatal error: unexpectedly found nil while unwrapping an Optional value

…básicamente debido a que no podemos desempaquetar al valor nil. Una solución elegante y rápida para nuestro ejemplo pudiera ser el uso del operador de coalescencia nula:

print(dogBreeds.nodeAt(index: -1) ?? "ERROR: Negative index makes no sense.")

…y la salida en pantalla sería:

[Labrador, Bulldog, Beagle, Husky]
ERROR: Negative index makes no sense.

En el siguiente artículo puedes aprender más sobre: el operador de coalescencia nula y los valores opcionales.

Eliminando Todos los Nodos

Otra funcionalidad que debe tener una lista enlazada es la posibilidad de poder remover todos los elementos que la conforman, una especie de reset que vacíe la lista y la vuelva a su estado inicial. En el siguiente código implementamos la función removeAll():

public func removeAll() {
        
    head = nil
    tail = nil

    count = 0
    
} // removeAll

Como pueden ver es bastante simple de lograr, basta con igualar a nil tanto la cabeza como la cola de la lista. Podemos probarlo haciendo:

print(dogBreeds)

dogBreeds.removeAll()

print(dogBreeds)

print(dogBreeds.count)

…la salida sería:

[Labrador, Bulldog, Beagle, Husky]
[]
0

Ya la lista la tenemos vacía pero vamos a darle un pequeño ajuste para obtener una mejor salida en momentos como estos:

extension LinkedList: CustomStringConvertible {

    public var description: String {
        
        if isEmpty {
        
            return String("[Empty List]")
            
        } // if

        var text = "["
        var node = first

        while node != nil {
            
            text += "\(node!.value)"
            
            node = node!.next
            
            if node != nil {
                
                text += ", "
            
            } // if
            
        } // while

        return text + "]"
        
    } // description
    
} // LinkedList Extension

…y ahora la salida es:

[Labrador, Bulldog, Beagle, Husky]
[Empty List]
0

Eliminando Nodos Individuales

Cuando se nos presenta la necesidad de eliminar nodos individuales nos vemos ante tres casos:

1 – Remover el primer nodo, en este caso tenemos que actualizar las referencias head y previous sobre el nodo siguiente.

Lista Enlazada - Eliminando Primero

2 – Remover un nodo dentro de la lista, en este caso tenemos que actualizar las referencias previous del nodo siguiente y next del nodo anterior.

Lista Enlazada - Eliminando Intermedio

3 – Remover al último nodo, en este caso tenemos que actualizar las referencias next y tail sobre el nodo anterior.

Lista Enlazada - Eliminando Último

Teniendo en cuenta esto, prosigamos a crear una nueva función de nombre remove:

public func remove(node: Node?) -> String {
        
        if isEmpty {
            
            return String("ERROR: Empty list, nothing to remove.")
            
        } // if

        guard node != nil else {
            
           return String("ERROR: Invalid node, nothing to remove.")
            
        } // guard

        let prev = node?.previous
        let next = node?.next
        
        if next != nil && prev == nil {
            
            // Caso 1
            
            head = next
            
            next?.previous = nil
            
        } else if next != nil && prev != nil {
            
            // Caso 2

            prev?.next = next
            
            next?.previous = prev

        } else if next == nil && prev != nil {
            
            // Caso 3

            tail = prev
            
            prev?.next = nil
            
        } // if

        node?.previous = nil
        node?.next = nil

        count -= 1
        
        return String("Successfully removed node: \(node!.value)")
        
    } // remove
    
} // LinkedList

…en la cual contemplaremos cada uno de estos casos tal y como hemos marcado en el código mediante comentarios. Lo primero que hacemos es verificar que la lista no este vacía ya que no tiene sentido eliminar algo cuando no hay nada, lo segundo es asegurarnos de que el nodo pasado como parámetro es válido y en cualquiera de estos dos casos retornamos un mensaje de error correspondiente. El resto del código creo que se explica mejor con las imágenes asociadas a cada caso en la lista de arriba no obstante si tiene alguna duda en los comentarios la pueden dejar y con gusto la respondo. Por último en las líneas 44 y 45 las referencias que atan a nuestro nodo con la lista se liberan igualándolas a nil, luego al no haber más referencias a esta posición de memoria pues ARC toma el control y la libera.

En el siguiente tutorial podrás profundizar más sobre: ARC (Automatic Reference Counting) y la gestión de memoria.

Genéricos

Hasta ahora hemos implementado una lista con soporte solamente para valores de tipo String y esto nos limita grandemente por razones más que evidentes. La solución reside en el uso de código genérico, veamos:

public class Node<T> {
    
    var value: T
    
    var next: Node<T>?
    
    weak var previous: Node<T>?
    
    init(value: T) {
        
        self.value = value
        
    } // init
    
} // Node

Como ya sabemos la clase Node se encarga de almacenar los valores de nuestra lista, fungiendo como los eslabones de una cadena y al mismo tiempo como las cabinas de un teleférico que solamente permite montar solamente a mujeres, siendo estas últimas el tipo String al que hemos dado soporte hasta ahora. En la nueva versión de Node ya podemos manejar todo tipo de valores, es decir las cabinas ya permiten montar junto a las mujeres todo tipo de personas y animales: hombres, niños, perritos, gaticos… etc.

Lo siguiente es modificar la clase LinkedList ya que al trabajar internamente con la clase Node no se abstrae del tipo de datos que estamos almacenando:

public class LinkedList<T> {
    
    private var head: Node<T>?
    
    private var tail: Node<T>?

    public private(set) var count: Int = 0
    
    public init() { } // init
    
    public var isEmpty: Bool {
        
        return head == nil
    
    } // isEmpty
    
    public var first: Node<T>? {
        
        return head
    
    } // first
    
    public var last: Node<T>? {
        
        return tail
    
    } // last
    
    public func append(value: T) {

        let newNode = Node(value: value)

        if let tailNode = tail {
            
            newNode.previous = tailNode
            
            tailNode.next = newNode
            
        } else {
            
            head = newNode
            
        } // else

        tail = newNode

        count += 1
        
    } // append
    
    public func nodeAt(index: Int) -> Node<T>? {

        if index >= 0 {
            
            var node = head
            
            var i = index

            while node != nil {
                
                if i == 0 {
                    
                    return node
                
                } // if
                
                i -= 1
                
                node = node!.next
                
            } // while
            
        } // if

        return nil
        
    } // nodeAt
    
    public func removeAll() {
        
        head = nil
        tail = nil

        count = 0
    
    } // removeAll
    
    public func remove(node: Node<T>?) -> String {
        
        if isEmpty {
            
            return String("ERROR: Empty list, nothing to remove.")
            
        } // if

        guard node != nil else {
            
           return String("ERROR: Invalid node, nothing to remove.")
            
        } // guard

        let prev = node?.previous
        let next = node?.next
        
        if next != nil && prev == nil {
            
            // Caso 1
            
            head = next
            
            next?.previous = nil
            
        } else if next != nil && prev != nil {
            
            // Caso 2

            prev?.next = next
            
            next?.previous = prev

        } else if next == nil && prev != nil {
            
            // Caso 3

            tail = prev
            
            prev?.next = nil
            
        } // if

        node?.previous = nil
        node?.next = nil

        count -= 1
        
        return String("Successfully removed node: \(node!.value)")
        
    } // remove
    
} // LinkedList

En este punto ya nuestro código compila nuevamente y podemos tratar varios tipos de datos. Veamos un ejemplo:

let dogBreeds = LinkedList<String>()

dogBreeds.append(value: "Labrador")
dogBreeds.append(value: "Bulldog")
dogBreeds.append(value: "Beagle")
dogBreeds.append(value: "Husky")

print(dogBreeds)

let someIntValues = LinkedList<Int>()

someIntValues.append(value: 10)
someIntValues.append(value: 20)
someIntValues.append(value: 30)
someIntValues.append(value: 40)

print(someIntValues)

let someDoubleValues = LinkedList<Double>()

someDoubleValues.append(value: 10.5)
someDoubleValues.append(value: 13.56)
someDoubleValues.append(value: 3.0)
someDoubleValues.append(value: 400.23)

print(someDoubleValues)

La salida en pantalla de este código sería:

[Labrador, Bulldog, Beagle, Husky]
[10, 20, 30, 40]
[10.5, 13.56, 3.0, 400.23]

Si te preguntas por las extensiones pues no he hablado de ellas en este segmento debido a que no necesitamos modificarlas, el código que habíamos implementado es compatible con los cambios implementados.

No he explicado en detalles los últimos cambios de esta sección ya que es un tema que se ha abordado en otro artículos, si deseas aprender más te exhorto a que visites nuestro tutorial sobre el aprendizaje de genéricos en el lenguaje de programación Swift.

Resumen

Como muchas veces ocurre en el desarrollo de software, no existe un único método correcto para resolver un problema. Una estructura de lista enlazada puede trabajar bien en un caso pero causar problemas en otros. En general, el beneficio de las listas enlazadas se incrementa cuando trabajamos con una colección dinámica en la cual añadimos y eliminamos nodos de manera frecuente y donde la localización de los nuevos elementos introducidos, importa.

Como ya hemos comentado esta estructura de datos es de las clásicas, una más de las tantas que como iOS Developer necesitamos saber implementar o mejor aún, entender la tesis detrás de su puesta en práctica, comprendiendo la teoría, seremos capaces de implementarla, no solamente en Swift, sino en cualquier otro lenguaje. En KodigoSwift hemos abordado varias estructuras de datos, igual de importantes, que te invitamos a conocer en la sección de algoritmos de programación en Swift.

Falta aún mucho por aprender en nuestro camino a convertirnos en iOS Developer. Suscríbete a nuestra lista de correo mediante el formulario en el panel derecho y síguenos en nuestras redes sociales. Mantente así al tanto de todas nuestras publicaciones futuras.

Espero que todo cuanto se ha dicho aquí, de una forma u otra le haya servido de aprendizaje, de referencia, que haya valido su preciado tiempo.

Este artículo, al igual que el resto, será revisado con cierta frecuencia en pos de mantener un contenido de calidad y actualizado.

Cualquier sugerencia, ya sea errores a corregir, información o ejemplos a añadir será, más que bienvenida, necesaria!

Get real time updates directly on you device, subscribe now.

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Accept Read More

RECIBE CONTENIDO SIMILAR EN TU CORREO

RECIBE CONTENIDO SIMILAR EN TU CORREO

Suscríbete a nuestra lista de correo y mantente actualizado con las nuevas publicaciones.

Se ha suscrito correctamente!