Algoritmos

Lista encadeada: cada item aponta o caminho para o próximo

Capa do artigo Lista encadeada: cada item aponta o caminho para o próximo
Leitura com foco

Entenda o contexto.
Leve para a prática.

Neste artigo
  1. Como funciona uma lista encadeada?
  2. Qual a diferença entre vetor e lista encadeada?
  3. Como montar uma lista encadeada só com referências?
  4. Aí você pergunta: o proximo guarda uma cópia do nó?
  5. Como adicionar, buscar e remover nós?
  6. Adicionar no início: ligar primeiro, mover depois
  7. Adicionar no fim: caminhar até o último
  8. Buscar: percorrer até achar
  9. Remover: desviar a seta
  10. Aí você pergunta: a lista encadeada é mais rápida que o vetor?
  11. E nas outras linguagens?
  12. Aí você pergunta: preciso criar a lista encadeada na mão?
  13. Quais são os erros mais comuns com lista encadeada?
  14. Agora é com você!

Lista encadeada é uma estrutura de dados em que cada elemento, chamado de nó, guarda um valor e a indicação de onde está o próximo elemento. Os nós não precisam ficar lado a lado na memória: o que mantém a sequência é essa ligação de um para o outro.

No artigo sobre bubble sort, deixei um desafio: contar as trocas para ordenar o vetor [4, 2, 7, 1, 3]. A resposta é 6 trocas. Conseguiu? Se o seu número deu diferente, refaça passada por passada, sem pressa.

Hoje começamos uma trilha nova: a das estruturas de dados. E a primeira pergunta é: se já existe o vetor, para que inventar outro jeito de guardar valores em sequência? Calma, você já entenderá!

Como funciona uma lista encadeada?

Pense em uma caça ao tesouro. Você recebe a primeira pista, e nela está escrito onde fica a segunda. Na segunda está escrito onde fica a terceira, e assim vai, até a última, que não aponta para lugar nenhum. Você não sabe de antemão onde está a quarta pista: precisa passar pela primeira, pela segunda e pela terceira para chegar nela.

História em quadrinhos em três quadros de uma caça ao tesouro: a pista 1 leva à pista 2, a pista 2 leva à pista 3 e a pista 3 marca o fim
A lista encadeada como caça ao tesouro: cada pista diz onde está a próxima.

Na lista encadeada é igualzinho:

  • Nó: é cada pista. Guarda um valor e a referência para o próximo nó.
  • Início (ou cabeça): é a primeira pista. É a única que a lista precisa guardar.
  • Fim: é o último nó, que aponta para “nada” (null em Java e em PHP, None em Python e NULL em C).

Qual a diferença entre vetor e lista encadeada?

No vetor, os valores ficam um do lado do outro, e você chega em qualquer posição direto pelo índice. Na lista encadeada, os nós ficam espalhados, e você só chega em um deles caminhando desde o início.

VetorLista encadeada
Como os valores ficam na memóriaLado a ladoEspalhados, ligados por referências
Acessar a posição 500Direto, pelo índicePrecisa passar pelos 500 nós que vêm antes
Inserir no inícioPrecisa empurrar todos os valores uma posiçãoCria um nó e ajusta uma referência
Memória por elementoSó o valorO valor e mais a referência para o próximo
Diferença entre vetor e lista encadeada.

Então não existe “a melhor”: existe a que combina com o problema. Precisa acessar muito pelo índice? Vetor. Precisa inserir e remover o tempo todo no início? Lista encadeada. Saber escolher é o que separa quem decora de quem entende!

Como montar uma lista encadeada só com referências?

Vamos ao código, começando pelo Java. Nada de estrutura pronta da linguagem: só uma classe para o nó, com duas propriedades. A valor guarda o número. A proximo é do tipo No, a própria classe do nó: é por ela que um objeto chega ao outro.

// Lista encadeada sem nenhuma classe pronta: só objetos ligados por referências
public class ListaNaMao {

    // cada nó guarda um valor e a referência para o próximo nó
    static class No {
        int valor;
        No proximo; // ninguém deu valor a ele: começa em null

