Estructuras de datos en Go: Listas Doblemente Enlazadas

En este post vamos a explorar las listas doblemente enlazadas en Go, una estructura de datos increíblemente útil y versátil. En este artículo, aprenderás qué son las listas doblemente enlazadas, cómo implementarlas en Go y cómo aplicarlas en diferentes casos prácticos. 📚👩‍💻👨‍💻

🧩 ¿Qué son las listas doblemente enlazadas?

Las listas doblemente enlazadas son una estructura de datos lineal similar a las listas enlazadas simples, pero con una diferencia clave: cada nodo en una lista doblemente enlazada contiene dos punteros 🎯, uno al siguiente nodo y otro al nodo anterior. Esto permite recorrer la lista en ambas direcciones, lo que facilita la implementación de ciertas operaciones y mejora la eficiencia en algunos casos.

📜 Historia de las listas doblemente enlazadas

Las listas doblemente enlazadas han sido una parte integral de la informática desde sus inicios. Su concepto fue introducido por primera vez en la década de 1960 por Peter L. Weiner, quien las llamó "listas de doble enlace". Desde entonces, estas listas han sido aplicadas en una amplia variedad de algoritmos y aplicaciones, desde sistemas operativos hasta navegadores web. 🌐

🛠 Implementación de listas doblemente enlazadas en Go

Veamos un ejemplo básico de cómo implementar una lista doblemente enlazada en Go. 🤓

package main

import "fmt"type Node struct {
	data int
	prev *Node
	next *Node
}

type DoublyLinkedList struct {
	head *Node
	tail *Node
}

func (list *DoublyLinkedList) Append(value int) {
	newNode := &Node{data: value, prev: nil, next: nil}

	if list.head == nil {
		list.head = newNode
		list.tail = newNode
	} else {
		newNode.prev = list.tail
		list.tail.next = newNode
		list.tail = newNode
	}
}

func (list *DoublyLinkedList) Print() {
	current := list.head
	for current != nil {
		fmt.Printf("%d ", current.data)
		current = current.next
	}
	fmt.Println()
}

func main() {
	list := DoublyLinkedList{}

	list.Append(1)
	list.Append(2)
	list.Append(3)
	list.Append(4)

	fmt.Println("Lista doblemente enlazada:")
	list.Print()
}

Esta implementación básica incluye una estructura Node con punteros prev y next, así como una estructura DoublyLinkedList con punteros head y tail. El método Append() permite agregar elementos al final de la lista y el método Print() imprime los elementos de la lista.

📝 Ejemplos de uso de las listas doblemente enlazadas

Las listas doblemente enlazadas son ideales para una amplia variedad de aplicaciones. Aquí hay algunas situaciones en las que podrías utilizarlas:

1. Navegadores web para implementar el historial de navegación, donde los usuarios pueden moverse hacia adelante y hacia atrás entre las páginas visitadas. 🌐 2. Sistemas de edición de texto o imágenes que permiten funciones de deshacer y rehacer, almacenando acciones en una estructura fácilmente navegable en ambas direcciones. 📝🎨

2. Implementación de algoritmos avanzados, como el algoritmo de Dijkstra para encontrar el camino más corto en un grafo ponderado. 🚗🗺️

3. Manejo de memoria en sistemas operativos, donde las listas doblemente enlazadas facilitan la asignación y liberación eficiente de recursos. 💻🔋

4. Almacenar y administrar listas de reproducción en aplicaciones multimedia, donde los usuarios pueden navegar fácilmente hacia adelante y hacia atrás a través de canciones o videos. 🎵📺

📝 Metodos de las listas doblemente enlazadas

Las listas doblemente enlazadas en Go, como en otros lenguajes de programación, tienen varios métodos comunes que se utilizan para manipular y trabajar con la estructura de datos. A continuación, se presentan algunos de los métodos más comunes y su explicación:

Append: Este método se utiliza para agregar un elemento al final de la lista doblemente enlazada. Crea un nuevo nodo con el valor proporcionado, establece sus punteros prev y next correctamente y actualiza la cola de la lista.

func (list *DoublyLinkedList) Append(value int) {
    newNode := &Node{data: value, prev: nil, next: nil}

    if list.head == nil {
        list.head = newNode
        list.tail = newNode
    } else {
        newNode.prev = list.tail
        list.tail.next = newNode
        list.tail = newNode
    }
}

InsertAt: Este método inserta un elemento en una posición específica de la lista doblemente enlazada. Crea un nuevo nodo con el valor proporcionado y ajusta los punteros prev y next de los nodos adyacentes.

func (list *DoublyLinkedList) InsertAt(value int, position int) error {
    if position < 0 {
        return fmt.Errorf("Invalid position")
    }

    newNode := &Node{data: value, prev: nil, next: nil}
    current := list.head
    index := 0if position == 0 {
        newNode.next = list.head
        list.head.prev = newNode
        list.head = newNode
    } else {
        for current != nil && index < position-1 {
            current = current.next
            index++
        }

        if current == nil {
            return fmt.Errorf("Position out of range")
        }

        newNode.prev = current
        newNode.next = current.next
        current.next = newNode

        if newNode.next != nil {
            newNode.next.prev = newNode
        } else {
            list.tail = newNode
        }
    }

    return nil
}

