DEV Community: Yesmin Marie Soret Lahoud

Conhecendo a classe LinkedList do Java

Yesmin Marie Soret Lahoud — Tue, 01 Nov 2022 14:09:00 +0000

Neste artigo apresentarei algumas características da classe LinkedList, também explanarei um pouco sobre seu funcionamento e farei algumas comparações entre a mesma e a classe ArrayList.

Se você quiser saber mais sobre a classe ArrayList, escrevi um artigo sobre esse assunto e você poderá consultá-lo clicando aqui.

Como funciona a classe LinkedList do Java?

Assim como ArrayList, a classe LinkedList também implementa a interface List. Veja no diagrama abaixo a hierarquia de interfaces e classes. As linhas cheias representam “extends” e as linhas pontilhadas “implements”:

Sendo assim, os mesmos métodos disponíveis para ArrayList também estão disponíveis para LinkedList, mas implementados de forma diferente.

De forma distinta da classe ArrayList, que usa um array internamente, a classe LinkedList trabalha com lista duplamente encadeada. Seu funcionamento ocorre da seguinte forma: cada elemento da lista fica armazenado em um nó e cada nó possui dois ponteiros, um localizado à esquerda e outro à direita. Esses ponteiros guardam a posição do nó anterior e do nó posterior.

A imagem a seguir ilustra como é um nó do LinkedList:

A próxima imagem mostra o funcionamento de uma lista duplamente encadeada, onde cada nó aponta para o elemento anterior e posterior. Veja que o primeiro nó não possui posição para o elemento anterior (null). Assim como último elemento não possui posição para o próximo.

Dessa maneira, diferentemente do ArrayList, que armazena os elementos de forma consecutiva (um ao lado do outro), no LinkedList os elementos ficam espalhados na memória, mas cada um deles sabe quem é seu antecessor e seu sucessor por meio dos ponteiros que fazem as conexões entre eles.

Sendo assim, adicionar ou remover elementos no LinkedList é mais rápido do que no ArrayList. Isso porque na lista encadeada, não há o deslocamento dos elementos após cada operação de adição e remoção, bastando apenas alterar as referências dos ponteiros, indicando quem passou a ser o elemento anterior e posterior.

Como funciona a adição de elementos no LinkedList?

Como exemplo, vamos supor que temos um LinkedList onde cada nó armazena os seguinte nomes:

Vamos adicionar um novo elemento contendo o nome “Rafael” após o índice 1, que contém o nome “Pedro” e que está apontando para “Maria” (índice 2):

Repare que foi apenas necessário mudar os apontamentos dos nós:

“Pedro”, que antes apontava para “Maria”, agora está apontando para “Rafael”.
“Maria”, que antes apontava para “Pedro” como seu antecessor, agora passa a apontar para “Rafael”.
“Rafael” agora se tornou o elemento de índice 2, passando a apontar para “Pedro” como seu antecessor, e “Maria” como sucessor.
“Maria”, que antes era o elemento de índice 2, agora passa a ser o índice 3.
“João” agora ocupa o índice 4.

Como funciona a remoção de elementos no LinkedList?

Usando como exemplo a lista abaixo, vamos remover o elemento que contém o nome “Pedro”:

Lista após a remoção:

Veja que agora “Ana” passa a apontar para “Rafael” e vice-versa. “Rafael” passa a ter o índice 1, “Maria” agora está no índice 2 e “João” no índice 3. O Garbage Collector do Java se encarrega de liberar a memória que o elemento removido ocupava.

Outros aspectos que diferem LinkedList de ArrayList

Até aqui, vimos que tanto adicionar quanto remover elementos são tarefas que o LinkedList realiza com mais eficiência do que o ArrayList. No entanto, o LinkedList é mais lento para acessar elementos da lista. Se por exemplo, quiséssemos acessar a posição 10, teríamos que percorrer desde o início até a posição que queremos.

