É 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

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

Awesome!

Implementando nossa LinkedList

Criar

Ler

Atualização