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.
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.
Vetor
Lista encadeada
Como os valores ficam na memória
Lado a lado
Espalhados, ligados por referências
Acessar a posição 500
Direto, pelo índice
Precisa passar pelos 500 nós que vêm antes
Inserir no início
Precisa empurrar todos os valores uma posição
Cria um nó e ajusta uma referência
Memória por elemento
Só o valor
O 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
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));
}
}
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.
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
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.
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))
<?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;
/* 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 classeSplDoublyLinkedList, 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á!
Oracle, documentação do Java 21. Classe LinkedList (em inglês), com a lista duplamente encadeada da biblioteca padrão e o método addFirst, que insere no início.
Oracle. The Java Language Specification, Java SE 21, capítulo 4 (em inglês), com as referências como ponteiros para objetos, o null que não aponta para nenhum objeto e o valor inicial null das propriedades de tipo objeto (seções 4.3.1 e 4.12.5).
Documentação do Java SE 21. Classe ArrayList (em inglês, cópia hospedada pela EPFL), com o vetor redimensionável, o get em tempo constante e o add em uma posição, que empurra os elementos seguintes para a direita.
OpenJDK. JEP 358: Helpful NullPointerExceptions (em inglês), com a mensagem que diz qual variável era null e os nomes de variáveis locais que só aparecem com javac -g.
Os exemplos foram executados em Java 21, Python 3.13, PHP 8.3 e GCC 13. A medição de tempo foi feita em uma máquina virtual com processador Intel Xeon de 2,1 GHz; em outra máquina, os números serão outros.
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.
Usamos cookies necessários para o site funcionar. Com a sua permissão, também usamos cookies de estatística e de publicidade e marketing. Você pode mudar a escolha quando quiser em Preferências de cookies. Política de privacidade
Continue a conversa