        No(int valor) {
            this.valor = valor;
        }
    }

    public static void main(String[] args) {
        No primeiro = new No(10);
        No segundo = new No(20);
        No terceiro = new No(30);

        primeiro.proximo = segundo; // o 10 aponta para o 20
        segundo.proximo = terceiro; // o 20 aponta para o 30
        // terceiro.proximo continua null: é o fim da lista

        No atual = primeiro;
        while (atual != null) {
            System.out.print(atual.valor + " -> ");
            atual = atual.proximo; // pula para o próximo nó
        }
        System.out.println("null");

        // por baixo dos panos: o que a propriedade proximo guarda?
        System.out.println("primeiro.proximo == segundo? " + (primeiro.proximo == segundo));
        segundo.valor = 99;
        System.out.println("primeiro.proximo.valor depois de mudar o segundo: " + primeiro.proximo.valor);
    }
}

Para rodar, salve o código em um arquivo chamado ListaNaMao.java e digite java ListaNaMao.java. Desde o Java 11, o comando java compila um programa de arquivo único na memória e já executa a primeira classe dele. Saída:

10 -> 20 -> 30 -> null
primeiro.proximo == segundo? true
primeiro.proximo.valor depois de mudar o segundo: 99
Diagrama de três nós em Java: as variáveis primeiro, segundo e terceiro apontam para os nós 10, 20 e 30; o proximo do 10 aponta para o 20, o proximo do 20 aponta para o 30 e o proximo do 30 é null
Cada seta é uma referência guardada na propriedade proximo.

As três primeiras linhas do main criam três objetos soltos. Quem transforma os três em uma lista são as duas atribuições seguintes: primeiro.proximo = segundo e segundo.proximo = terceiro. No terceiro.proximo ninguém mexeu, e mesmo assim ele vale null: pela especificação do Java, toda propriedade de tipo objeto começa valendo null. É esse null que marca o fim da corrente.

O while faz a caça ao tesouro: mostra o valor do nó atual e pula para onde o proximo aponta, até chegar ao null.

Aí você pergunta: o proximo guarda uma cópia do nó?

Não! E as duas últimas linhas da saída provam isso. Com objetos, o == não compara o conteúdo: pela especificação do Java, ele dá true quando os dois lados apontam para o mesmo objeto. Deu true, então primeiro.proximo e segundo são o mesmo objeto, com dois nomes.

A segunda prova é ainda mais direta: o programa mudou o valor pelo nome segundo e leu pelo caminho primeiro.proximo. Apareceu 99. Só existe um objeto, e as duas variáveis guardam o caminho até ele. A especificação chama esse caminho de referência e explica que ela é um ponteiro para o objeto. É a mesma ideia do ponteiro: o papel com o endereço, não a casa.

Como adicionar, buscar e remover nós?

Ligar nó por nó à mão mostra o mecanismo, mas ninguém quer escrever primeiro.proximo = segundo para cada valor kkkk. A classe ListaEncadeada guarda só o inicio e faz as ligações dentro dos métodos:

// Lista encadeada feita à mão em Java: adicionar, buscar, remover e percorrer
public class ListaEncadeada {

    // cada nó guarda um valor e a referência para o próximo nó
    static class No {
        int valor;
        No proximo;

        No(int valor) {
            this.valor = valor;
        }
    }

    private No inicio; // o primeiro nó; null enquanto a lista está vazia

    // adiciona no início: o nó novo aponta para quem era o primeiro
    void adicionarNoInicio(int valor) {
        No novo = new No(valor);
        novo.proximo = inicio; // 1º: liga o nó novo ao antigo primeiro
        inicio = novo;         // 2º: o início passa a ser o nó novo
    }

    // adiciona no fim: caminha até o último nó e liga o novo depois dele
    void adicionarNoFim(int valor) {
        No novo = new No(valor);
        if (inicio == null) {
            inicio = novo;
            return;
        }
        No atual = inicio;
        while (atual.proximo != null) {
            atual = atual.proximo;
        }
        atual.proximo = novo;
    }

