Estructura de Datos - Linked List (Lista Enlazada)

Hola a todos, estaré haciendo una serie de post, donde les voy a hablar sobre las estructuras de datos como por ejemplo Linked List, Stack & Queue, Binary Tree, Graph, Heap y explicando algunas operaciones y ejercicios.

Este es el primer post veremos Linked List, conceptos fundamentales y algunas operaciones =).

Conceptos principales

Linked List son estructuras de datos lineales, donde sus elementos no están almacenados en bloques continuos de memoria, a diferencia de los array, que estos son almacenados de bloques continuos de memoria, para entender mucho mejor vea la siguiente imagen.

Mientras que las Linked List son almacenadas en diferentes sectores de la memoria y hace referencia a sus elementos mediantes punteros.

Que diferencia una Linked List de un Array

No tiene un tamaño fijo, si conoces otros lenguajes como Java o **C++ sabrás que al momento de crear un array debes indicar el tamaño del mismo, pero si viene con un background solo de lenguajes dinámicos como Javascript o Python esto es totalmente transparente para usted.
Agregar elementos y remover de un array son operaciones costosas, ya que se debe crear un nuevo array y luego organizar los elementos o solo reorganizar los elementos si la operación fue remover, mientra que las Linked Lists es más fácil este proceso.

Ventajas

Tamaño dinámico.
Fácil realizar procesos como agregar o remover.

Desventajas

Acceso random no está permitido, si usted quiere poder acceder a un elemento como lo hace con los array esto no es posible, usted debe iniciar desde el nodo root e iterar por cada uno de los elementos hasta encontrar el valor que desea.
Se tiene un espacio de memoria extra para los punteros de cada uno de los elementos.
No es amigable con la cache, en los array los elementos son almacenados en continuos bloques de memoria y el acceso de cada uno de ellos son obtenidos mediante un cálculo matemático address calculation in an array.

Tipos de Linked Lists

Simple Linked List (Lista Enlazada Simple). La navegación siempre es hacia adelante.

Doubly Linked List (Lista Enlazada Doble). La navegación puede ser hacia adelante o hacia atrás.

Circular Linked List (Lista Enlazada Circular). En el primer elemento tiene un puntero que apunta al elemento final y elemento final apunta al primero. Esto se traduciría en un bucle infinito, también se puede combinar con las anteriores.

Uso de las Linked List

Les dejo los siguientes links para profundizar más sobre este aspecto.

Bueno creo que eso fue mucha información, espero no haberte abrumado o aburrido =). Ok veamos algo de código, los siguientes ejemplos serán implementados en Kotlin, usted puede llevar este ejemplo al lenguaje de su preferencia.

Ejemplo de codigo (Kotlin)

Primero crearemos una class Node el cual hara referencia a cada uno de los elementos en la Linked List.



class Node (var value: String, var next: Node? = null)

El siguiente paso es crear una clase que se encargue de gestionar las operaciones como agregar, remover, etc. El cual le llamaremos MyLinkedList.



class MyLinkedList(var root: Node? = null) {
    fun add(value: String) {
        // nuevo nodo a crear
        val node = Node(value)

        // validar que el nodo padre no este vacio
        if (root == null) {
            root = node
            return
        }

        // agregar elemento al final de la lista
        var e = this.root
        while (e?.next != null) {
            e = e?.next
        }

        e?.next = node
    }

    fun unShift(value: String) {
        // agregar elemento al inicio
        // nuevo nodo a crear
        val node = Node(value)

        // agregar el nuevo nodo si el root esta vacio
        if (this.root == null) {
            this.root = node
        } else {
            // asignar el nuevo nodo como root
            node.next = this.root
            this.root = node
        }
    }

    fun remove(value: String): Boolean {
        // para remover un elemento siempre hay ubicarse
        // en elemento anterior
        var prev: Node? = null
        var current = this.root

        // eliminar el nodo root
        if (current?.value == value) {
            this.root = this.root?.next
            return true
        }

        // buscar el nodo con el valor a eliminar y mantener el nodo anterior
        while (current != null && current?.value != value) {
            prev = current
            current = current.next
        }

        // verificar si el nodo a eliminar existe
        if (current == null) return false

        prev?.next = current.next

        return true
    }

    fun printValues() {
        var e = this.root
        while (e != null) {
            println(e.value)
            e = e.next
        }
    }
}



fun main() {
    val myLinkedList = MyLinkedList()
    myLinkedList.add("Kotlin")
    myLinkedList.add("Javascript")
    myLinkedList.add("Python")
    myLinkedList.unShift("Java")
    myLinkedList.remove("Javascript")

    myLinkedList.printValues()
}

Estos son ejemplos sencillos para poder introducirse en las Linked List. Existe operaciones más avanzadas que podemos realizar y podemos profundizar en otro post. Si está interesado en profundizar más, vea el final de post para consultar los recursos.

Si quiere usar una Linked List en Kotlin no es necesario crearla usted mismo, puede usar la clase nativa de Java.



import java.util.*

fun main() {
    val linkedList = LinkedList<String>()
    linkedList.add("Kotlin")
    linkedList.add("Java")


    val iterator: Iterator<String> = linkedList.iterator()
    while (iterator.hasNext()) {
        println(iterator.next())
    }
}

Mis recomendaciones para poder entender más las estructuras de datos es practicar, intente buscar ejercicios en páginas como Hackerrank, Leetcode.com o Geeksforgeeks donde puede consultar ejemplos y resolver ejercicios referentes a cada sección. Existe muchas páginas de este estilo no importa cual use lo importante es practicar.

Espero que les halla gustado este post, si tiene alguna sugerencia o corrección no dude es escribirme =).

Blog

Estructura de Datos - Linked List (Lista Enlazada)

Ronny Medina