Outro ponto que difere um ArrayList de um LinkedList é que neste, não é possível passar a capacidade inicial por parâmetro no construtor quando o inicializamos. Como o LinkedList se baseia no modelo de lista encadeada, o espaço em memória não é alocado antes dos itens serem inseridos e sua capacidade inicial é zero.

No entanto, assim como no ArrayList, podemos criar uma lista a partir de outra já existente, passando a lista base por parâmetro no construtor. Exemplo:

LinkedList<String> lista = new LinkedList<>();
lista.add("Maria");
lista.add("Pedro");
LinkedList<String> novaLista = new LinkedList<>(lista);
System.out.println(novaLista);

Formas de Inicializar um LinkedList

Assim como no ArrayList, podemos utilizar o polimorfismo e declarar uma referência da interface List e instanciar a classe LinkedList:

List<String> lista = new LinkedList<>();

Mas se quisermos utilizar os métodos específicos do LinkedList, temos que declarar uma referência da própria classe LinkedList:

LinkedList<String> lista = new LinkedList<>();

Métodos específicos do LinkedList

Além dos métodos implementados da interface List, como add(item), remove(posição), set(posição, item), get(posição), dentre outros. Também temos alguns métodos específicos que a classe LinkedList implementa da interface Deque. A seguir estão listados alguns deles:

addFirst(item) -> adiciona um elemento no início da lista;
addLast(item) -> adiciona um elemento no final da lista;
getFirst() -> retorna o primeiro elemento da lista;
getLast() -> retorna o último elemento da lista;
removeFirst() -> remove o primeiro elemento da lista e o retorna;
removeLast() -> remove o último elemento da lista e o retorna;

Exemplos de como utilizar LinkedList

Este primeiro exemplo é igual a outro que inseri no artigo que escrevi sobre ArrayList. Estou colocando neste artigo também para mostrar que podemos usar os mesmos métodos que estão disponíveis para ArrayList, pois ambos implementam a interface List.

import java.util.Iterator;
import java.util.LinkedList;

public class TesteLinkedList {
    public static void main(String[] args) {

        // 1) Primeiro, vamos instanciar uma LinkedList;
        LinkedList<String> cidades = new LinkedList<>();

        // 2) Depois, vamos adicionar cinco cidades
        // usando o método add(item);
        cidades.add("São Paulo");
        cidades.add("Rio de Janeiro");
        cidades.add("Recife");
        cidades.add("Manaus");
        cidades.add("Curitiba");

        // 3) Percorreremos a lista e exibiremos
        // essas cidades usando o for.
        // Aqui serão utilizados os métodos get(posição) e size()
        System.out.println("Percorrendo a lista usando for:");
        for(int i = 0; i < cidades.size(); i++){
            System.out.println("Posição " + i + " - " + cidades.get(i));
        }

        // 4) Com o método remove(posição),
        // removeremos a cidade da posição 3 (Manaus);
        cidades.remove(3);

        // 5) Com o método add(posição, item),
        // adicionaremos a cidade “Florianópolis” na posição zero;
        cidades.add(0, "Florianópolis");

        // 6) Vamos percorrer novamente a lista usando for-each;
        System.out.println("==================");
        System.out.println("Percorrendo a lista usando for-each:");
        int i = 0;
        for(String cidade : cidades){
            System.out.println("Posição " + i + " - " + cidade);
            i++;
        }

        // 7) Agora, usaremos o indexOf(item) para retornar
        // a posição da cidade “Recife” e, com o método
        // set(posição, item) substituiremos "Recife"
        // por “Salvador”;
        int posicaoCidade = cidades.indexOf("Recife");
        cidades.set(posicaoCidade, "Salvador");

        // 8) Agora, vamos percorrer a lista novamente,
        // mas usando Iterator.
        System.out.println("==================");
        System.out.println("Percorrendo a lista usando Iterator:");
        i = 0;
        Iterator<String> iterator = cidades.iterator();
        // o método hasNext() verifica se existe
        // um próximo elemento para ser iterado
        while (iterator.hasNext()){
            // o método next() retorna o próximo elemento
            System.out.println("Posição " + i + " - " + iterator.next());
            i++;
        }
    }
}

