Lista Enlazada

Una lista enlazada es una estructura de datos lineal, en la cual los elementos no se almacenan en posiciones de memoria contiguas. Cada elemento (también conocido como nodo) de la lista enlazada está formado por dos partes:

• Una que almacena el dato.
• Otra que almacena la dirección del siguiente elemento de la lista.

El primer elemento de la lista enlazada también se conoce como head, y el último como tail.

Componentes básicos

// Node representa un nodo de la lista enlazada con un dato genérico,
// y la referencia al siguiente Node.
type Node[T comparable] struct {
  value T
  next  *Node[T]
}

// LinkedList representa la lista enlazada que contiene la referencia inicial
// a los demás nodos (`head`) y el número de elementos que contiene la lista.
type LinkedList[T comparable] struct {
  head *Node[T]
  size int
}

// New crea una nueva estructura LinkedList con el `size` inicializado en 0.
func New[T comparable]() *LinkedList[T] {
  return &LinkedList[T]{size: 0}
}

Empecemos por implementar dos métodos sencillos, el primero nos permitirá obtener el tamaño de la lista y el segundo saber si la lista está vacía.

Obtener el tamaño de la lista

// Size regresa el tamaño de la lista.
func (l *LinkedList[T]) Size() int {
  return l.size
}

Determinar si la lista está vacía

// IsEmpty determina si la lista enlazada esta vacía o no.
func (l *LinkedList[T]) IsEmpty() bool {
  return l.size == 0
}

Insertar un elemento

// Add añade un nuevo Node al final de la lista enlazada.
func (l *LinkedList[T]) Add(value T) {
  node := &Node[T]{value: value}
  if l.head == nil {
    l.head = node
    l.size++
    return
  }
  last := l.head
  for last.next != nil {
    last = last.next
  }
  last.next = node
  l.size++
}

Buscar un elemento

// Contains determina si la lista enlazada contiene al elemento `value`.
func (l *LinkedList[T]) Contains(value T) bool {
  if l.head == nil {
    return false
  }
  node := l.head
  for node != nil {
    if node.value == value {
      return true
    }
    node = node.next
  }
  return false
}

Eliminar un elemento

// Remove remueve el Node con el `value` especificado.
func (l *LinkedList[T]) Remove(value T) error {
  if l.head == nil {
    return errors.New("empty list")
  }
  if l.head.value == value {
    l.head = l.head.next
    l.size--
    return nil
  }
  prev := l.head
  for prev.next != nil {
    if prev.next.value == value {
      prev.next = prev.next.next
      l.size--
      return nil
    }
    prev = prev.next
  }
  return fmt.Errorf("value %v not found", value)
}

Implementación completa

package main

import "fmt"

// Node is a node of a linked list with an integer value.
type Node[T comparable] struct {
  value T
  next  *Node[T]
}

// LinkedList is a linked list of nodes, with a head node.
type LinkedList[T comparable] struct {
  head *Node[T]
  size int
}

// Add adds a node to the end of the linked list.
func (l *LinkedList[T]) Add(value T) {
  node := &Node[T]{value: value}
  if l.head == nil {
    l.head = node
    l.size++
    return
  }
  last := l.head
  for last.next != nil {
    last = last.next
  }
  last.next = node
  l.size++
}

// Remove removes a node from the linked list.
func (l *LinkedList[T]) Remove(value T) error {
  if l.head == nil {
    return fmt.Errorf("empty list")
  }
  if l.head.value == value {
    l.head = l.head.next
    l.size--
    return nil
  }
  prev := l.head
  for prev.next != nil {
    if prev.next.value == value {
      prev.next = prev.next.next
      l.size--
      return nil
    }
    prev = prev.next
  }
  return fmt.Errorf("value %v not found", value)
}

// Size returns the size of the linked list.
func (l *LinkedList[T]) Size() int {
  return l.size
}

// IsEmpty returns true if the linked list is empty.
func (l *LinkedList[T]) IsEmpty() bool {
  return l.size == 0
}

// Contains returns true if the linked list contains the value.
func (l *LinkedList[T]) Contains(value T) bool {
  if l.head == nil {
    return false
  }
  node := l.head
  for node != nil {
    if node.value == value {
      return true
    }
    node = node.next
  }
  return false
}

// String regresa un string que representa la lista enlazada.
func (l *LinkedList[T]) String() string {
  if l.head == nil {
    return "[]"
  }
  node := l.head
  s := "["
  for node != nil {
    s += fmt.Sprintf("%v", node.value)
    if node.next != nil {
      s += ", "
    }
    node = node.next
  }
  s += "]"
  return s
}

func New[T comparable]() *LinkedList[T] {
  return &LinkedList[T]{size: 0}
}

func main() {
  ll := New[int]()
  ll.Add(1)
  ll.Add(2)
  ll.Add(3)

  fmt.Println("Elementos:", ll)
  fmt.Println("Tamaño:", ll.Size())

  fmt.Println("¿Está vacía?", ll.IsEmpty())
  fmt.Println("¿Contiene el número 2?", ll.Contains(2))
  fmt.Println("¿Contiene el número 4?", ll.Contains(4))

  fmt.Printf("\nℹ️ Elemento número 2 eliminado...\n\n")

  ll.Remove(2)
  fmt.Println("Elementos:", ll)
  fmt.Println("Tamaño:", ll.Size())
  fmt.Println("¿Está vacía?", ll.IsEmpty())

  fmt.Printf("\nℹ️ Lista enlazada de tipo string creada...\n\n")

  ll2 := New[string]()

  ll2.Add("a")
  ll2.Add("b")
  ll2.Add("c")
  fmt.Println("Elementos:", ll2)
  fmt.Println("Tamaño:", ll2.Size())
  fmt.Println("¿Contiene la letra 'a'?", ll2.Contains("a"))
}

Ejecuta el código en este playground.