Listas Ligadas

Sejam bem-vindos a mais uma do curso Estruturas de Dados Essenciais. Hoje vamos abordar, mais uma vez, uma estrutura de sequência, só que com uma abordagem diferente.

Hoje falaremos sobre listas ligadas, nossa primeira estrutura de nós.

Alguns dos conceitos que veremos aqui serão importantes para entendermos e construírmos outras estruturas extremamente importantes em toda a ciência da computação, as árvores.

Introdução

Listas ligadas são estruturas de dados que representam uma sequência de elementos. Cada elemento é um nó que contém um valor e uma referência para o próximo nó.

Aqui está um exemplo de uma lista ligada com três elementos:

1 -> 2 -> 3

Cada nó contém um valor e uma referência para o próximo nó. O último nó da lista tem uma referência nula.

Tipos de Listas Ligadas

Existem vários tipos de listas ligadas. As mais comuns são:

Simplesmente ligada: Cada nó contém uma referência para o próximo nó.
Duplamente ligada: Cada nó contém uma referência para o próximo nó e para o nó anterior.
Circular: A referência do último nó aponta para o primeiro nó.
Circular duplamente ligada: A referência do último nó aponta para o primeiro nó e a referência do primeiro nó aponta para o último nó.

ADT Lista Ligada

build(X): Cria uma nova lista ligada.
insert(value): Insere um novo valor na lista ligada.
delete(value): Remove um valor da lista ligada.
search(value): Busca um valor na lista ligada.
size(): Retorna o tamanho da lista ligada.
isEmpty(): Retorna se a lista ligada está vazia.

Implementação

Vamos implementar uma lista ligada simples em Ruby.

class Node
  attr_accessor :value, :next

  def initialize(value)
    @value = value
    @next = nil
  end
end

class LinkedList
  def initialize
    @head = nil
  end

  def insert(value)
    node = Node.new(value)

    if @head.nil?
      @head = node
    else
      current = @head

      while current.next
        current = current.next
      end

      current.next = node
    end
  end

  def delete(value)
    current = @head

    if current.value == value
      @head = current.next
    else
      while current.next
        if current.next.value == value
          current.next = current.next.next
          break
        end

        current = current.next
      end
    end
  end

  def search(value)
    current = @head

    while current
      return true if current.value == value

      current = current.next
    end

    false
  end

  def size
    count = 0
    current = @head

    while current
      count += 1
      current = current.next
    end

    count
  end

  def isEmpty
    @head.nil?
  end
end

Casos de Uso

Fila: Listas ligadas são muito utilizadas para implementar filas.
Pilha: Listas ligadas são muito utilizadas para implementar pilhas.
…