Saída:

Percorrendo a lista usando for:
Posição 0 - São Paulo
Posição 1 - Rio de Janeiro
Posição 2 - Recife
Posição 3 - Manaus
Posição 4 - Curitiba
==================
Percorrendo a lista usando for-each:
Posição 0 - Florianópolis
Posição 1 - São Paulo
Posição 2 - Rio de Janeiro
Posição 3 - Recife
Posição 4 - Curitiba
==================
Percorrendo a lista usando Iterator:
Posição 0 - Florianópolis
Posição 1 - São Paulo
Posição 2 - Rio de Janeiro
Posição 3 - Salvador
Posição 4 - Curitiba

Neste segundo exemplo, vamos utilizar alguns dos métodos específicos do LinkedList:

import java.util.Iterator;
import java.util.LinkedList;

public class TesteLinkedListMetodosEspecificos {
    public static void main(String[] args) {

        // 1) Primeiro, vamos instanciar uma LinkedList;
        LinkedList<String> nomes = new LinkedList<>();

        // 2) Depois, vamos adicionar quatro nomes
        // usando o método add(item);
        nomes.add("Ana");
        nomes.add("Pedro");
        nomes.add("Maria");
        nomes.add("João");

        // 3) Com o método addFirst(item) vamos
        // adicionar Marcelo no início da lista
        nomes.addFirst("Marcelo");

        // 4) Com o método addLast(item) vamos
        // adicionar Bruna no final da lista
        nomes.addLast("Bruna");

        // 5) Vamos percorrer a lista usando for-each;
        System.out.println("Percorrendo a lista usando for-each:");
        int i = 0;
        for(String nome : nomes){
            System.out.println("Posição " + i + " - " + nome);
            i++;
        }

        System.out.println("==================");

        // 6) Usando o método getFirst(),
        // vamos retornar o primeiro elemento da lista
        System.out.println("Primeiro elemento: " + nomes.getFirst());

        // 8) Usando o método getLast(),
        // vamos retornar o último elemento da lista
        System.out.println("Último elemento: " + nomes.getLast());

        // 9) Com o método removeFirst() vamos remover
        // o primeiro elemento da lista
        nomes.removeFirst();

        // 10) Com o método removeLast() vamos remover
        // o último elemento da lista
        nomes.removeLast();

        // 11) vamos percorrer a lista novamente
        System.out.println("==================");
        System.out.println("Percorrendo a lista usando Iterator:");
        i = 0;
        Iterator<String> iterator = nomes.iterator();
        while (iterator.hasNext()){
            System.out.println("Posição " + i + " - " + iterator.next());
            i++;
        }
    }
}

Saída:

Percorrendo a lista usando for-each:
Posição 0 - Marcelo
Posição 1 - Ana
Posição 2 - Pedro
Posição 3 - Maria
Posição 4 - João
Posição 5 - Bruna
==================
Primeiro elemento: Marcelo
Último elemento: Bruna
==================
Percorrendo a lista usando Iterator:
Posição 0 - Ana
Posição 1 - Pedro
Posição 2 - Maria
Posição 3 - João

Quando usar ArrayList e quando usar LinkedList?

Se você for utilizar com frequência operações de adicionar e remover elementos da lista, o mais indicado seria usar LinkedList, pois como vimos, esta classe consegue realizar essas operações com mais eficiência do que a classe ArrayList.

Agora, se você precisar acessar elementos da lista com mais frequência, a melhor escolha seria usar a classe ArrayList, pois ela faz isso de maneira muito mais rápida do que a classe LinkedList.

Considerações Finais