RemoveAt: Este método elimina un elemento de la lista doblemente enlazada en una posición específica. Encuentra el nodo en la posición indicada y ajusta los punteros prev y next de los nodos adyacentes antes de eliminar el nodo.

func (list *DoublyLinkedList) RemoveAt(position int) error {
    if position < 0 || list.head == nil {
        return fmt.Errorf("Invalid position or empty list")
    }

    current := list.head
    index := 0if position == 0 {
        list.head = current.next
        if list.head != nil {
            list.head.prev = nil
        } else {
            list.tail = nil
        }
    } else {
        for current != nil && index < position {
            current = current.next
            index++
        }

        if current == nil {
            return fmt.Errorf("Position out of range")
        }

        current.prev.next = current.next
        if current.next != nil {
            current.next.prev = current.prev
        } else {
            list.tail = current.prev
        }
    }

    return nil
}

Size: Este método devuelve el número de elementos en la lista doblemente enlazada. Recorre la lista y cuenta los nodos hasta que se alcance el final de la lista.

func (list *Doubly LinkedList) Size() int {
count := 0
current := list.head
for current != nil {
    count++
    current = current.next
}

return count
}

Get: Este método devuelve un puntero al nodo en el índice especificado de la lista doblemente enlazada. Recorre la lista hasta encontrar el nodo en la posición requerida.

func (list *DoublyLinkedList) Get(index int) (*Node, error) {
    if index < 0 {
        return nil, fmt.Errorf("Invalid index")
    }

    current := list.head
    count := 0

    for current != nil && count < index {
        current = current.next
        count++
    }

    if current == nil {
        return nil, fmt.Errorf("Index out of range")
    }

    return current, nil
}

Reverse: Este método invierte el orden de los elementos en la lista doblemente enlazada. Intercambia los punteros prev y next de cada nodo y actualiza la cabeza y la cola de la lista.

func (list *DoublyLinkedList) Reverse() {
    current := list.head
    var temp *Node

    for current != nil {
        temp = current.prev
        current.prev = current.next
        current.next = temp
        current = current.prev
    }

    if temp != nil {
        list.tail = list.head
        list.head = temp.prev
    }
}

Estos son algunos de los métodos más comunes utilizados al trabajar con listas doblemente enlazadas en Go. Implementar y entender estos métodos te permitirá manipular y gestionar listas doblemente enlazadas de manera eficiente en tus proyectos de programación.

🏋️‍♀️ Ejercicios para practicar listas doblemente enlazadas en Go

Aquí tienes algunos ejercicios para practicar y mejorar tus habilidades con las listas doblemente enlazadas en Go y envies la solucioón como un Pull requeste a este repositorio: 

Go Para Principiantes

1. Implementa un método InsertAt(value int, position int) para insertar un elemento en una posición específica de la lista.

2. Implementa un método RemoveAt(position int) para eliminar un elemento de la lista dado su índice.

3. Crea un método Size() que devuelva el número de elementos en la lista doblemente enlazada.

4. Implementa un método Get(index int) (*Node, error) que devuelva un puntero al nodo en el índice especificado.

5. Implementa un método Reverse() para invertir el orden de los elementos en la lista doblemente enlazada.

6. Crea un método RemoveDuplicates() que elimine los elementos duplicados de una lista doblemente enlazada.

7. Implementa un método FindMiddle() *Node que encuentre y devuelva un puntero al nodo del elemento central de la lista.

8. Crea un método HasCycle() bool para detectar ciclos en una lista doblemente enlazada.

9. Implementa un método SwapNodes(node1, node2 *Node) que intercambie dos nodos en una lista doblemente enlazada.

10. Crea un método Sort() para ordenar los elementos de la lista doblemente enlazada en orden ascendente o descendente.

¡No olvides probar tus implementaciones y experimentar con diferentes casos de uso para comprender mejor las listas doblemente enlazadas en Go! 🚀🔧

🌈 Conclusión

Las listas doblemente enlazadas son una herramienta poderosa y versátil en el mundo de la programación. Al dominar esta estructura de datos en Go, podrás abordar una amplia gama de problemas y aplicaciones de manera eficiente y elegante. 💡

Recuerda que, aunque las listas doblemente enlazadas son increíbles, es esencial elegir la estructura de datos adecuada para cada situación. ¡Sigue aprendiendo y explorando, y no dudes en sumergirte en otros temas como árboles, grafos y algoritmos! 🌳🌉

Te deseo mucho éxito en tu viaje de aprendizaje y espero que disfrutes descubriendo todas las posibilidades que las listas doblemente enlazadas y otras estructuras de datos tienen para ofrecer! 😊👩‍💻👨‍💻