    // busca: anda de nó em nó até achar o valor ou chegar ao fim
    boolean contem(int valor) {
        No atual = inicio;
        while (atual != null) {
            if (atual.valor == valor) {
                return true;
            }
            atual = atual.proximo;
        }
        return false;
    }

    // remove: o nó anterior passa a apontar para o nó seguinte
    boolean remover(int valor) {
        if (inicio == null) {
            return false;
        }
        if (inicio.valor == valor) {
            inicio = inicio.proximo;
            return true;
        }
        No anterior = inicio;
        while (anterior.proximo != null && anterior.proximo.valor != valor) {
            anterior = anterior.proximo;
        }
        if (anterior.proximo == null) {
            return false; // chegou ao fim sem achar
        }
        anterior.proximo = anterior.proximo.proximo; // pula o nó removido
        return true;
    }

    // percorre do início até o null, mostrando cada ligação
    void percorrer() {
        No atual = inicio;
        while (atual != null) {
            System.out.print(atual.valor + " -> ");
            atual = atual.proximo;
        }
        System.out.println("null");
    }

    public static void main(String[] args) {
        ListaEncadeada lista = new ListaEncadeada();
        lista.adicionarNoInicio(30);
        lista.adicionarNoInicio(20);
        lista.adicionarNoInicio(10);
        System.out.print("adicionando 30, 20 e 10 no início: ");
        lista.percorrer();

        lista.adicionarNoFim(40);
        System.out.print("adicionando 40 no fim:             ");
        lista.percorrer();

        System.out.println("contém 30? " + lista.contem(30));

        lista.remover(20);
        System.out.print("removendo o 20:                    ");
        lista.percorrer();

        System.out.println("contém 20? " + lista.contem(20));
    }
}

Saída:

adicionando 30, 20 e 10 no início: 10 -> 20 -> 30 -> null
adicionando 40 no fim:             10 -> 20 -> 30 -> 40 -> null
contém 30? true
removendo o 20:                    10 -> 30 -> 40 -> null
contém 20? false

Adicionar no início: ligar primeiro, mover depois

O adicionarNoInicio tem duas linhas, e a ordem delas importa. Primeiro, o nó novo passa a apontar para quem era o primeiro. Só depois o inicio passa a ser o nó novo. Reparou que o 30 entrou primeiro e terminou por último? Cada valor novo entra na frente de todos.

Diagrama de uma lista encadeada antes e depois de inserir o nó 10 no início
Inserção no início: o nó novo aponta para o antigo primeiro, e o início passa a apontar para o nó novo.
Ver a animação da inserção no início e do percurso
Animação de uma lista encadeada recebendo os valores 30, 20 e 10 no início e sendo percorrida nó por nó
O mesmo exemplo em movimento: três inserções no início e, depois, o percurso do primeiro nó até o fim.

Em nenhum momento foi preciso mexer nos nós que já existiam. Tanto faz se a lista tem 3 ou 3 milhões de nós: inserir no início dá o mesmo trabalho.

Adicionar no fim: caminhar até o último

O adicionarNoFim não sabe onde está o último nó. Ele começa no inicio e anda enquanto o proximo do nó atual não for null. Quando para, está no último, e é só ligar o nó novo nele. Quanto maior a lista, maior a caminhada. Dá para evitar essa caminhada guardando também uma referência para o último nó.

Buscar: percorrer até achar

O contem segue o mesmo caminho do percorrer, mas para assim que encontra o valor. No pior caso, passa por todos os nós.

Já para achar um valor, o jeito é percorrer nó por nó. É por isso que a busca binária não combina com a lista encadeada: não dá para pular direto para o meio. Sacou?

Remover: desviar a seta

O remover procura o nó que vem antes do valor, o anterior, e faz a seta dele pular o nó removido: anterior.proximo = anterior.proximo.proximo. Se o valor estiver no primeiro nó, não existe anterior, e quem anda é o próprio inicio.

