Sebastian Gomez

Apr 06, 2023

Estructuras de datos en Go: Listas Enlazadas

Las listas enlazadas son una estructura de datos lineal y dinámica que se utiliza para almacenar y organizar información en una secuencia ordenada. A diferencia de los arrays y slices, las listas enlazadas no tienen un tamaño fijo, lo que significa que pueden crecer o disminuir según las necesidades de nuestro programa.

En este artículo, exploraremos el concepto de listas enlazadas y cómo implementarlas en Go, un lenguaje de programación de alto rendimiento y tipado estático desarrollado por Google.

Concepto de listas enlazadas:

Una lista enlazada consta de una serie de elementos, llamados nodos, que se conectan entre sí mediante punteros o referencias. Cada nodo contiene dos partes principales: el valor del dato almacenado y un puntero al siguiente nodo de la lista. El último nodo de la lista apunta a nil, lo que indica el final de la secuencia.

Existen varios tipos de listas enlazadas, como las listas enlazadas simples, las listas enlazadas dobles y las listas enlazadas circulares. La principal diferencia entre estos tipos radica en la forma en que los nodos están conectados entre sí.

1. Listas enlazadas simples: En estas listas, cada nodo tiene un puntero al siguiente nodo de la lista.
2. Listas enlazadas dobles: Cada nodo tiene un puntero al siguiente nodo y otro al nodo anterior, lo que facilita la navegación en ambas direcciones.
3. Listas enlazadas circulares: El último nodo de la lista apunta al primer nodo en lugar de nil, lo que crea un bucle circular.

Implementación de listas enlazadas en Go:

En Go, podemos implementar listas enlazadas utilizando estructuras personalizadas y punteros. A continuación se muestra un ejemplo básico de cómo implementar una lista enlazada simple en Go:

package main

type Node struct {
	data int
	next *Node
}

type LinkedList struct {
	head *Node
	size int
}

func main() {
	// Código para manipular la lista enlazada
}

En este ejemplo, hemos definido una estructura Node que contiene un campo data para almacenar el valor del dato y un campo next que apunta al siguiente nodo de la lista. Además, hemos creado una estructura LinkedList que contiene un puntero head al primer nodo de la lista y un campo size que mantiene el número de elementos en la lista.

A partir de esta implementación básica, podemos agregar métodos para manipular y gestionar nuestra lista enlazada, como insertar, eliminar y buscar elementos.

Historia de las listas enlazadas

Las listas enlazadas tienen una larga historia en el mundo de la informática y se remontan a los albores de la programación moderna. Su invención se atribuye a Allen Newell, Cliff Shaw y Herbert A. Simon, quienes desarrollaron la estructura de datos en la década de 1950 como parte de su trabajo en el proyecto RAND Corporation. Las listas enlazadas surgieron como una solución para superar las limitaciones de almacenamiento y manipulación de datos en las computadoras de la época, que contaban con memoria muy limitada y hardware de bajo rendimiento. Desde entonces, las listas enlazadas se han convertido en un pilar fundamental en la enseñanza y aplicación de algoritmos y estructuras de datos, siendo utilizadas en una amplia variedad de sistemas informáticos y lenguajes de programación.

Aplicaciones de las listas enlazadas

Las listas enlazadas son una estructura de datos versátil que se utiliza en diversos escenarios y aplicaciones. Algunos ejemplos de uso incluyen:

Manejo de memoria: Las listas enlazadas pueden ser útiles en la implementación de sistemas de gestión de memoria, como el mantenimiento de bloques de memoria libres en un sistema operativo, ya que permiten agregar y eliminar elementos de manera eficiente.

Implementación de otras estructuras de datos: Las listas enlazadas pueden utilizarse como base para construir estructuras de datos más complejas, como pilas, colas, colas de prioridad y árboles.

Listas de adyacencia: En teoría de grafos, las listas enlazadas pueden emplearse para representar listas de adyacencia, que son una forma de almacenar grafos en memoria. Cada nodo de la lista enlazada representa un vértice del grafo, y sus nodos adyacentes se almacenan como una lista enlazada asociada a ese vértice.

Gestión de procesos: Los sistemas operativos utilizan listas enlazadas para mantener y gestionar listas de procesos, lo que permite agregar, eliminar y reorganizar procesos de manera eficiente.

Algoritmos de manipulación de texto: Las listas enlazadas son útiles en aplicaciones y algoritmos de procesamiento de texto, como editores de texto, donde la inserción y eliminación de caracteres o líneas se realizan con frecuencia.

