Listas Ligadas em Java - Documento
Completo
Índice
1. Introdução
2. Conceitos Fundamentais
3. Diferença entre Listas Ligadas e Arrays
4. Tipos de Listas Ligadas
5. Implementação em Java
6. Classe Nó
7. Classe ListaLigada
8. Operações Básicas
9. Exemplo Prático
10. LinkedList Nativa do Java
11. Comparação entre Implementações
12. Quando Usar Listas Ligadas
13. Conclusão
Introdução
As listas ligadas, também conhecidas como listas encadeadas, são estruturas de dados
fundamentais na ciência da computação e na programação. Elas oferecem uma
alternativa flexível e dinâmica para o armazenamento de dados em comparação com
estruturas baseadas em arrays (vetores).
Neste documento, vamos explorar em detalhes como funcionam as listas ligadas em
Java, desde seus conceitos básicos até sua implementação e operações comuns.
Conceitos Fundamentais
Uma lista ligada é uma estrutura de dados linear e dinâmica composta por uma
sequência de elementos chamados "nós" ou "células". Cada nó contém dois
componentes principais:
1. Dados: O valor ou informação que queremos armazenar
2. Referência: Um ponteiro ou referência para o próximo nó na sequência
A característica fundamental de uma lista ligada é que os elementos não são
armazenados em posições contíguas de memória, como acontece em arrays. Em vez
disso, cada elemento "conhece" apenas o próximo elemento na sequência, formando
uma cadeia de elementos conectados.
Diferença entre Listas Ligadas e Arrays
Para entender melhor o conceito de listas ligadas, é útil compará-las com arrays:
Característica Array Lista Ligada
Contígua (elementos Não contígua (elementos
Alocação de memória
adjacentes) dispersos)
Dinâmico (cresce conforme
Tamanho Fixo (definido na criação)
necessário)
Acesso direto por índice -
Acesso aos elementos Acesso sequencial - O(n)
O(1)
Inserção/remoção no Custoso (requer Eficiente (apenas atualiza
meio deslocamento) referências)
Uso de memória Apenas dados Dados + referências
Tipos de Listas Ligadas
Existem diferentes tipos de listas ligadas:
1. Lista Ligada Simples: Cada nó aponta apenas para o próximo nó na sequência.
2. Lista Ligada Dupla: Cada nó aponta para o próximo nó e para o nó anterior.
3. Lista Ligada Circular: O último nó aponta de volta para o primeiro nó, formando
um círculo.
Neste documento, focaremos principalmente nas listas ligadas simples.
Implementação em Java
Para implementar uma lista ligada em Java, precisamos de duas classes principais:
Classe Nó
A classe Nó é responsável por armazenar o valor do elemento e a referência para o
próximo nó:
public class No {
private Object valor; // Dado armazenado
private No proximo; // Referência para o próximo nó
// Construtor
public No(Object valor) {
[Link] = valor;
[Link] = null; // Inicialmente, não aponta para nenhum outro nó
}
// Getters e setters
public Object getValor() {
return valor;
}
public void setValor(Object valor) {
[Link] = valor;
}
public No getProximo() {
return proximo;
}
public void setProximo(No proximo) {
[Link] = proximo;
}
}
Classe ListaLigada
A classe ListaLigada gerencia a coleção de nós e fornece métodos para adicionar,
remover e buscar elementos:
public class ListaLigada {
private No primeiro; // Referência para o primeiro nó da lista
private No ultimo; // Referência para o último nó da lista
private int tamanho; // Número de elementos na lista
// Construtor
public ListaLigada() {
[Link] = null;
[Link] = null;
[Link] = 0;
}
// Métodos para manipular a lista
// (serão detalhados mais adiante)
}
Operações Básicas
Vamos explorar as operações fundamentais que podemos realizar em uma lista ligada:
1. Adicionar Elementos
Existem três formas principais de adicionar elementos:
a) Adicionar no início da lista
public void adicionarNoInicio(Object valor) {
No novoNo = new No(valor);
if ([Link] == null && [Link] == null) {
// Lista vazia
[Link] = novoNo;
[Link] = novoNo;
} else {
// Lista não vazia
[Link]([Link]);
[Link] = novoNo;
}
[Link]++;
}
b) Adicionar no final da lista
public void adicionar(Object valor) {
No novoNo = new No(valor);
if ([Link] == null && [Link] == null) {
// Lista vazia
[Link] = novoNo;
[Link] = novoNo;
} else {
// Lista não vazia
[Link](novoNo);
[Link] = novoNo;
}
[Link]++;
}
c) Adicionar em uma posição específica
public void adicionar(int posicao, Object valor) {
if (posicao < 0 || posicao > [Link]) {
throw new IllegalArgumentException("Posição inválida");
}
if (posicao == 0) {
// Adicionar no início
[Link](valor);
return;
}
if (posicao == [Link]) {
// Adicionar no final
[Link](valor);
return;
}
// Adicionar no meio
No novoNo = new No(valor);
No anterior = [Link](posicao - 1);
No atual = [Link]();
[Link](novoNo);
[Link](atual);
[Link]++;
}
2. Remover Elementos
A remoção de elementos também pode ser feita de diferentes formas:
a) Remover do início
public Object removerDoInicio() {
if ([Link] == null) {
// Lista vazia
return null;
}
Object valorRemovido = [Link]();
if ([Link] == [Link]) {
// Lista com apenas um elemento
[Link] = null;
[Link] = null;
} else {
// Lista com mais de um elemento
[Link] = [Link]();
}
[Link]--;
return valorRemovido;
}
b) Remover de uma posição específica
public Object remover(int posicao) {
if (posicao < 0 || posicao >= [Link]) {
throw new IllegalArgumentException("Posição inválida");
}
if (posicao == 0) {
// Remover do início
return [Link]();
}
// Remover do meio ou do final
No anterior = [Link](posicao - 1);
No atual = [Link]();
Object valorRemovido = [Link]();
if (atual == [Link]) {
// Remover do final
[Link](null);
[Link] = anterior;
} else {
// Remover do meio
[Link]([Link]());
}
[Link]--;
return valorRemovido;
}
3. Buscar Elementos
A busca em uma lista ligada é sempre sequencial:
public Object buscar(int posicao) {
if (posicao < 0 || posicao >= [Link]) {
throw new IllegalArgumentException("Posição inválida");
}
return [Link](posicao).getValor();
}
private No buscarNo(int posicao) {
if (posicao < 0 || posicao >= [Link]) {
throw new IllegalArgumentException("Posição inválida");
}
No atual = [Link];
for (int i = 0; i < posicao; i++) {
atual = [Link]();
}
return atual;
}
4. Verificar se a Lista Contém um Elemento
public boolean contem(Object valor) {
No atual = [Link];
while (atual != null) {
if ([Link]().equals(valor)) {
return true;
}
atual = [Link]();
}
return false;
}
5. Obter o Tamanho da Lista
public int tamanho() {
return [Link];
}
Exemplo Prático
Vamos ver um exemplo prático de como usar nossa implementação de lista ligada:
public class ExemploListaLigada {
public static void main(String[] args) {
// Criando uma nova lista ligada
ListaLigada lista = new ListaLigada();
[Link]("=== Demonstração de Lista Ligada em Java ===");
// Verificando se a lista está vazia
[Link]("\n1. Lista inicial:");
[Link]("Lista: " + lista);
[Link]("Tamanho: " + [Link]());
[Link]("Está vazia? " + [Link]());
// Adicionando elementos no final da lista
[Link]("\n2. Adicionando elementos no final da lista:");
[Link]("Java");
[Link]("Python");
[Link]("C++");
[Link]("Lista após adições: " + lista);
[Link]("Tamanho: " + [Link]());
[Link]("Está vazia? " + [Link]());
// Adicionando elementos no início da lista
[Link]("\n3. Adicionando elementos no início da lista:");
[Link]("JavaScript");
[Link]("TypeScript");
[Link]("Lista após adições no início: " + lista);
[Link]("Tamanho: " + [Link]());
// Adicionando elementos em posições específicas
[Link]("\n4. Adicionando elementos em posições específicas:");
[Link](2, "Ruby");
[Link](4, "Go");
[Link]("Lista após adições em posições específicas: " + lista);
[Link]("Tamanho: " + [Link]());
// Buscando elementos por posição
[Link]("\n5. Buscando elementos por posição:");
[Link]("Elemento na posição 0: " + [Link](0));
[Link]("Elemento na posição 3: " + [Link](3));
[Link]("Elemento na posição 6: " + [Link](6));
// Verificando se a lista contém determinados elementos
[Link]("\n6. Verificando se a lista contém elementos:");
[Link]("Contém 'Java'? " + [Link]("Java"));
[Link]("Contém 'PHP'? " + [Link]("PHP"));
[Link]("Contém 'Ruby'? " + [Link]("Ruby"));
// Removendo elementos do início
[Link]("\n7. Removendo elementos do início:");
Object removido = [Link]();
[Link]("Elemento removido do início: " + removido);
[Link]("Lista após remoção do início: " + lista);
[Link]("Tamanho: " + [Link]());
// Removendo elementos de posições específicas
[Link]("\n8. Removendo elementos de posições específicas:");
removido = [Link](2);
[Link]("Elemento removido da posição 2: " + removido);
[Link]("Lista após remoção: " + lista);
removido = [Link]([Link]() - 1);
[Link]("Elemento removido da última posição: " + removido);
[Link]("Lista após remoção: " + lista);
[Link]("Tamanho: " + [Link]());
// Esvaziando a lista
[Link]("\n9. Esvaziando a lista:");
while (![Link]()) {
removido = [Link]();
[Link]("Removido: " + removido);
}
[Link]("Lista após esvaziar: " + lista);
[Link]("Tamanho: " + [Link]());
[Link]("Está vazia? " + [Link]());
[Link]("\n=== Fim da demonstração ===");
}
}
A saída deste exemplo seria:
=== Demonstração de Lista Ligada em Java ===
1. Lista inicial:
Lista: []
Tamanho: 0
Está vazia? true
2. Adicionando elementos no final da lista:
Lista após adições: [Java, Python, C++]
Tamanho: 3
Está vazia? false
3. Adicionando elementos no início da lista:
Lista após adições no início: [TypeScript, JavaScript, Java, Python, C++]
Tamanho: 5
4. Adicionando elementos em posições específicas:
Lista após adições em posições específicas: [TypeScript, JavaScript, Ruby, Java, Go,
Python, C++]
Tamanho: 7
5. Buscando elementos por posição:
Elemento na posição 0: TypeScript
Elemento na posição 3: Java
Elemento na posição 6: C++
6. Verificando se a lista contém elementos:
Contém 'Java'? true
Contém 'PHP'? false
Contém 'Ruby'? true
7. Removendo elementos do início:
Elemento removido do início: TypeScript
Lista após remoção do início: [JavaScript, Ruby, Java, Go, Python, C++]
Tamanho: 6
8. Removendo elementos de posições específicas:
Elemento removido da posição 2: Java
Lista após remoção: [JavaScript, Ruby, Go, Python, C++]
Elemento removido da última posição: C++
Lista após remoção: [JavaScript, Ruby, Go, Python]
Tamanho: 4
9. Esvaziando a lista:
Removido: JavaScript
Removido: Ruby
Removido: Go
Removido: Python
Lista após esvaziar: []
Tamanho: 0
Está vazia? true
=== Fim da demonstração ===
LinkedList Nativa do Java
Java oferece implementações nativas de listas ligadas através da classe LinkedList do
pacote [Link] . Esta classe implementa as interfaces List e Deque , oferecendo
funcionalidades tanto de lista quanto de fila de duas pontas.
Exemplo de uso da LinkedList nativa:
import [Link];
public class ExemploLinkedListNativa {
public static void main(String[] args) {
// Criando uma LinkedList de Strings
LinkedList<String> lista = new LinkedList<>();
[Link]("=== Demonstração da LinkedList Nativa do Java ===");
// Verificando se a lista está vazia
[Link]("\n1. Lista inicial:");
[Link]("Lista: " + lista);
[Link]("Tamanho: " + [Link]());
[Link]("Está vazia? " + [Link]());
// Adicionando elementos no final da lista
[Link]("\n2. Adicionando elementos no final da lista:");
[Link]("Java");
[Link]("Python");
[Link]("C++");
[Link]("Lista após adições: " + lista);
[Link]("Tamanho: " + [Link]());
[Link]("Está vazia? " + [Link]());
// Adicionando elementos no início da lista
[Link]("\n3. Adicionando elementos no início da lista:");
[Link]("JavaScript");
[Link]("TypeScript");
[Link]("Lista após adições no início: " + lista);
[Link]("Tamanho: " + [Link]());
// Adicionando elementos em posições específicas
[Link]("\n4. Adicionando elementos em posições específicas:");
[Link](2, "Ruby");
[Link](4, "Go");
[Link]("Lista após adições em posições específicas: " + lista);
[Link]("Tamanho: " + [Link]());
// Buscando elementos por posição
[Link]("\n5. Buscando elementos por posição:");
[Link]("Elemento na posição 0: " + [Link](0));
[Link]("Elemento na posição 3: " + [Link](3));
[Link]("Elemento na posição 6: " + [Link](6));
// Verificando se a lista contém determinados elementos
[Link]("\n6. Verificando se a lista contém elementos:");
[Link]("Contém 'Java'? " + [Link]("Java"));
[Link]("Contém 'PHP'? " + [Link]("PHP"));
[Link]("Contém 'Ruby'? " + [Link]("Ruby"));
// Removendo elementos do início
[Link]("\n7. Removendo elementos do início:");
String removido = [Link]();
[Link]("Elemento removido do início: " + removido);
[Link]("Lista após remoção do início: " + lista);
[Link]("Tamanho: " + [Link]());
// Removendo elementos de posições específicas
[Link]("\n8. Removendo elementos de posições específicas:");
removido = [Link](2);
[Link]("Elemento removido da posição 2: " + removido);
[Link]("Lista após remoção: " + lista);
removido = [Link]();
[Link]("Elemento removido da última posição: " + removido);
[Link]("Lista após remoção: " + lista);
[Link]("Tamanho: " + [Link]());
// Recursos adicionais da LinkedList nativa
[Link]("\n9. Recursos adicionais da LinkedList nativa:");
[Link]("Primeiro elemento: " + [Link]());
[Link]("Último elemento: " + [Link]());
// Usando como pilha (LIFO - Last In, First Out)
[Link]("\n10. Usando LinkedList como pilha (LIFO):");
[Link]("Elemento no topo");
[Link]("Lista após push: " + lista);
String topo = [Link]();
[Link]("Elemento removido do topo: " + topo);
[Link]("Lista após pop: " + lista);
// Usando como fila (FIFO - First In, First Out)
[Link]("\n11. Usando LinkedList como fila (FIFO):");
[Link]("Último da fila");
[Link]("Lista após offer: " + lista);
String primeiro = [Link]();
[Link]("Elemento removido do início: " + primeiro);
[Link]("Lista após poll: " + lista);
// Esvaziando a lista
[Link]("\n12. Esvaziando a lista:");
[Link]();
[Link]("Lista após clear: " + lista);
[Link]("Tamanho: " + [Link]());
[Link]("Está vazia? " + [Link]());
[Link]("\n=== Fim da demonstração ===");
}
}
Comparação entre Implementações
Semelhanças
1. Estrutura básica: Ambas implementações seguem o conceito fundamental de lista
ligada, onde cada elemento conhece o próximo na sequência.
2. Operações básicas: Ambas oferecem operações fundamentais como:
3. Adicionar elementos (no início, no final e em posições específicas)
4. Remover elementos (do início, do final e de posições específicas)
5. Buscar elementos por posição
6. Verificar se a lista contém determinados elementos
7. Verificar o tamanho da lista e se está vazia
8. Comportamento dinâmico: Ambas crescem e diminuem conforme necessário,
sem necessidade de redimensionamento.
Diferenças
1. Tipagem genérica:
2. A LinkedList nativa usa generics para garantir tipagem segura
3. Nossa implementação personalizada usa Object , exigindo casting ao recuperar
elementos
4. Funcionalidades adicionais:
5. A LinkedList nativa implementa as interfaces List e Deque , oferecendo
funcionalidades tanto de lista quanto de fila de duas pontas
6. A LinkedList nativa pode ser usada como pilha (LIFO) com métodos como push()
e pop()
7. A LinkedList nativa pode ser usada como fila (FIFO) com métodos como offer() e
poll()
8. Implementação interna:
9. A LinkedList nativa é uma lista duplamente ligada (cada nó conhece tanto o
próximo quanto o anterior)
10. Nossa implementação personalizada é uma lista simplesmente ligada (cada nó
conhece apenas o próximo)
11. Métodos de acesso:
12. A LinkedList nativa oferece métodos como getFirst() e getLast() para acesso
rápido ao primeiro e último elementos
13. Nossa implementação personalizada requer percorrer a lista para acessar o último
elemento (exceto que mantemos uma referência para ele)
14. Otimizações:
15. A LinkedList nativa é altamente otimizada para desempenho
16. Nossa implementação personalizada é mais simples e focada em demonstrar o
conceito
17. Integração com o framework de coleções:
18. A LinkedList nativa se integra com o framework de coleções do Java, permitindo
uso com iteradores, streams, etc.
19. Nossa implementação personalizada não oferece essa integração
Quando Usar Listas Ligadas
As listas ligadas são mais adequadas nas seguintes situações:
1. Quando o tamanho da coleção é desconhecido ou pode variar significativamente.
2. Quando as operações de inserção e remoção no meio da coleção são frequentes.
3. Quando não é necessário acesso aleatório rápido aos elementos.
4. Quando a memória é uma preocupação e você deseja alocar apenas o espaço
necessário.
Use a implementação personalizada quando:
1. Quiser entender como as listas ligadas funcionam internamente
2. Precisar de uma implementação específica não disponível na biblioteca padrão
3. Estiver aprendendo sobre estruturas de dados e algoritmos
Use a LinkedList nativa quando:
1. Estiver desenvolvendo aplicações reais que precisam de desempenho e
confiabilidade
2. Precisar de funcionalidades adicionais como uso como pilha ou fila
3. Precisar de integração com o framework de coleções do Java
4. Precisar de tipagem genérica segura
Conclusão
As listas ligadas são estruturas de dados fundamentais que oferecem flexibilidade e
eficiência em determinadas operações. Embora não sejam a melhor escolha para todos
os cenários, elas têm seu lugar no arsenal de estruturas de dados de qualquer
programador.
Em Java, você pode optar por implementar sua própria lista ligada para entender
melhor seu funcionamento ou utilizar a implementação nativa LinkedList para
aplicações práticas. O conhecimento de como as listas ligadas funcionam internamente
é valioso para tomar decisões informadas sobre qual estrutura de dados usar em
diferentes situações.
A implementação nativa LinkedList do Java é mais robusta, eficiente e rica em
funcionalidades do que nossa implementação personalizada. No entanto, implementar
nossa própria lista ligada é um excelente exercício para entender os conceitos
fundamentais por trás dessa estrutura de dados.
Para aplicações reais, é geralmente recomendado usar a implementação nativa, a
menos que haja requisitos muito específicos que justifiquem uma implementação
personalizada.