Este artículo detalla la implementación de una lista enlazada simple en Go, abarcando funcionalidades esenciales como inicialización, visualización, detección de ciclos, inversión, vaciado, y operaciones de inserción y eliminación en diversas posiciones.
Estructuras de Datos
Se define un nodo (Node) que continee un valor entero y un puntero al siguiente nodo. Una estructura SinglyLinkedList encapsula el nodo cabeza (head) y el tamaño actual de la lista (size).
package singlylinkedlist
import (
"fmt"
)
type Node struct {
value int
next *Node
}
// NewNode crea un nuevo nodo.
func NewNode(value int, next *Node) *Node {
return &Node{value, next}
}
type SinglyLinkedList struct {
head *Node
size int
}
// NewList inicializa una nueva lista enlazada.
func NewList(head *Node, size int) *SinglyLinkedList {
return &SinglyLinkedList{head, size}
}
Operaciones de la Lista
Visualización
El método Display recorre la lista e imprime los valores de cada nodo, separados por "->". Si la lista está vacía, se imprime un mensaje indicándolo.
// Display muestra los valores de los nodos de la lista.
func (l *SinglyLinkedList) Display() {
if l.isEmpty() {
fmt.Println("La lista está vacía.")
return
}
current := l.head
for current != nil {
if current.next == nil {
fmt.Println(current.value)
break
}
fmt.Print(current.value, "->")
current = current.next
}
}
Detección de Ciclos
El método DetectLoop utiliza el algoritmo de los punteros rápido y lento (Floyd's cycle-finding algorithm) para determinar si la lista contiene un ciclo.
// DetectLoop determina si existe un ciclo en la lista.
func (l *SinglyLinkedList) DetectLoop() bool {
slow := l.head
fast := l.head
for (fast != nil) && (fast.next != nil) {
slow = slow.next
fast = fast.next.next
if fast == slow {
return true
}
}
return false
}
Inversión de Lista
El método ReverseList invierte la lista enlazada in-place, modificando los punteros next de cada nodo.
// ReverseList invierte la lista enlazada in-place.
func (l *SinglyLinkedList) ReverseList() {
var previous *Node
current := l.head
next := l.head
for current != nil {
next = current.next
current.next = previous
previous = current
current = next
}
l.head = previous
}
Vaciado de Lista
El método Clear elimina todos los nodos de la lista, estableciendo head a nil y size a 0. Devuelve una lista con los valores de los nodos eliminados.
// Clear elimina todos los nodos de la lista.
func (l *SinglyLinkedList) Clear() (values []int) {
current := l.head
for current != nil {
previous := current
values = append(values, previous.value)
current = current.next
previous = nil // Liberar memoria implícitamente
}
l.head = nil
l.size = 0
return values
}
Verificación de Vacío
El método IsEmpty devuelve true si la lista está vacía (tamaño es 0), y false en caso contrario.
// IsEmpty verifica si la lista está vacía.
func (l *SinglyLinkedList) IsEmpty() bool {
return l.size == 0
}
Obtención de Tamaño
El método Length devuelve el número actual de elementos en la lista.
// Length devuelve el tamaño de la lista.
func (l *SinglyLinkedList) Length() int {
return l.size
}
Acceso a la Cabeza
Los métodos GetHead y SetHead permiten obtener y establecer el nodo cabeza de la lista, respectivamente.
// GetHead devuelve el nodo cabeza de la lista.
func (l *SinglyLinkedList) GetHead() *Node {
return l.head
}
// SetHead establece el nodo cabeza de la lista.
func (l *SinglyLinkedList) SetHead(node *Node) {
l.head = node
}
Conteo Manual
El método Count calcula manualmente el número de nodos en la lista recorriéndola desde la cabeza.
// Count calcula manualmente el número de nodos en la lista.
func (l *SinglyLinkedList) Count() int {
count := 0
current := l.head
for current != nil {
count++
current = current.next
}
return count
}
Búsqueda de Valor
El método Search comprueba si un valor específico (key) existe dentro de la lista.
// Search verifica si un valor existe en la lista.
func (l *SinglyLinkedList) Search(key int) bool {
current := l.head
for current != nil {
if current.value == key {
return true
}
current = current.next
}
return false
}
Obtención por Índice
El método GetNth devuelve el valor del nodo en un índice especificado. Utiliza CheckBounds para validar el índice.
// GetNth devuelve el valor del nodo en el índice especificado.
func (l *SinglyLinkedList) GetNth(index int) int {
l.CheckBounds(index, 0, l.size-1)
current := l.head
for i := 0; i < index; i++ {
current = current.next
}
return current.value
}
Inserción de Nodos
Los métodos InsertHead, InsertTail e InsertNth permiten insertar nuevos nodos al principio, al final o en una posición específica de la lista, respectivamente. InsertNth maneja la lógica de inserción general.
// InsertHead inserta un elemento al principio de la lista.
func (l *SinglyLinkedList) InsertHead(data int) {
l.InsertNth(data, 0)
}
// InsertTail inserta un elemento al final de la lista.
func (l *SinglyLinkedList) InsertTail(data int) {
l.InsertNth(data, l.size)
}
// InsertNth inserta un nuevo nodo en una posición especificada.
func (l *SinglyLinkedList) InsertNth(data int, position int) {
l.CheckBounds(position, 0, l.size)
newNode := NewNode(data, nil)
if l.head == nil { // Lista vacía
l.head = newNode
l.size++
return
}
if position == 0 { // Insertar al principio
newNode.next = l.head
l.head = newNode
l.size++
return
}
// Encontrar el nodo anterior a la posición de inserción
current := l.head
for i := 0; i < position-1; i++ {
current = current.next
}
newNode.next = current.next
current.next = newNode
l.size++
}
Eliminación de Nodos
Los métodos DeleteHead, DeleteTail y DeleteNth eliminan nodos de la cabeza, la cola o una posición específica. DeleteNth contiene la lógica principal de eliminación.
// DeleteHead elimina el nodo de la cabeza.
func (l *SinglyLinkedList) DeleteHead() int {
return l.DeleteNth(0)
}
// DeleteTail elimina el nodo de la cola.
func (l *SinglyLinkedList) DeleteTail() int {
return l.DeleteNth(l.size - 1)
}
// DeleteNth elimina el nodo en la posición especificada y devuelve su valor.
func (l *SinglyLinkedList) DeleteNth(position int) int {
l.CheckBounds(position, 0, l.size-1)
var deletedValue int
if position == 0 { // Eliminar cabeza
nodeToDelete := l.head
deletedValue = nodeToDelete.value
l.head = l.head.next
nodeToDelete = nil // Liberar memoria
l.size--
return deletedValue
}
// Encontrar el nodo anterior a la posición a eliminar
current := l.head
for i := 0; i < position-1; i++ {
current = current.next
}
nodeToDelete := current.next
deletedValue = nodeToDelete.value
current.next = current.next.next
nodeToDelete = nil // Liberar memoria
l.size--
return deletedValue
}
Validación de Límites
El método CheckBounds se utiliza para asegurar que las posiciones proporcionadas en las operaciones de inserción y eliminación estén dentro de los límites válidos de la lista. Si un índice está fuera de rango, se lanza una excepción panic.
// CheckBounds verifica si una posición está dentro de los límites permitidos.
func (l *SinglyLinkedList) CheckBounds(position int, low int, high int) {
if position < low || position > high {
panic("Índice fuera de rango")
}
}