Recorridos en listas: En ciertas aplicaciones, como videojuegos o simulaciones, las listas enlazadas pueden utilizarse para recorrer objetos y actualizar su estado o posición en tiempo real.

Undo y redo en aplicaciones: Las listas enlazadas dobles son útiles para implementar funciones de deshacer y rehacer en aplicaciones de software, ya que permiten navegar hacia adelante y hacia atrás en el historial de acciones realizadas.

Cabe destacar que, aunque las listas enlazadas son una herramienta valiosa en ciertos casos de uso, no siempre son la estructura de datos más eficiente. En algunos escenarios, otras estructuras como arrays, slices o árboles pueden ser más apropiadas. La elección de la estructura de datos adecuada dependerá de los requisitos específicos de la aplicación y las operaciones que se realicen con mayor frecuencia.

Los metodos mas comunes de las listas enlazadas

A continuación, se muestra una implementación de una lista enlazada simple en Go con métodos para operaciones básicas como insertar, eliminar y buscar elementos:

package main

import "fmt"

type Node struct {
	data int
	next *Node
}

type LinkedList struct {
	head *Node
	size int
}

// Insertar un elemento al final de la lista enlazada
func (list *LinkedList) Append(value int) {
	newNode := &Node{data: value, next: nil}

	if list.head == nil {
		list.head = newNode
	} else {
		current := list.head
		for current.next != nil {
			current = current.next
		}
		current.next = newNode
	}

	list.size++
}

// Eliminar un elemento de la lista enlazada por valor
func (list *LinkedList) Remove(value int) bool {
	if list.head == nil {
		return false
	}

	if list.head.data == value {
		list.head = list.head.next
		list.size--
		return true
	}

	current := list.head
	for current.next != nil {
		if current.next.data == value {
			current.next = current.next.next
			list.size--
			return true
		}
		current = current.next
	}

	return false
}

// Buscar un elemento en la lista enlazada por valor
func (list *LinkedList) Search(value int) *Node {
	current := list.head
	for current != nil {
		if current.data == value {
			return current
		}
		current = current.next
	}

	return nil
}

// Imprimir la lista enlazada
func (list *LinkedList) Print() {
	current := list.head
	for current != nil {
		fmt.Printf("%d ", current.data)
		current = current.next
	}
	fmt.Println()
}

func main() {
	list := LinkedList{}

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

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

	list.Remove(3)
	fmt.Println("Lista enlazada después de eliminar el valor 3:")
	list.Print()

	node := list.Search(2)
	if node != nil {
		fmt.Println("Elemento encontrado:", node.data)
	} else {
		fmt.Println("Elemento no encontrado")
	}
}

Este código incluye los siguientes métodos:

• Append(): Inserta un elemento al final de la lista enlazada.
• Remove(): Elimina un elemento de la lista enlazada dado su valor. Si el elemento se encuentra en la lista, lo elimina y devuelve true. Si no se encuentra, devuelve false.
• Search(): Busca un elemento en la lista enlazada por su valor y devuelve un puntero al nodo encontrado o nil si no se encuentra.
• Print(): Imprime los elementos de la lista enlazada en orden.

Puedes adaptar y expandir este código según las necesidades de tu aplicación, por ejemplo, agregando métodos para insertar elementos en una posición específica o para eliminar elementos por índice.

Simples vs Doblemente Enlazadas

Las listas enlazadas simples y las listas doblemente enlazadas son variantes de la estructura de datos de listas enlazadas, y su principal diferencia radica en la forma en que los nodos están conectados entre sí. A continuación, se explica la diferencia entre ambas:

Listas enlazadas simples: En una lista enlazada simple, cada nodo contiene un puntero al siguiente nodo de la lista. Esto permite recorrer la lista en una sola dirección, desde el inicio hasta el final. La principal ventaja de las listas enlazadas simples es su simplicidad y menor consumo de memoria, ya que solo se necesita un puntero por nodo. Sin embargo, dado que solo se puede navegar en una dirección, algunas operaciones pueden resultar ineficientes o complicadas de implementar.

Listas doblemente enlazadas: En una lista doblemente enlazada, cada nodo tiene 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, como la eliminación de nodos o el acceso a elementos adyacentes. La principal desventaja de las listas doblemente enlazadas es el mayor consumo de memoria, ya que se requieren dos punteros por nodo, y una mayor complejidad en la manipulación de punteros durante las operaciones de inserción y eliminación.

