Aprenda Implementação de LinkedList em Java | Estruturas de Dados Fundamentais em Java

É 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.

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 esse 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 ver a implementação do método para adicionar um elemento ao final da lista. Vamos detalhar como esse método funciona:

Criamos um objeto da classe Node, chamado newNode, e o inicializamos através do construtor, passando o data recebido nos parâmetros do método append();
Em seguida, verificamos se a lista está vazia e, caso esteja, substituímos o primeiro elemento da lista (head) por newNode através de reatribuição;
Depois, adicionamos uma instrução return para sair do método;
Se a lista não estiver vazia, neste método, criamos um novo objeto, current, que representa o Node head neste contexto;
Utilizando um laço while, iteramos por toda a lista até que current.next seja null, ou seja, até determinarmos que o próximo elemento da lista está vazio;
Assim que encontramos o último elemento não nulo da lista, definimos seu link para newNode, adicionando assim o elemento à nossa lista.

Em outras palavras, o objetivo do método append foi definir o link do último elemento para o novo elemento. Dessa forma, adicionamos um novo elemento à 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();
    }

A 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, define-se a condição para o laço while como current != null e exibe-se o campo data na tela;
Para iterar pela lista, utiliza-se a referência por reatribuição de current, que fica como current = current.next;;
Isso é feito até que o Node current se torne vazio. Após isso, o laço é encerrado e segue-se para a próxima linha.

Por sinal, 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, cuja 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 contrário, 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 tem a seguinte forma:
for (int i = 0; i < index; i++). Neste laço, localiza-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 6

Pergunte à IA

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

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.

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.

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 ver a implementação do método para adicionar um elemento ao final da lista. Vamos detalhar como esse método funciona:

Criamos um objeto da classe Node, chamado newNode, e o inicializamos através do construtor, passando o data recebido nos parâmetros do método append();
Em seguida, verificamos se a lista está vazia e, caso esteja, substituímos o primeiro elemento da lista (head) por newNode através de reatribuição;
Depois, adicionamos uma instrução return para sair do método;
Se a lista não estiver vazia, neste método, criamos um novo objeto, current, que representa o Node head neste contexto;
Utilizando um laço while, iteramos por toda a lista até que current.next seja null, ou seja, até determinarmos que o próximo elemento da lista está vazio;
Assim que encontramos o último elemento não nulo da lista, definimos seu link para newNode, adicionando assim o elemento à nossa lista.

Em outras palavras, o objetivo do método append foi definir o link do último elemento para o novo elemento. Dessa forma, adicionamos um novo elemento à 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();
    }

A 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, define-se a condição para o laço while como current != null e exibe-se o campo data na tela;
Para iterar pela lista, utiliza-se a referência por reatribuição de current, que fica como current = current.next;;
Isso é feito até que o Node current se torne vazio. Após isso, o laço é encerrado e segue-se para a próxima linha.

Por sinal, 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, cuja 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 contrário, 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 tem a seguinte forma:
for (int i = 0; i < index; i++). Neste laço, localiza-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 6