Neste artigo foi apresentado o funcionamento da classe LinkedList e foram abordadas as principais diferenças entre esta classe e a ArrayList. Vimos também que podemos utilizar os mesmos métodos de ArrayList, já que as duas implementam a interface List, e conhecemos mais alguns métodos específicos de LinkedList. Além disso, vimos em quais momentos é mais adequado utilizar um ou outro.

Espero ter ajudado e até a próxima!

Utilização da Classe ArrayList do Java para Manipulação de Vetores

Yesmin Marie Soret Lahoud — Thu, 27 Oct 2022 17:54:14 +0000

Neste artigo vou apresentar algumas características da classe ArrayList do Java e demonstrar a utilização de alguns dos métodos mais utilizados.

Por que utilizar a classe ArrayList?

Quando utilizamos o array padrão do Java, precisamos determinar qual será o seu tamanho no momento de sua criação. Esse tamanho é fixo e, uma vez criado, não conseguimos alterar o número de elementos. Se por exemplo, precisarmos adicionar mais um elemento, é necessário criar um novo array e copiar todos os elementos que estão no antigo array para o novo. Essa prática acaba sendo muito trabalhosa e também provoca uma perda de desempenho.

A classe ArrayList serve justamente para solucionar esse problema, pois ela permite que sejam criados arrays dinâmicos, ou seja, se precisarmos adicionar mais um elemento, o ArrayList faz esse redimensionamento de forma automática.

Hierarquia da Classe ArrayList

A classe ArrayList faz parte do Java Collections, que pertence ao pacote java.util. O ArrayList é uma implementação da interface List, que por sua vez estende a interface Collection. No diagrama abaixo, as linhas cheias representam “extends” e as linhas pontilhadas “implements”:

Além dos métodos herdados de Collection, a interface List fornece métodos que permitem a manipulação de elementos com base na posição (ou índice) em que eles se encontram. Assim como nos vetores, o índice começa em zero.

Alguns dos principais métodos

add(item) -> adiciona um novo elemento ao ArrayList. O elemento é inserido no final da lista;
add(posição, item) -> insere o elemento em uma posição específica da lista;
remove(posição) -> remove o elemento de uma determinada posição da lista;
set(posição, item) -> substitui um elemento em uma posição específica;
get(posição) -> retorna o elemento da posição especificada;
indexOf(item) -> retorna a posição da primeira ocorrência do elemento especificado;
contains(item) -> retorna verdadeiro caso a lista contenha o elemento especificado. Caso contrário, retorna falso;
clear() -> remove todos os elementos da lista;
isEmpty()-> retorna verdadeiro se a lista estiver vazia. Caso contrário retorna falso;
size()-> retorna a quantidade de elementos da lista.

Formas de inicializar um ArrayList

Podemos inicializar o ArrayList sem especificar o tipo dos elementos que a lista conterá, como mostrado a seguir:

ArrayList lista = new ArrayList();

Esse formato permite que adicionemos elementos de qualquer tipo na lista. No exemplo abaixo, repare que os tipos dos dados inseridos estão misturados:

import java.util.ArrayList;

public class TesteArrayList {
    public static void main(String[] args) {
        ArrayList lista = new ArrayList();
        lista.add("Ana");
        lista.add(123);
        lista.add("Maria");
        lista.add(12.34);
        lista.add("Paulo");

        System.out.println(lista);
    }
}

Saída:

[Ana, 123, Maria, 12.34, Paulo]

Se por exemplo, precisássemos armazenar o elemento de determinada posição em uma variável, seria necessário fazer o type cast, indicando o tipo do Objeto. No exemplo abaixo, estamos tentando armazenar o elemento da posição 1 na String nome, no entanto esse elemento é um valor inteiro(123), o que acabará causando um “run time exception” no momento da execução.

import java.util.ArrayList;

public class TesteArrayList {
    public static void main(String[] args) {
        ArrayList lista = new ArrayList();
        lista.add("Ana");
        lista.add(123);
        lista.add("Maria");
        lista.add(12.34);
        lista.add("Paulo");

        // vai causar run time exception, 
        // pois o elemento da posição 1 é um inteiro(123)
        String nome = (String) lista.get(1); 

        System.out.println(lista);
    }
}

