Estructura de Datos - Linked List (Lista Enlazada)
Tags: beginners, kotlin, tutorial
Published: 2020-09-12 16:12:32

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.

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/wivagxkow49y436qdaaf.png)

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

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/e65b6pku9i7tstechfnz.jpeg)

### 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](http://www.guideforschool.com/625348-memory-address-calculation-in-an-array/).

### Tipos de **Linked Lists**
- Simple Linked List (Lista Enlazada Simple). La navegación siempre es hacia adelante.

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/rd4zeajh6dqnme4e3uhc.png)

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

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/bzt4m25cfowzraozktyk.png)

- 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.

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/iqj8io57z79ivydaoo84.png)

### Uso de las **Linked List**

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

- [https://www.geeksforgeeks.org/applications-of-linked-list-data-structure/](https://www.geeksforgeeks.org/applications-of-linked-list-data-structure/)

- [https://stackoverflow.com/questions/644167/what-is-a-practical-real-world-example-of-the-linked-list#:~:text=A%20linked%20list%20can%20be,the%20top%20of%20the%20stack.](https://stackoverflow.com/questions/644167/what-is-a-practical-real-world-example-of-the-linked-list#:~:text=A%20linked%20list%20can%20be,the%20top%20of%20the%20stack.)

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**.

```kotlin
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**.

```kotlin
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
        }
    }
}
```

```kotlin
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**.

```kotlin
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](https://www.hackerrank.com/), [Leetcode.com](https://leetcode.com/) o [Geeksforgeeks](https://www.geeksforgeeks.org/data-structures/linked-list/) 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 =).

### Recursos
- [https://www.geeksforgeeks.org/data-structures/linked-list/](https://www.geeksforgeeks.org/data-structures/linked-list/)
- [https://www.youtube.com/watch?v=NobHlGUjV3g&list=PL2_aWCzGMAwI3W_JlcBbtYTwiQSsOTa6P&index=3](https://www.youtube.com/watch?v=NobHlGUjV3g&list=PL2_aWCzGMAwI3W_JlcBbtYTwiQSsOTa6P&index=3)