Diagrama da remoção do 20 em uma lista com 10, 20, 30 e 40: antes, o 10 aponta para o 20; depois, a referência do 10 pula o 20 e aponta para o 30, e o 20 fica sem ninguém apontando para ele
Remover é desviar uma seta: o nó anterior passa a apontar para o seguinte.

E o nó do 20, para onde foi? Ninguém mais aponta para ele. Pelo guia do coletor de lixo da Oracle, um objeto que nenhuma referência de outro objeto vivo alcança é considerado lixo, e a máquina virtual pode reaproveitar a memória dele. Em C, ninguém recolhe por você: quem remove o nó precisa chamar free, como você viu no artigo sobre alocação de memória.

Aí você pergunta: a lista encadeada é mais rápida que o vetor?

Depende da operação, e dá para medir. O programa abaixo coloca 100.000 valores no início de duas listas: um ArrayList, a lista do Java que guarda os valores em um vetor, e a nossa lista à mão. Depois, lê o valor do meio de cada uma 10.000 vezes. Cada medição foi repetida 5 vezes, e ficou o menor tempo.

Ver o programa da medição
// Inserir no início e ler o meio: a lista feita à mão contra o ArrayList
import java.util.ArrayList;

public class Medicao {

    static class No {
        int valor;
        No proximo;

        No(int valor) {
            this.valor = valor;
        }
    }

    static final int N = 100_000;     // quantos valores entram em cada lista
    static final int LEITURAS = 10_000; // quantas vezes o valor do meio é lido

    public static void main(String[] args) {
        double melhorArrayInserir = Double.MAX_VALUE, melhorListaInserir = Double.MAX_VALUE;
        double melhorArrayLer = Double.MAX_VALUE, melhorListaLer = Double.MAX_VALUE;
        long somaArray = 0, somaLista = 0;

        for (int rodada = 0; rodada < 5; rodada++) { // 5 rodadas; fica a mais rápida
            // inserir no início do ArrayList: cada add(0, ...) empurra todos para a direita
            long t0 = System.nanoTime();
            ArrayList<Integer> vetor = new ArrayList<>();
            for (int i = 0; i < N; i++) {
                vetor.add(0, i);
            }
            melhorArrayInserir = Math.min(melhorArrayInserir, (System.nanoTime() - t0) / 1e6);

            // inserir no início da lista à mão: um nó novo e uma referência ajustada
            t0 = System.nanoTime();
            No inicio = null;
            for (int i = 0; i < N; i++) {
                No novo = new No(i);
                novo.proximo = inicio;
                inicio = novo;
            }
            melhorListaInserir = Math.min(melhorListaInserir, (System.nanoTime() - t0) / 1e6);

            // ler o valor do meio no ArrayList: direto pela posição
            t0 = System.nanoTime();
            somaArray = 0;
            for (int k = 0; k < LEITURAS; k++) {
                somaArray += vetor.get(N / 2);
            }
            melhorArrayLer = Math.min(melhorArrayLer, (System.nanoTime() - t0) / 1e6);

            // ler o valor do meio na lista à mão: caminhando desde o início
            t0 = System.nanoTime();
            somaLista = 0;
            for (int k = 0; k < LEITURAS; k++) {
                No atual = inicio;
                for (int passo = 0; passo < N / 2; passo++) {
                    atual = atual.proximo;
                }
                somaLista += atual.valor;
            }
            melhorListaLer = Math.min(melhorListaLer, (System.nanoTime() - t0) / 1e6);
        }

        System.out.printf("inserir 100.000 valores no início: ArrayList %6.1f ms | lista à mão %6.1f ms%n",
                melhorArrayInserir, melhorListaInserir);
        System.out.printf("ler o valor do meio 10.000 vezes:  ArrayList %6.1f ms | lista à mão %6.1f ms%n",
                melhorArrayLer, melhorListaLer);
        System.out.println("o valor do meio é o mesmo nas duas? " + (somaArray == somaLista));
    }
}

Saída:

inserir 100.000 valores no início: ArrayList  387.6 ms | lista à mão    0.4 ms
ler o valor do meio 10.000 vezes:  ArrayList    0.0 ms | lista à mão  787.1 ms
o valor do meio é o mesmo nas duas? true

Cada estrutura ganhou uma e perdeu a outra. No início, o ArrayList levou quase mil vezes mais tempo: a documentação do Java explica que inserir em uma posição empurra o elemento que estava ali e todos os seguintes uma casa para a direita. Na leitura do meio, a situação se inverte. O get do ArrayList roda em tempo constante, também pela documentação, enquanto a nossa lista precisa caminhar 50.000 nós a cada leitura. É a tabela lá de cima, agora com números!

E nas outras linguagens?

O conceito é o mesmo em todas: um nó com o valor e a ligação para o próximo, e uma variável que guarda o início. Em Python e em PHP, o nó também é uma classe, o fim é None ou null, e a própria linguagem cuida da memória. Em C, o nó é uma struct, o campo proximo é um ponteiro com o endereço do próximo nó, e cada nó é pedido com malloc e devolvido com free. As saídas só mudam no jeito de cada linguagem escrever o fim e o verdadeiro ou falso. Foque no conceito, e não na linguagem!

Ver a mesma lista em Python, PHP e C

Python:

# Lista encadeada feita à mão em Python: adicionar, buscar, remover e percorrer

class No:
    def __init__(self, valor):
        self.valor = valor
        self.proximo = None  # ainda não aponta para ninguém


class ListaEncadeada:
    def __init__(self):
        self.inicio = None  # o primeiro nó; None enquanto a lista está vazia

    def adicionar_no_inicio(self, valor):
        novo = No(valor)
        novo.proximo = self.inicio  # 1º: liga o nó novo ao antigo primeiro
        self.inicio = novo          # 2º: o início passa a ser o nó novo

    def adicionar_no_fim(self, valor):
        novo = No(valor)
        if self.inicio is None:
            self.inicio = novo
            return
        atual = self.inicio
        while atual.proximo is not None:
            atual = atual.proximo
        atual.proximo = novo

    def contem(self, valor):
        atual = self.inicio
        while atual is not None:
            if atual.valor == valor:
                return True
            atual = atual.proximo
        return False

    def remover(self, valor):
        if self.inicio is None:
            return False
        if self.inicio.valor == valor:
            self.inicio = self.inicio.proximo
            return True
        anterior = self.inicio
        while anterior.proximo is not None and anterior.proximo.valor != valor:
            anterior = anterior.proximo
        if anterior.proximo is None:
            return False  # chegou ao fim sem achar
        anterior.proximo = anterior.proximo.proximo  # pula o nó removido
        return True

    def percorrer(self):
        atual = self.inicio
        while atual is not None:
            print(atual.valor, end=" -> ")
            atual = atual.proximo
        print("None")


lista = ListaEncadeada()
lista.adicionar_no_inicio(30)
lista.adicionar_no_inicio(20)
lista.adicionar_no_inicio(10)
print("adicionando 30, 20 e 10 no início: ", end="")
lista.percorrer()

lista.adicionar_no_fim(40)
print("adicionando 40 no fim:             ", end="")
lista.percorrer()

print("contém 30?", lista.contem(30))

lista.remover(20)
print("removendo o 20:                    ", end="")
lista.percorrer()

print("contém 20?", lista.contem(20))

Saída:

adicionando 30, 20 e 10 no início: 10 -> 20 -> 30 -> None
adicionando 40 no fim:             10 -> 20 -> 30 -> 40 -> None
contém 30? True
removendo o 20:                    10 -> 30 -> 40 -> None
contém 20? False

PHP:

<?php
// Lista encadeada feita à mão em PHP: adicionar, buscar, remover e percorrer

class No
{
    public ?No $proximo = null; // ainda não aponta para ninguém

    public function __construct(public int $valor)
    {
    }
}

class ListaEncadeada
{
    private ?No $inicio = null; // o primeiro nó; null enquanto a lista está vazia

