É hora de se desafiar com algumas tarefas verdadeiramente complexas. Neste capítulo, vamos implementar a nossa estrutura de dados simplificada - especificamente, a SinglyLinkedList.

Vamos começar implementando a classe Node, que 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;
    }
}

No capítulo anterior, eu já demonstrei a implementação da classe Node em SinglyLinkedList, então não vamos nos deter nela por muito tempo.

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

SinglyLinkedList.java


              1234567
            
public class SinglyLinkedList {
    private Node head;

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

Criamos o campo Node head, que armazenará o primeiro elemento da nossa estrutura de dados. Em uma LinkedList comum, também existem head e tail que armazenam os primeiros e últimos elementos da estrutura de dados. Como a estrutura de dados deve estar vazia durante a inicialização, inicializamos esse campo como null no construtor.

Nossa estrutura de dados precisa ter todas as operações CRUD.

Criar

Então, vamos passo a passo e 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, você pode ver a implementação do método para adicionar um elemento ao final da lista. Vamos detalhar como este método funciona:
Criamos um objeto da classe Node, newNode, e o inicializamos através do construtor, passando os dados dos parâmetros do método append().
Em seguida, verificamos se a lista está vazia, e se estiver, substituímos o primeiro elemento da lista (head) por newNode por meio 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.
Usando um laço while, iteramos por toda a lista até que current.next seja null, ou seja, até determinarmos que o próximo elemento na lista está vazio.
Uma vez que encontramos o último elemento não nulo na lista, definimos sua ligação para newNode, adicionando assim o elemento à nossa lista.

Em outras palavras, o objetivo do método append era definir a ligação do último elemento para o novo elemento. Dessa forma, adicionamos um novo elemento à lista.

Ler

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. Precisamos iterar por cada elemento da lista e imprimi-los na tela. No nosso caso, também utilizamos o marcador current, que inicializamos com o Node head.
Em seguida, definimos a condição para o loop while como current != null e imprimimos o campo data na tela.
Para iterar pela lista, usamos a referência reatribuindo current, o que se parece com current = current.next;.
Fazemos isso até que o Node current fique vazio. Depois disso, saímos do loop e passamos para a próxima linha.

A propósito, pense em como substituir este loop while por um loop do-while. Será que isso pode ser feito?

Atualização

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

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;
}

Nota

Neste método, utilizamos o método size, que você implementará por conta própria no próximo capítulo. Portanto, por agora, é importante entender que este método retorna o comprimento da lista.

Primeiro, verificamos se o index está na nossa lista usando uma instrução if. Se não estiver, imprimimos a mensagem "Índice inválido" e terminamos o método. Isso é feito para evitar erros.

Se o índice estiver dentro dos limites da nossa lista, prosseguimos com o algoritmo familiar. Primeiro, criamos um objeto da classe Node chamado current, que inicializamos como a head.

Em vez de usar um loop while, usamos um loop for, que é mais adequado aqui uma vez que conhecemos o número exato de iterações necessárias. O número de iterações é igual ao valor do parâmetro index.

Nosso loop se parece com isto:
for (int i = 0; i < index; i++). Neste loop, encontramos o elemento desejado usando a operação familiar: current = current.next.

Uma vez que encontramos o elemento desejado, atribuímos ao seu atributo data um novo valor, realizando a operação
current.data = newData. Pegamos o newData dos parâmetros deste método.

Parece bem simples, não é? Deixo para você como uma tarefa pessoal implementar dois métodos nesta classe: o método delete e o método size. Tenho confiança de que você vai conseguir realizar essa tarefa. Vejo você no próximo capítulo!

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

Suggested prompts:

Can you show me the code for the append method?

How would you implement the read operation in code?

Can you explain how the update method works with an example?

Deslize para mostrar o menu

É hora de se desafiar com algumas tarefas verdadeiramente complexas. Neste capítulo, vamos implementar a nossa estrutura de dados simplificada - especificamente, a SinglyLinkedList.

Vamos começar implementando a classe Node, que 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;
    }
}

No capítulo anterior, eu já demonstrei a implementação da classe Node em SinglyLinkedList, então não vamos nos deter nela por muito tempo.

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

SinglyLinkedList.java


              1234567
            
public class SinglyLinkedList {
    private Node head;

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

Nossa estrutura de dados precisa ter todas as operações CRUD.

Criar

Então, vamos passo a passo e 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, você pode ver a implementação do método para adicionar um elemento ao final da lista. Vamos detalhar como este método funciona:
Criamos um objeto da classe Node, newNode, e o inicializamos através do construtor, passando os dados dos parâmetros do método append().
Em seguida, verificamos se a lista está vazia, e se estiver, substituímos o primeiro elemento da lista (head) por newNode por meio 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.
Usando um laço while, iteramos por toda a lista até que current.next seja null, ou seja, até determinarmos que o próximo elemento na lista está vazio.
Uma vez que encontramos o último elemento não nulo na lista, definimos sua ligação para newNode, adicionando assim o elemento à nossa lista.

Em outras palavras, o objetivo do método append era definir a ligação do último elemento para o novo elemento. Dessa forma, adicionamos um novo elemento à lista.

Ler

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. Precisamos iterar por cada elemento da lista e imprimi-los na tela. No nosso caso, também utilizamos o marcador current, que inicializamos com o Node head.
Em seguida, definimos a condição para o loop while como current != null e imprimimos o campo data na tela.
Para iterar pela lista, usamos a referência reatribuindo current, o que se parece com current = current.next;.
Fazemos isso até que o Node current fique vazio. Depois disso, saímos do loop e passamos para a próxima linha.

A propósito, pense em como substituir este loop while por um loop do-while. Será que isso pode ser feito?

Atualização

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

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;
}

Nota

Neste método, utilizamos o método size, que você implementará por conta própria no próximo capítulo. Portanto, por agora, é importante entender que este método retorna o comprimento da lista.

Se o índice estiver dentro dos limites da nossa lista, prosseguimos com o algoritmo familiar. Primeiro, criamos um objeto da classe Node chamado current, que inicializamos como a head.

Nosso loop se parece com isto:
for (int i = 0; i < index; i++). Neste loop, encontramos o elemento desejado usando a operação familiar: current = current.next.

Uma vez que encontramos o elemento desejado, atribuímos ao seu atributo data um novo valor, realizando a operação
current.data = newData. Pegamos o newData dos parâmetros deste método.

Tudo estava claro?

Obrigado pelo seu feedback!

Seção 1. Capítulo 6

Implementando nossa LinkedList

Criar

Ler

Atualização

Implementando nossa LinkedList

Criar

Ler

Atualização