Saída:

java.lang.ClassCastException
class java.lang.Integer cannot be cast to class java.lang.String

Portanto, para evitar problemas, o ideal é não permitirmos que o ArrayList armazene elementos com tipos misturados. Para limitar o ArrayList podemos usar o Generics, inserindo o tipo de objeto que a lista irá armazenar.

Obs.: Não são aceitos tipos primitivos. Por exemplo, para inserir valores inteiros, usamos Integer ao invés de int.

ArrayList<Integer> lista = new ArrayList<>();

Veja um exemplo em que criamos uma lista de elementos inteiros.

import java.util.ArrayList;

public class TesteArrayList {
    public static void main(String[] args) {
        ArrayList<Integer> lista = new ArrayList<>();
        lista.add(1);
        lista.add(2);
        lista.add(3);

        System.out.println(lista);
    }
}

Saída:

[1, 2, 3]

Podemos também utilizar o polimorfismo e declarar uma referência da interface List e instanciar a classe ArrayList.

List<Integer> lista = new ArrayList<>();

A vantagem de declararmos o ArrayList desta maneira é que podemos a qualquer momento, caso seja necessário, alterar a classe que implementa a interface List. Por exemplo, ao invés de utilizar a classe ArrayList podemos optar por usar a LinkedList ou a Vector, pois ambas implementam a interface List.

List<Integer> lista = new LinkedList<>();

Caso já saibamos quantos elementos o array terá, podemos passar a capacidade inicial por parâmetro no construtor. Isso é muito recomendado nestes casos, pois evitamos desperdício de memória. No exemplo abaixo, estamos iniciando nosso ArrayList com 5 posições. Caso seja necessário adicionar mais elementos posteriormente, o redimensionamento é feito de forma automática.

List<String> lista = new ArrayList<>(5);

Podemos ainda criar uma lista a partir de outra já existente. Basta passarmos a lista base por parâmetro no construtor:

List<String> lista = new ArrayList<>(5);
lista.add("Maria");
lista.add("Pedro");
List<String> novaLista = new ArrayList<>(lista);

Exemplo de como utilizar ArrayList

No exemplo a seguir, será demonstrado como usar alguns dos métodos fornecidos pela classe ArrayList.

Primeiro, vamos instanciar uma lista;
Depois, vamos adicionar cinco cidades usando o método add(item);
Percorreremos a lista e exibiremos essas cidades usando o for. Aqui serão utilizados os métodos get(posição) e size();
Com o método remove(posição), removeremos a cidade da posição 3 (Manaus);
Com o método add(posição, item), adicionaremos a cidade “Florianópolis” na posição zero;
Vamos percorrer novamente a lista usando for-each;
Agora usaremos o indexOf(item) para retornar a posição da cidade “Recife” e, com o método set(posição, item) substituiremos “Recife” por “Salvador”;
Agora vamos percorrer a lista novamente, mas usando Iterator. (O Iterator é um padrão de projeto que permite iterar entre os elementos dentro da coleção).

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