    public function adicionarNoInicio(int $valor): void
    {
        $novo = new No($valor);
        $novo->proximo = $this->inicio; // 1º: liga o nó novo ao antigo primeiro
        $this->inicio = $novo;          // 2º: o início passa a ser o nó novo
    }

    public function adicionarNoFim(int $valor): void
    {
        $novo = new No($valor);
        if ($this->inicio === null) {
            $this->inicio = $novo;
            return;
        }
        $atual = $this->inicio;
        while ($atual->proximo !== null) {
            $atual = $atual->proximo;
        }
        $atual->proximo = $novo;
    }

    public function contem(int $valor): bool
    {
        $atual = $this->inicio;
        while ($atual !== null) {
            if ($atual->valor === $valor) {
                return true;
            }
            $atual = $atual->proximo;
        }
        return false;
    }

    public function remover(int $valor): bool
    {
        if ($this->inicio === null) {
            return false;
        }
        if ($this->inicio->valor === $valor) {
            $this->inicio = $this->inicio->proximo;
            return true;
        }
        $anterior = $this->inicio;
        while ($anterior->proximo !== null && $anterior->proximo->valor !== $valor) {
            $anterior = $anterior->proximo;
        }
        if ($anterior->proximo === null) {
            return false; // chegou ao fim sem achar
        }
        $anterior->proximo = $anterior->proximo->proximo; // pula o nó removido
        return true;
    }

    public function percorrer(): void
    {
        $atual = $this->inicio;
        while ($atual !== null) {
            echo $atual->valor, ' -> ';
            $atual = $atual->proximo;
        }
        echo 'null', PHP_EOL;
    }
}

$lista = new ListaEncadeada();
$lista->adicionarNoInicio(30);
$lista->adicionarNoInicio(20);
$lista->adicionarNoInicio(10);
echo 'adicionando 30, 20 e 10 no início: ';
$lista->percorrer();

$lista->adicionarNoFim(40);
echo 'adicionando 40 no fim:             ';
$lista->percorrer();

echo 'contém 30? ', var_export($lista->contem(30), true), PHP_EOL;

$lista->remover(20);
echo 'removendo o 20:                    ';
$lista->percorrer();

echo 'contém 20? ', var_export($lista->contem(20), true), PHP_EOL;

Saída:

adicionando 30, 20 e 10 no início: 10 -> 20 -> 30 -> null
adicionando 40 no fim:             10 -> 20 -> 30 -> 40 -> null
contém 30? true
removendo o 20:                    10 -> 30 -> 40 -> null
contém 20? false

C:

/* Lista encadeada feita à mão em C: adicionar, buscar, remover e percorrer */
#include <stdio.h>
#include <stdlib.h>

struct No {
    int valor;
    struct No *proximo; /* ponteiro: guarda o endereço do próximo nó */
};

/* em C, a memória de cada nó é pedida com malloc */
struct No *novo_no(int valor) {
    struct No *no = malloc(sizeof(struct No));
    if (no == NULL) {
        exit(1); /* sem memória: o programa para */
    }
    no->valor = valor;
    no->proximo = NULL;
    return no;
}

struct No *adicionar_no_inicio(struct No *inicio, int valor) {
    struct No *novo = novo_no(valor);
    novo->proximo = inicio; /* 1º: liga o nó novo ao antigo primeiro */
    return novo;            /* 2º: o nó novo passa a ser o início */
}

struct No *adicionar_no_fim(struct No *inicio, int valor) {
    struct No *novo = novo_no(valor);
    if (inicio == NULL) {
        return novo;
    }
    struct No *atual = inicio;
    while (atual->proximo != NULL) {
        atual = atual->proximo;
    }
    atual->proximo = novo;
    return inicio;
}

int contem(struct No *inicio, int valor) {
    for (struct No *atual = inicio; atual != NULL; atual = atual->proximo) {
        if (atual->valor == valor) {
            return 1;
        }
    }
    return 0;
}

