Sebastian Gomez

Apr 07, 2023

Updated: Jun 24, 2026

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. Aprenderás qué son las listas doblemente enlazadas, cómo implementarlas en Go y cómo aplicarlas en diferentes casos prácticos. Vamos a empezar.

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

Un poco de contexto

Las listas doblemente enlazadas han sido una parte integral de la informática desde sus inicios. Son una estructura fundamental que se ha usado desde los primeros días de la computación y, desde entonces, 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í tienes 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.
3. Implementación de algoritmos avanzados, como el algoritmo de Dijkstra para encontrar el camino más corto en un grafo ponderado.
4. Manejo de memoria en sistemas operativos, donde las listas doblemente enlazadas facilitan la asignación y liberación eficiente de recursos.
5. 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.

Métodos 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. Observa que protegemos el caso de la lista vacía, así insertar en la posición 0 de una lista vacía no provoca un panic y además actualiza la cola.

func (list *DoublyLinkedList) InsertAt(value int, position int) error {
	if position < 0 {
		return fmt.Errorf("posición inválida")
	}

	newNode := &Node{data: value, prev: nil, next: nil}
	current := list.head
	index := 0

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

		if current == nil {
			return fmt.Errorf("posición fuera de rango")
		}

		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("posición inválida o lista vacía")
	}

	current := list.head
	index := 0

	if 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("posición fuera de rango")
		}

		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 alcanza el final.

func (list *DoublyLinkedList) 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("índice inválido")
	}

	current := list.head
	count := 0

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

	if current == nil {
		return nil, fmt.Errorf("índice fuera de rango")
	}

	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, al terminar, intercambia la cabeza y la cola de la lista. Esa última línea es la clave: como ya volteamos todos los punteros internos, basta con permutar head y tail para que la lista quede correctamente invertida.

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

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

	list.head, list.tail = list.tail, list.head
}

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. Cuando termines, envíes la solución como un Pull request 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.

Nota: verifica que la URL del repositorio de ejercicios siga resolviendo antes de publicar, ya que en el texto original solo aparecía el nombre del enlace y no la dirección. verify

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. Este post forma parte de una serie sobre Go, así que te invito a revisar los demás artículos para seguir profundizando.

Eso es todo, espero que este post te sea de utilidad y lo puedas aplicar a algún proyecto que tengas en mente. Déjame un comentario si te sirvió, si quieres añadir alguna opinión o si tienes alguna duda. Y recuerda que si te gustó, también puedes compartirlo usando los links a las redes sociales aquí abajo. Buena suerte en tu viaje de aprendizaje.