public class TesteArrayList {
    public static void main(String[] args) {

        // 1) Primeiro, vamos instanciar uma lista;
        List<String> cidades = new ArrayList<>();

        // 2) Depois, vamos adicionar cinco cidades 
        // usando o método add(item);
        cidades.add("São Paulo");
        cidades.add("Rio de Janeiro");
        cidades.add("Recife");
        cidades.add("Manaus");
        cidades.add("Curitiba");

        // 3) Percorreremos a lista e exibiremos 
        // essas cidades usando o for.
        // Aqui serão utilizados os métodos get(posição) e size()
        System.out.println("Percorrendo a lista usando for:");
        for(int i = 0; i < cidades.size(); i++){
            System.out.println("Posição " + i + " - " + cidades.get(i));
        }

        // 4) Com o método remove(posição), 
        // removeremos a cidade da posição 3 (Manaus);
        cidades.remove(3);

        // 5) Com o método add(posição, item), 
        // adicionaremos a cidade “Florianópolis” na posição zero;
        cidades.add(0, "Florianópolis");

        // 6) Vamos percorrer novamente a lista usando for-each;
        System.out.println("==================");
        System.out.println("Percorrendo a lista usando for-each:");
        int i = 0;
        for(String cidade : cidades){
            System.out.println("Posição " + i + " - " + cidade);
            i++;
        }

        // 7) Agora usaremos o indexOf(item) para retornar 
        // a posição da cidade “Recife” e, com o método 
        // set(posição, item) substituiremos "Recife" 
        // por “Salvador”;
        int posicaoCidade = cidades.indexOf("Recife");
        cidades.set(posicaoCidade, "Salvador");

        // 8) Agora vamos percorrer a lista novamente, 
        // mas usando Iterator.
        System.out.println("==================");
        System.out.println("Percorrendo a lista usando Iterator:");
        i = 0;
        Iterator<String> iterator = cidades.iterator();
        // o método hasNext() verifica se existe 
        // um próximo elemento para ser iterado
        while (iterator.hasNext()){
            // o método next() retorna o próximo elemento
            System.out.println("Posição " + i + " - " + iterator.next()); 
            i++;
        }
    }
}

A saída após executar a aplicação será:

Percorrendo a lista usando for:
Posição 0 - São Paulo
Posição 1 - Rio de Janeiro
Posição 2 - Recife
Posição 3 - Manaus
Posição 4 - Curitiba
==================
Percorrendo a lista usando for-each:
Posição 0 - Florianópolis
Posição 1 - São Paulo
Posição 2 - Rio de Janeiro
Posição 3 - Recife
Posição 4 - Curitiba
==================
Percorrendo a lista usando Iterator:
Posição 0 - Florianópolis
Posição 1 - São Paulo
Posição 2 - Rio de Janeiro
Posição 3 - Salvador
Posição 4 - Curitiba

Vantagens e Desvantagens do ArrayList

O uso do ArayList é mais indicado quando queremos apenas adicionar elementos em uma lista para posteriormente fazer a iteração. Adicionar elementos ao final de uma lista é bastante simples (isso caso a capacidade de armazenamento do array não tenha sido ultrapassado). O acesso a qualquer elemento do array pelo seu índice também é feito de forma bastante eficiente, ou seja, quando usamos o método get(posição), o tempo para acessar um elemento que esteja no início, ou no meio, ou no fim é praticamente o mesmo, independente do tamanho do vetor.

No entanto, o ArrayList na verdade usa o array padrão internamente, ou seja, quando a capacidade do array acaba, ele precisa criar um novo array com capacidade maior e copiar os elementos do antigo para o novo.

Quando usamos, por exemplo, o método add(posição, item) para adicionar um elemento no início ou no meio do vetor, primeiramente será necessário deslocar cada elemento uma posição para a direita, fazendo com que a posição desejada seja liberada, e só assim adicionar o novo item nesta posição. Caso o array seja muito grande, isso pode consumir muita memória.

Remover elementos no meio ou no início de um array também pode ser muito crítico, pois não é permitido existir “buracos” no vetor, sendo necessário deslocar todos os elementos para a esquerda.

Considerações Finais

Neste artigo foram abordadas algumas características do ArrayList. Vimos que esta classe implementa a interface List e faz parte do pacote java.util. Também conhecemos alguns dos seus métodos mais utilizados e entendemos um pouco do seu funcionamento, bem como suas vantagens e desvantagens.

Dependendo do contexto, talvez outras implementações sejam mais apropriadas, como LinkedList (que também implementa a interface List), ou HashSet (que implementa a interface Set). Mas isso é assunto para um próximo artigo.