A Classe LinkedList em Java

A LinkedList<E> é uma estrutura de dados que representa uma lista encadeada. Diferente de um ArrayList, ele organiza os elementos como nós conectados, permitindo inserções e remoções rápidas em qualquer posição da lista.

A LinkedList combina funcionalidades de listas e filas, pois implementa as interfaces List, Deque e Queue.

Construtores

A LinkedList oferece três formas principais de criar uma lista:

• LinkedList() : cria uma lista vazia.
• LinkedList(Collection<? extends E> c) : cria uma lista preenchida com os elementos de outra coleção.

Principais métodos

A LinkedList possui métodos das interfaces List, Deque e Queue, permitindo diferentes formas de manipular os elementos.

Inserção de elementos:

• add(E e) : adiciona no final da lista.
• add(int index, E e) : adiciona em uma posição específica.
• addFirst(E e) / offerFirst(E e) : adiciona no início da lista.
• addLast(E e) / offerLast(E e) : adiciona no final da lista.

Acesso aos elementos:

• get(int index) : retorna o elemento de uma posição específica.
• getFirst() / peekFirst() : retorna o primeiro elemento.
• getLast() / peekLast() : retorna o último elemento.

Remoção de elementos:

• remove(Object o) : remove a primeira ocorrência do elemento.
• remove(int index) : remove o elemento de uma posição específica.
• removeFirst() / pollFirst() : remove o primeiro elemento.
• removeLast() / pollLast() : remove o último elemento.

Outros métodos úteis:

• contains(Object o) : verifica se a lista contém determinado elemento.
• size() : retorna o número de elementos na lista.

Dica: métodos que começam com offer ou peek geralmente não lançam exceções, enquanto métodos como addFirst, removeFirst ou getFirst podem lançar exceções se a lista estiver vazia.

Exemplo prático

import java.util.LinkedList;

public class Main {

    public static void main(String[] args) {

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

        // Adicionando elementos
        states.add("Germany");
        states.add("France");
        states.addLast("Great Britain"); // adiciona no final
        states.addFirst("Spain");        // adiciona no início
        states.add(1, "Italy");          // adiciona no índice 1

        System.out.printf("A lista tem %d elementos.\n", states.size());
        System.out.println("Elemento no índice 1: " + states.get(1));

        states.set(1, "Portugal"); // altera o elemento do índice 1

        System.out.println("Todos os estados:");
        for (String state : states) {
            System.out.println(state);
        }

        // Verificação de presença de elemento
        if (states.contains("Germany")) {
            System.out.println("A lista contém Germany");
        }

        // Removendo elementos
        states.remove("Germany"); // remove pelo valor
        states.removeFirst();     // remove o primeiro
        states.removeLast();      // remove o último

        // Lista de objetos personalizados
        LinkedList<Person> people = new LinkedList<>();
        people.add(new Person("Mike"));
        people.addFirst(new Person("Tom"));
        people.addLast(new Person("Nick"));
        people.remove(1); // remove o segundo elemento

        System.out.println("Lista de pessoas:");
        for (Person p : people) {
            System.out.println(p.getName());
        }

        Person first = people.getFirst();
        System.out.println("Primeiro da lista de pessoas: " + first.getName());
    }
}

class Person {
    private String name;

    public Person(String value) {
        name = value;
    }

    public String getName() {
        return name;
    }
}

Saída:

A lista tem 5 elementos.
Elemento no índice 1: Italy
Todos os estados:
Spain
Portugal
Germany
France
Great Britain
A lista contém Germany
Lista de pessoas:
Tom
Nick
Primeiro da lista de pessoas: Tom

Como o LinkedList funciona

• Cada elemento da lista é armazenado em um nó que aponta para o próximo (e também para o anterior, no caso de Deque).
• Inserir ou remover elementos no início ou no fim da lista é muito rápido, diferente do ArrayList, que precisa mover elementos em um array interno.
• Acesso a elementos pelo índice (get(int index)) é mais lento que em um ArrayList, pois é necessário percorrer a lista até encontrar o elemento.

Resumo

• LinkedList combina funcionalidades de lista e fila.
• Permite adicionar e remover elementos no início, no fim ou em posições específicas.
• Suporta métodos da interface Collection, como add(), remove(), contains() e size().
• Bom para operações frequentes de inserção e remoção, mas menos eficiente para acesso direto por índice.

📝 Exercícios

Tarefa: Comparar desempenho de LinkedList e ArrayList

Objetivo: Medir a diferença de tempo ao inserir elementos no início de uma lista usando LinkedList e ArrayList.

1. Criar uma LinkedList<Integer> e uma ArrayList<Integer>.
2. Adicionar 50.000 elementos no início de cada lista (usar add(0, i)).
3. Medir o tempo gasto para cada lista usando System.currentTimeMillis().
4. Comparar os tempos e explicar por que a LinkedList é mais eficiente nesse caso.

import java.util.LinkedList;
import java.util.ArrayList;

public class Main {
    public static void main(String[] args) {
        LinkedList<Integer> linkedList = new LinkedList<>();
        ArrayList<Integer> arrayList = new ArrayList<>();

        // Adicionar 10.000 elementos no início da linkedList e medir o tempo
        // Adicionar 10.000 elementos no início da arrayList e medir o tempo

        // Exibir os tempos no console
    }
}

import java.util.LinkedList;
import java.util.ArrayList;

public class Main {
    public static void main(String[] args) {
        LinkedList<Integer> linkedList = new LinkedList<>();
        ArrayList<Integer> arrayList = new ArrayList<>();

        long startLinked = System.currentTimeMillis();
        for (int i = 0; i < 50000; i++) {
            linkedList.add(0, i);
        }
        long endLinked = System.currentTimeMillis();

        long startArray = System.currentTimeMillis();
        for (int i = 0; i < 50000; i++) {
            arrayList.add(0, i);
        }
        long endArray = System.currentTimeMillis();

        System.out.println("LinkedList: " + (endLinked - startLinked) + " ms");
        System.out.println("ArrayList: " + (endArray - startArray) + " ms");
    }
}

LinkedList: 8 ms
ArrayList: 319 ms