struct No *remover(struct No *inicio, int valor) {
    if (inicio == NULL) {
        return NULL;
    }
    if (inicio->valor == valor) {
        struct No *segundo = inicio->proximo;
        free(inicio); /* em C, quem remove devolve a memória */
        return segundo;
    }
    struct No *anterior = inicio;
    while (anterior->proximo != NULL && anterior->proximo->valor != valor) {
        anterior = anterior->proximo;
    }
    if (anterior->proximo != NULL) {
        struct No *removido = anterior->proximo;
        anterior->proximo = removido->proximo; /* pula o nó removido */
        free(removido);
    }
    return inicio;
}

void percorrer(struct No *inicio) {
    for (struct No *atual = inicio; atual != NULL; atual = atual->proximo) {
        printf("%d -> ", atual->valor);
    }
    printf("NULL\n");
}

/* devolve a memória de todos os nós que sobraram */
void liberar(struct No *inicio) {
    while (inicio != NULL) {
        struct No *proximo = inicio->proximo;
        free(inicio);
        inicio = proximo;
    }
}

int main(void) {
    struct No *inicio = NULL;
    inicio = adicionar_no_inicio(inicio, 30);
    inicio = adicionar_no_inicio(inicio, 20);
    inicio = adicionar_no_inicio(inicio, 10);
    printf("adicionando 30, 20 e 10 no início: ");
    percorrer(inicio);

    inicio = adicionar_no_fim(inicio, 40);
    printf("adicionando 40 no fim:             ");
    percorrer(inicio);

    printf("contém 30? %s\n", contem(inicio, 30) ? "sim" : "não");

    inicio = remover(inicio, 20);
    printf("removendo o 20:                    ");
    percorrer(inicio);

    printf("contém 20? %s\n", contem(inicio, 20) ? "sim" : "não");

    liberar(inicio);
    return 0;
}

Saída:

adicionando 30, 20 e 10 no início: 10 -> 20 -> 30 -> NULL
adicionando 40 no fim:             10 -> 20 -> 30 -> 40 -> NULL
contém 30? sim
removendo o 20:                    10 -> 30 -> 40 -> NULL
contém 20? não

O programa em C passou pelo Valgrind sem nenhum vazamento: cada malloc teve o seu free.

Aí você pergunta: preciso criar a lista encadeada na mão?

Para aprender, sim! No dia a dia, as linguagens já trazem estruturas prontas. O Java tem a classe LinkedList, que a documentação descreve como uma lista duplamente encadeada: cada nó se liga ao próximo e também ao anterior, então dá para andar nos dois sentidos. O método addFirst faz o papel do nosso adicionarNoInicio:

// A lista encadeada pronta do Java faz o mesmo papel da nossa
import java.util.LinkedList;

public class Pronta {
    public static void main(String[] args) {
        LinkedList<Integer> lista = new LinkedList<>();
        lista.addFirst(30);
        lista.addFirst(20);
        lista.addFirst(10);
        System.out.println(lista); // [10, 20, 30]
    }
}

O PHP tem a classe SplDoublyLinkedList, também duplamente encadeada. E a lista encadeada serve de base para outras estruturas desta trilha: no próprio PHP, as classes SplStack (a pilha) e SplQueue (a fila) são implementadas com uma lista duplamente encadeada.

Quais são os erros mais comuns com lista encadeada?

O mais traiçoeiro é inverter as duas linhas do adicionarNoInicio. Fiz de propósito:

// O erro da ordem: mover o início antes de ligar o nó novo
public class OrdemErrada {

    static class No {
        int valor;
        No proximo;

        No(int valor) {
            this.valor = valor;
        }
    }

    public static void main(String[] args) {
        No inicio = new No(20); // uma lista com um nó só

        No novo = new No(10);
        inicio = novo;         // ERRADO: moveu o início primeiro...
        novo.proximo = inicio; // ...e o nó novo passou a apontar para ele mesmo

        // mostra só 6 passos, porque essa corrente nunca chega ao null
        No atual = inicio;
        for (int passo = 0; passo < 6; passo++) {
            System.out.print(atual.valor + " -> ");
            atual = atual.proximo;
        }
        System.out.println("...");
        System.out.println("o nó novo aponta para ele mesmo? " + (novo.proximo == novo));
    }
}