El siguiente tema que recomendamos aprender es cómo implementar y utilizar listas doblemente enlazadas en Go. Al dominar las listas doblemente enlazadas, podrás manejar una estructura de datos más flexible y adecuada para ciertos casos de uso, como la implementación de algoritmos de acceso aleatorio, la manipulación de listas en ambas direcciones, o la implementación de funciones de deshacer y rehacer en aplicaciones de software.

Lista enlazada simple:

[Head] -> [Nodo 1] -> [Nodo 2] -> ... -> [Nodo n] -> nil

Cada nodo en una lista enlazada simple contiene un puntero al siguiente nodo. El último nodo de la lista apunta a nil, indicando el final de la lista.

Lista doblemente enlazada:

[Head] <-> [Nodo 1] <-> [Nodo 2] <-> ... <-> [Nodo n] <-> nil

En una lista doblemente enlazada, cada nodo contiene dos punteros: uno al siguiente nodo y otro al nodo anterior. El primer nodo de la lista tiene su puntero anterior apuntando a nil, y el último nodo tiene su puntero siguiente apuntando a nil.

Conclusión

Las listas enlazadas son una estructura de datos flexible y dinámica que ofrece una alternativa a los arrays y slices en ciertos casos de uso. Al implementar listas enlazadas en Go, podemos aprovechar las ventajas de su sistema de tipado estático y su enfoque en la simplicidad y el rendimiento. A lo largo de este artículo, hemos presentado los conceptos básicos de las listas enlazadas y proporcionado un ejemplo de implementación en Go. En futuras publicaciones, exploraremos en detalle cómo manipular y optimizar listas enlazadas

En resumen, las listas enlazadas 📝 son una estructura de datos fundamental en el mundo de la programación. Ya sea que estés trabajando con listas enlazadas simples o doblemente enlazadas, ambas ofrecen ventajas y desafíos únicos. Al dominar estas estructuras, podrás abordar una amplia variedad de problemas y aplicaciones en el campo de la informática. 🌟

No olvides que, aunque las listas enlazadas son una herramienta poderosa, siempre 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 enlazadas y otras estructuras de datos tienen para ofrecer! 😊👩‍💻👨‍💻

Ejercicios para practicar

A continuación te dejo unos ejercicios para que practiques la estructura Cola (Queue) en Go y envies la solucioón como un Pull requeste a este repositorio: 

Go Para Principiantes

Insertar al inicio: Implementa un método Prepend(value int) que inserte un elemento al inicio de la lista enlazada.

Insertar en una posición específica: Implementa un método InsertAt(value int, position int) que inserte un elemento en una posición específica de la lista enlazada. Si la posición es inválida (negativa o mayor al tamaño de la lista), el método debe retornar un error.

Eliminar por índice: Implementa un método RemoveAt(position int) que elimine un elemento de la lista enlazada dado su índice. Si la posición es inválida (negativa o mayor o igual al tamaño de la lista), el método debe retornar un error.

Reversa de la lista: Implementa un método Reverse() que invierta el orden de los elementos en la lista enlazada.

Tamaño de la lista: Implementa un método Size() que devuelva el número de elementos en la lista enlazada sin utilizar una variable size en la estructura LinkedList.

Obtener elemento por índice: Implementa un método Get(index int) (*Node, error) que devuelva un puntero al nodo en el índice especificado. Si el índice es inválido (negativo o mayor o igual al tamaño de la lista), el método debe retornar un error.

Eliminar duplicados: Implementa un método RemoveDuplicates() que elimine los elementos duplicados de una lista enlazada sin ordenar, conservando solo la primera aparición de cada valor.

Dividir una lista enlazada: Implementa un método Split(position int) (*LinkedList, error) que divida la lista enlazada en dos listas a partir de una posición dada. La lista original debe contener los elementos anteriores a la posición, y la nueva lista debe contener los elementos a partir de la posición. Si la posición es inválida (negativa o mayor al tamaño de la lista), el método debe retornar un error.

Encontrar el elemento central: Implementa un método FindMiddle() *Node que encuentre y devuelva un puntero al nodo del elemento central de la lista enlazada. Si la lista tiene un número par de elementos, devuelve el primero de los dos nodos centrales.

Detectar ciclos: Implementa un método HasCycle() bool que determine si una lista enlazada tiene un ciclo (es decir, un nodo que apunta a un nodo anterior en lugar de nil). El método debe devolver true si hay un ciclo, y false en caso contrario.

Estos ejercicios te ayudarán a familiarizarte con las operaciones básicas y avanzadas de las listas enlazadas en Go y a profundizar en tus habilidades para manipular y gestionar esta estructura de datos.