Introdução

O que são estruturas de dados afinal? Estruturas de dados são formas organizadas de armazenar, gerenciar e organizar dados para que eles possam ser usados com eficiência em diferentes computações. Elas definem o formato e as relações entre os elementos de dados, permitindo melhor recuperação, manipulação e armazenamento. Existem vários tipos de estruturas de dados e hoje vamos falar sobre Listas e algumas variações como Array Lists, Listas Encadeadas Simples e Listas Encadeadas Duplas.

Vamos começar definindo uma interface Container que pode generalizar estruturas de dados. Essa interface terá os seguintes métodos:

type Container interface {
  Empty() bool
  Size() int
  Clear()
  Values() []interface{}
  String() string
}

Todas as implementações de listas neste artigo vão seguir essa interface.

Funções auxiliares

Estruturas de dados podem ser ordenadas ou não ordenadas. Neste artigo, todas as estruturas de dados ordenadas vão fornecer iteradores com estado e algumas delas também vão permitir funções enumeráveis.

Um iterador é uma interface usada para percorrer a estrutura de dados. Nas implementações deste artigo, o iterador das estruturas que oferecem um pode ser obtido usando o método Iterator(). Depois disso, a função iterator.Next() pode ser usada para mover o cursor do iterador para o próximo elemento na estrutura de dados, essa função retorna true se existir um próximo elemento. Depois da chamada de Next(), o elemento atual apontado pelo cursor pode ser obtido pela função Value().

A interface básica de Iterator é:

type Iterator[V any] interface {
  Next() bool
  Value() V
  Begin() // Esta função reseta o iterador para um estado um-antes-do-primeiro, para que quando você chamar Next(), ele não vá para o segundo elemento.
  First() bool // Move o cursor para o primeiro elemento do iterador
}

Esse iterador tem uma implementação com estado, então as funções Next(), Begin() e First() alteram o estado do iterador movendo o cursor.

Listas

Existem alguns tipos de Listas. Algumas delas são Array Lists, Singly Linked Lists, Doubly Linked Lists e Multi-Linked Lists. Cada uma delas pode ter variações e aplicações próprias que vamos exemplificar aqui. Uma Lista é basicamente uma coleção linear de elementos onde cada elemento é armazenado em sequência e pode ser acessado individualmente. Listas permitem inserção, remoção e travessia dinâmica de elementos, o que as torna flexíveis para organização de dados. Dependendo da implementação, listas podem suportar acesso aleatório ou exigir travessia sequencial.

Array Lists

Uma Array List é uma lista baseada em um array dinâmico que cresce e diminui implicitamente. Os dados ficam em um bloco contínuo de memória e esse tipo de lista permite acesso aleatório, você pode acessar qualquer elemento a qualquer momento, o que deixa a busca muito rápida (complexidade O(1)). Por outro lado, inserções podem ser custosas porque podem exigir deslocamento de elementos (principalmente quando a inserção acontece no meio). Se o array interno atingir sua capacidade, um novo array maior é alocado e os elementos existentes são copiados para ele.

Na prática, essa é uma boa implementação padrão quando leituras e acesso por índice acontecem com frequência.

Uma implementação básica de ArrayList seguindo a interface Container:

type ArrayList struct {
  elements []interface{}
}

func NewArrayList(values ...interface{}) *ArrayList {
  return &ArrayList{elements: append([]interface{}{}, values...)}
}

func (l *ArrayList) Empty() bool {
  return len(l.elements) == 0
}

func (l *ArrayList) Size() int {
  return len(l.elements)
}

func (l *ArrayList) Clear() {
  l.elements = nil
}

func (l *ArrayList) Values() []interface{} {
  return append([]interface{}{}, l.elements...)
}

func (l *ArrayList) String() string {
  return fmt.Sprintf("%v", l.elements)
}

Listas Encadeadas Simples

Singly Linked Lists são um tipo de Lista em que cada elemento armazena uma referência apenas para o próximo elemento. Existe apenas uma referência por nó e ela sempre aponta para frente na sequência.

Isso torna inserção e remoção no início muito eficientes (O(1)), porque só precisamos atualizar um ponteiro. Porém, o acesso por índice é sequencial (O(n)), já que para chegar em um elemento precisamos percorrer os nós desde o início até encontrar a posição desejada.

Um modelo básico de nó para uma singly linked list em Go é:

type SinglyNode[V any] struct {
  Value V
  Next  *SinglyNode[V]
}

Singly linked lists são úteis quando o padrão de acesso é majoritariamente sequencial e quando inserções/remoções baratas no início são mais importantes do que acesso aleatório.

Uma implementação básica de SinglyLinkedList seguindo a mesma interface:

type SinglyLinkedList struct {
  head *SinglyNode[interface{}]
  size int
}

func (l *SinglyLinkedList) Empty() bool {
  return l.size == 0
}

func (l *SinglyLinkedList) Size() int {
  return l.size
}

func (l *SinglyLinkedList) Clear() {
  l.head = nil
  l.size = 0
}

func (l *SinglyLinkedList) Values() []interface{} {
  values := make([]interface{}, 0, l.size)
  for n := l.head; n != nil; n = n.Next {
    values = append(values, n.Value)
  }
  return values
}

func (l *SinglyLinkedList) String() string {
  return fmt.Sprintf("%v", l.Values())
}

Listas Encadeadas Duplas

Doubly Linked Lists são parecidas com singly linked lists, mas cada elemento armazena duas referências: uma para o próximo elemento e outra para o elemento anterior.

Com isso, a travessia pode acontecer nas duas direções e remoções ficam mais simples quando você já tem uma referência para o nó atual, porque dá para reconectar os nós anterior e próximo diretamente.

Um modelo básico de nó para uma doubly linked list em Go é:

type DoublyNode[V any] struct {
  Value V
  Prev  *DoublyNode[V]
  Next  *DoublyNode[V]
}

Essa flexibilidade extra tem um custo de memória maior, já que cada nó armazena um ponteiro adicional.

Uma implementação básica de DoublyLinkedList:

type DoublyLinkedList struct {
  head *DoublyNode[interface{}]
  tail *DoublyNode[interface{}]
  size int
}

func (l *DoublyLinkedList) Empty() bool {
  return l.size == 0
}

func (l *DoublyLinkedList) Size() int {
  return l.size
}

func (l *DoublyLinkedList) Clear() {
  l.head = nil
  l.tail = nil
  l.size = 0
}

func (l *DoublyLinkedList) Values() []interface{} {
  values := make([]interface{}, 0, l.size)
  for n := l.head; n != nil; n = n.Next {
    values = append(values, n.Value)
  }
  return values
}

func (l *DoublyLinkedList) String() string {
  return fmt.Sprintf("%v", l.Values())
}

Qual delas você deve usar?

Não existe implementação de lista universalmente melhor, a escolha certa depende do seu caso de uso:

• Array List: Melhor quando você precisa de leituras frequentes por índice.
• Lista Encadeada Simples: Melhor quando você percorre para frente e faz inserções/remoções frequentes no início.
• Lista Encadeada Dupla: Melhor quando você precisa de travessia em dois sentidos ou remoções frequentes no meio quando já possui referência para os nós.

Entender esses trade-offs é mais importante do que memorizar definições.

Conclusão

Hoje cobrimos o tema de listas de ponta a ponta: o que são listas, as diferenças entre Array Lists, Listas Encadeadas Simples e Listas Encadeadas Duplas, e exemplos práticos de implementação para cada uma.

No próximo artigo vamos entrar em outra categoria de estrutura de dados e manter a mesma abordagem de Container e iteradores mostrada aqui.