Saída:

10 -> 10 -> 10 -> 10 -> 10 -> 10 -> ...
o nó novo aponta para ele mesmo? true

O programa moveu o inicio para o nó novo e só depois mandou o nó novo apontar para o inicio, que agora é ele mesmo. A corrente virou um círculo, e o 20 sumiu: ninguém mais aponta para ele. Sem o limite de 6 passos do for, o percurso nunca terminaria. Ligue primeiro, mova depois!!!

Outros erros comuns:

  • Esquecer a lista vazia. Com o inicio valendo null, um while (atual.proximo != null) tenta ler o proximo de ninguém, e o Java para com NullPointerException: Cannot read field "proximo" because "atual" is null. O nome da variável só aparece quando o programa é compilado com javac -g; sem isso, a mensagem mostra "<local2>". Por isso o adicionarNoFim testa o inicio antes de caminhar.
  • Andar com o próprio inicio. Se o percorrer fizer inicio = inicio.proximo, a lista termina vazia depois de ser mostrada. Use uma variável auxiliar, como o atual.
  • Parar no nó errado na remoção. Para tirar um nó, o remover precisa parar no nó de antes. Parado no próprio nó, não há como voltar para a seta que aponta para ele.
  • Remover sem free em C. Desviar a seta tira o nó da lista, mas não devolve a memória dele. Sem o free, cada remoção vaza um nó.

Agora é com você!

Escolha uma das quatro linguagens e crie na sua lista um método que conta quantos nós ela tem. Uma dica: ele é muito parecido com o percorrer. Antes de digitar, responda no papel: o que muda de um para o outro?

Tente sozinho primeiro, sem pedir o código pronto para ninguém. Se travar, releia o método percorrer com calma, porque a resposta está quase toda ali. Você tem total capacidade de resolver! A resposta eu mostro no próximo artigo.

No próximo artigo vamos falar da fila, a estrutura do “primeiro que chega é o primeiro a ser atendido”. Até lá!

Confiança Sempre!!!

Fontes:

Sobre quem escreve

Walmir Silva

Olá! Sou Walmir, engenheiro de software com MBA em Engenharia de Software e o cérebro por trás do GrowthCode e autor do livro "Além do Código".

Se você acha que programação é apenas sobre escrever código, prepare-se para expandir seus horizontes. Aqui, nós vamos além do código e exploramos as interseções fascinantes entre tecnologia, negócios, artes e filosofia.

Você está em busca de crescimento na carreira? Quer se destacar em um mercado competitivo? Almeja uma vida mais rica em conhecimento e realização? Então você chegou ao lugar certo. No GrowthCode, oferecemos insights profundos, estratégias comprovadas e um toque de sabedoria filosófica para catalisar seu crescimento pessoal e profissional.

Ver todos os artigos →

Continue a conversa

Compartilhe sua perspectiva

O seu endereço de e-mail não será publicado. Campos obrigatórios são marcados com *

Encontre sua próxima resposta

O que você quer aprender?

Preferências de cookies

Os cookies opcionais começam desligados. Você pode mudar a escolha a qualquer momento por esta tela.

NecessáriosSempre ativos

Guardam a sua escolha de cookies e mantêm o site funcionando. Não são usados para publicidade.

Contam visitas e mostram como o site é usado: Google Analytics e Microsoft Clarity, carregados pelo Google Tag Manager. Como esse contêiner também carrega tags de publicidade, as estatísticas só são ativadas junto com Publicidade e marketing.

Exibem anúncios do Google AdSense e medem campanhas e e-mails: pixels da Meta e do TikTok e o Mautic.

Permite que o Google escolha anúncios com base nos seus interesses. Desligado, os anúncios aparecem sem personalização. Depende de Publicidade e marketing.

Também é possível bloquear cookies nas configurações do navegador. Detalhes na Política de privacidade.