Aprenda Implementando LinkedList em Java

Deslize para mostrar o menu

É hora de se desafiar com algumas tarefas realmente complexas.

Vamos implementar nossa estrutura de dados simplificada—especificamente, a SinglyLinkedList.

Vamos começar implementando a classe Node, que irá armazenar um valor e uma referência para o próximo Node.

Node.java


              123456789
            
class Node {
    int data;
    Node next;

    public Node(int data) {
        this.data = data;
        this.next = null;
    }
}

A implementação da classe Node em SinglyLinkedList já foi demonstrada no capítulo anterior, portanto não iremos nos aprofundar nela neste momento.

Em seguida, vamos criar a classe SinglyLinkedList, onde definiremos toda a lógica para nossa estrutura de dados:

SinglyLinkedList.java


              1234567
            
public class SinglyLinkedList {
    private Node head;

    public SinglyLinkedList() {
        this.head = null;
    }
}

Criamos o campo Node head, que irá armazenar o primeiro elemento da nossa estrutura de dados.

Em uma LinkedList comum, também existem os campos head e tail que armazenam o primeiro e o último elementos da estrutura de dados. Como a estrutura de dados deve estar vazia durante a inicialização, definimos este campo como null no construtor.

Nossa estrutura de dados precisa oferecer suporte a todas as operações CRUD.

Criar

Vamos, então, passo a passo, escrever um método para adicionar um elemento ao final da lista, representando a operação de criação:

SinglyLinkedList.java


              12345678910111213141516171819202122
            
public class SinglyLinkedList {
    private Node head;

    public SinglyLinkedList() {
        this.head = null;
    }

    public void append(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            return;
        }

        Node current = head;
        while (current.next != null) {
            current = current.next;
        }

        current.next = newNode;
    }
}

Acima, é possível visualizar a implementação do método para adicionar um elemento ao final da lista. A seguir, a explicação de como esse método funciona:

Criação de um objeto da classe Node, chamado newNode, inicializado por meio do construtor, passando o data recebido como parâmetro do método append();
Em seguida, verificação se a lista está vazia; caso esteja, substituição do primeiro elemento da lista (head) por newNode através de reatribuição;
Inclusão de uma instrução return para encerrar o método;
Caso a lista não esteja vazia, criação de um novo objeto, current, que representa o Node head neste contexto;
Utilização de um laço while para percorrer toda a lista até que current.next seja null, ou seja, até identificar que o próximo elemento da lista está vazio;
Ao encontrar o último elemento não nulo da lista, definição de seu link para newNode, adicionando assim o elemento à lista.

Em resumo, o objetivo do método append foi definir o link do último elemento para o novo elemento. Dessa forma, um novo elemento é adicionado à lista.

Leitura

Vamos prosseguir; agora precisamos implementar a operação de leitura.

SinglyLinkedList.java


              12345678
            
public void display() {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.next;
        }
        System.out.println();
    }

Operação de leitura é bastante simples. É necessário iterar por cada elemento da lista e exibi-los na tela. Neste caso, também utilizamos o placeholder current, que é inicializado com o Node head;
Em seguida, definimos a condição para o laço while como current != null e exibimos o campo data na tela;
Para iterar pela lista, utilizamos a referência por reatribuição de current, que fica assim: current = current.next;;
Isso é feito até que o Node current se torne vazio. Após isso, saímos do laço e seguimos para a próxima linha.

A propósito, reflita sobre como substituir esse laço while por um laço do-while. Isso é possível?

Atualização

Agora, vamos passar para o método de atualização, que possui uma implementação mais interessante:

SinglyLinkedList.java


              12345678910111213
            
public void update(int index, int newData) {
    if (index < 0 || index >= size()) {
        System.out.println("Invalid index");
        return;
    }

    Node current = head;
    for (int i = 0; i < index; i++) {
        current = current.next;
    }

    current.data = newData;
}

Primeiro, verifica-se se esse index está presente na lista utilizando uma instrução if. Caso não esteja, exibe-se a mensagem "Invalid index" e encerra-se o método. Isso é feito para evitar erros;
Se o índice estiver dentro dos limites da lista, prossegue-se com o algoritmo já conhecido. Inicialmente, cria-se um objeto da classe Node chamado current, que é inicializado como o head;
Em vez de utilizar um laço while, utiliza-se um laço for, que é mais adequado neste caso pois se conhece o número exato de iterações necessárias. O número de iterações é igual ao valor do parâmetro index;
O laço fica assim:
for (int i = 0; i < index; i++). Neste laço, encontra-se o elemento desejado utilizando a operação já conhecida: current = current.next;
Após encontrar o elemento desejado, atribui-se ao seu atributo data um novo valor, realizando a operação
current.data = newData. O valor de newData é recebido como parâmetro deste método.

Tudo estava claro?

Obrigado pelo seu feedback!

Seção 1. Capítulo 7

Pergunte à IA

Pergunte o que quiser ou experimente uma das perguntas sugeridas para iniciar nosso bate-papo

Seção 1. Capítulo 7