Uma introdução ao uso de listas vinculadas em Java
Uma estrutura de dados usa diferentes métodos predefinidos para armazenar, recuperar e excluir dados que culminam na criação de programas eficientes. Uma lista vinculada é uma estrutura de dados popular, que consiste em uma lista de nós que estão conectados (ou vinculados).
Mas como você cria uma lista vinculada em Java? Vamos dar uma olhada.
Como funciona uma lista vinculada?
Cada lista vinculada começa com um nó especial que geralmente é referido como "cabeça", que tem a responsabilidade de apontar para o início da lista o tempo todo. O cabeçalho é importante porque cada nó em uma lista encadeada não precisa seguir seu sucessor fisicamente (o que significa que um predecessor e um sucessor não precisam ser fisicamente adjacentes).
Como toda estrutura de dados, a lista vinculada facilita a criação, recuperação, inserção e destruição por meio de um conjunto de funções predefinidas que podem ser usadas por qualquer desenvolvedor.
Criação de uma lista vinculada em Java
Um programa Java projetado para criar e manipular listas vinculadas terá três seções distintas; a classe de nó, a classe de lista vinculada e o driver. Embora essas três seções possam ser combinadas em um arquivo, existe um princípio de design na ciência da computação conhecido como "separação de interesses" que todo desenvolvedor deve conhecer.
O princípio da separação de interesses determina que cada seção do código que trata de uma preocupação específica deve ser separada. Este princípio o ajudará a criar um código mais limpo (mais legível) e é ideal para criar estruturas de dados.
A primeira etapa na criação de uma lista vinculada em Java é criar uma classe de nó. Uma classe de nó deve ter dois atributos; um dos atributos representará a parte de dados do nó, enquanto o outro atributo representará a parte vinculada. Uma classe de nó também deve ter um construtor, getters e setters.
Os getters e setters permitirão que outras classes (como a classe da lista vinculada) acessem os vários nós dentro da lista vinculada.
Exemplo de classe de nó
Abaixo está um exemplo de classe de nó para você ter uma ideia do que queremos dizer:
public class Node {
private int Data;
private Node NextNode;
//constructor
public Node() {
Data = 0;
NextNode = null;
}
//getters and setters
public int getData() {
return Data;
}
public void setData(int data) {
Data = data;
}
public Node getNextNode() {
return NextNode;
}
public void setNextNode(Node nextNode) {
NextNode = nextNode;
}
}Neste exemplo, o atributo de dados armazenará valores inteiros. Agora que você tem a classe de nó, é hora de passar para a lista vinculada.
Exemplo de lista vinculada
Abaixo está um exemplo de uma lista vinculada em Java.
public class LinkedList {
private Node Head;
//constructor
public LinkedList() {
Head = null;
}
}
O código acima criará uma classe de lista vinculada, no entanto, sem suas várias operações, a classe pode ser vista como o equivalente a um shell vazio. A estrutura de dados da lista vinculada possui várias operações que podem ser usadas para preenchê-la:
- Insira na frente.
- Insira no meio.
- Insira na parte de trás.
A coleção de lista vinculada de métodos de inserção é uma razão pela qual um desenvolvedor pode escolher usar essa estrutura de dados em vez de outra estrutura de dados, como pilhas (que só permite a inserção e exclusão do topo).
Usando o método de inserção na frente
O método de inserção na frente, como o nome sugere, insere novos dados (ou novos nós) na frente da lista vinculada.
Exemplo de método de inserção na frente
Abaixo está um exemplo de como você inseriria novos dados no início da sua lista.
//insert node at front method
public void insertAtFront(int key) {
//create a new node using the node class
Node Temp = new Node();
//check if the Temp node was successfully created
//assign the data that was provides by the user to it
if(Temp != null) {
Temp.setData(key);
Temp.setNextNode(null);
//check if the head of the linked list is empty
//assign the node that was just created to the head position
if(Head == null) {
Head = Temp;
}
//if a node is already at the head position
//add the new node to it and set it as the head
else {
Temp.setNextNode(Head);
Head = Temp;
}
}
}
O método insertAtFront no exemplo acima permite que um usuário adicione novos nós a uma determinada lista vinculada.
Aplicando a Inserção na Frente Exemplo
Abaixo está um exemplo de como você aplicaria a inserção na frente.
public class Driver {
//executes the program
public static void main(String[] args) {
//create a new linked list called List
LinkedList List = new LinkedList();
//add each value to the front of the linked list as a new node
List.insertAtFront(10);
List.insertAtFront(8);
List.insertAtFront(6);
List.insertAtFront(4);
List.insertAtFront(2);
}
}
A classe Driver (que é o nome frequentemente atribuído à classe executável em Java) utiliza a classe LinkedList para criar uma lista vinculada de cinco números pares. Olhando para o código acima, deve ser fácil ver que o número "2" está na posição inicial na lista vinculada. Mas como você pode confirmar isso?
Usando o método de exibição de todos os nós
O método de exibição de todos os nós é um método de lista vinculada essencial. Sem ele, um desenvolvedor não será capaz de ver os nós em uma lista vinculada. Ele percorre a lista encadeada (começando pelo cabeçalho) imprimindo os dados armazenados em cada nó que forma a lista.
Exemplo de método de exibição de todos os nós
Abaixo está um exemplo de uso do método de exibição de todas as notas em Java.
//display all nodes method
public void displayAllNodes() {
//create a new node call Temp and assign it to the head of the linked list
//if the head has a null value then the linked list is empty
Node Temp = Head;
if (Head == null){
System.out.println("The list is empty.");
return;
}
System.out.println("The List:");
while(Temp != null) {
//print the data in each node to the console(starting from the head)
System.out.print(Temp.getData() + " ");
Temp = Temp.getNextNode();
}
}Agora que o método displayAllNodes foi adicionado à classe LinkedList, você pode visualizar a lista vinculada adicionando uma única linha de código à classe do driver.
Usando o Exemplo do Método Exibir Todos os Nós
Abaixo, você verá como usaria o método de exibição de todos os nós.
//print the nodes in a linked list
List.displayAllNodes();Executar a linha de código acima produzirá a seguinte saída no console:
A lista:
2 4 6 8 10Usando o método Find Node
Haverá casos em que um usuário desejará encontrar um nó específico em uma lista vinculada.
Por exemplo, não seria prático para um banco que tem milhões de clientes imprimir todos os clientes em seu banco de dados quando eles só precisam ver os detalhes de um cliente específico.
Portanto, em vez de usar o método displayAllNodes , um método mais eficiente é localizar o único nó que contém os dados necessários. É por isso que a busca por um método de nó único é importante na estrutura de dados da lista vinculada.
Exemplo de Método de Localização de Nó
Abaixo está um exemplo de uso do método find node.
//search for a single node using a key
public boolean findNode(int key) {
//create a new node and place it at the head of the linked list
Node Temp = Head;
//while the current node is not empty
//check if its data matches the key provided by the user
while (Temp != null) {
if (Temp.getData() == key) {
System.out.println("The node is in the list");
return true;
}
//move to the next node
Temp = Temp.getNextNode();
}
//if the key was not found in the linked list
System.out.println("The node is not in the list");
return false;
}Com o método displayAllNodes , você confirmou que LinkedList contém 5 números pares de 2 a 10. O exemplo findNode acima pode confirmar se um desses números pares é o numeral 4 simplesmente chamando o método na classe do driver e fornecendo o número como um parâmetro.
Usando o Exemplo do Método Find Node
Abaixo está um exemplo de como você usaria o método find node na prática.
//check if a node is in the linked list
List.findNode(4);
O código acima produzirá a seguinte saída no console:
The node is in the listUsando o Método Excluir um Nó
Usando o mesmo exemplo de banco acima, um cliente no banco de dados do banco pode desejar encerrar sua conta. É aqui que o método de exclusão de um nó será útil. É o método de lista vinculada mais complexo.
O método Delete a Node procura um determinado nó, exclui esse nó e vincula o nó anterior àquele que segue o nó que foi excluído.
Excluir um Exemplo de Método de Nó
Abaixo está um exemplo do método de exclusão de um nó.
public void findAndDelete(int key) {
Node Temp = Head;
Node prev = null;
//check if the head node holds the data
//and delete it
if (Temp != null && Temp.getData() == key) {
Head = Temp.getNextNode();
return;
}
//search the other nodes in the list
//and delete it
while (Temp != null) {
if (Temp.getNextNode().getData() == key ) {
prev = Temp.getNextNode().getNextNode();
Temp.setNextNode(prev);
return;
}
Temp = Temp.getNextNode();
}
}Usando o Exemplo de Método de Exclusão de Nó
Abaixo está um exemplo de como usar o método de exclusão de um nó na prática.
//delete the node that holds the data 4
List.findAndDelete(4);
//print all nodes in the linked list
List.displayAllNodes();Usar as duas linhas de código acima na classe Driver pré-existente produzirá a seguinte saída no console:
The List:
2 6 8 10Agora você pode criar listas vinculadas em Java
Se você chegou ao final deste artigo tutorial, terá aprendido:
- Como criar uma classe de nó.
- Como criar uma classe de lista vinculada.
- Como preencher uma classe de lista vinculada com seus métodos predefinidos.
- Como criar uma classe de driver e usar os diferentes métodos de lista vinculada para obter o resultado desejado.
Uma lista vinculada é apenas uma das muitas estruturas de dados que você pode usar para armazenar, recuperar e excluir dados. Já que você tem tudo de que precisa para começar, por que não experimentar esses exemplos em Java?