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 =).
Top comments (2)
Hola está simple y claro pero quería consultar he visto que existe también otro tipo de lista que el la lista circular doblemente enlazada creo q faltó incluirla dentro de las 3 ya expuestas
Excelente explicación, me queda mucho más claro, ya queda poner en práctica.