Implementando uma Lista Ligada Simples
Introdução
Após compreendermos a teoria por trás do funcionamento de uma Lista Ligada, chegou o momento de criarmos a nossa própria implementação. Com isso, colocaremos em prática os conceitos abordados e visualizaremos como funciona o controle de referências (ponteiros) entre os nós da estrutura.
Os Nós
De forma breve, como já abordamos anteriormente, podemos definir um nó como um objeto onde guardamos o elemento que queremos armazenar e uma referência para o próximo nó da lista. Ele se caracteriza da seguinte forma:
Podemos traduzir isso para código, em uma linguagem de nossa preferência — neste caso, Java —, da seguinte maneira:
package structures.linkedList;
public class Node<E>{
private E value;
private Node<E> next;
public Node(E value) {
this.value = value;
this.next = null;
}
@Override
public String toString() {
return "Node{" +
"value=" + value +
", next=" + next +
'}';
}
public E getValue() {
return value;
}
public void setValue(E value) {
this.value = value;
}
public Node<E> getNext() {
return next;
}
public void setNext(Node<E> next) {
this.next = next;
}
Perceba que utilizamos Generics justamente por não sabermos o tipo de dado que iremos armazenar até que a Lista Ligada seja instanciada. Iniciamos o construtor atribuindo null à referência next, visto que, por padrão, os nós instanciados antes de serem inseridos na lista não apontam para lugar nenhum.
Por fim, além dos getters e setters padrões, decidimos sobrescrever (override) o método toString() para podermos visualizar facilmente como os nós armazenados são impressos. Optei por deixar a implementação gerada por padrão pelo meu editor de código (IntelliJ).
A classe SLinkedList
Em nossa Lista Ligada Simples (Singly Linked List), também utilizaremos Generics, pois nossa estrutura deve ser capaz de receber qualquer tipo de Objeto de forma dinâmica. Lembra da nossa interface IndexList que fizemos para a estrutura anterior? Faremos proveito dela aqui também, implementando-a em nossa classe SLinkedList.
Para o estado da classe, iremos declarar uma variável do tipo Node chamada head, que apontará para a cabeça (head) da lista, e outra chamada count, que será responsável pelo controle da quantidade de elementos.
package structures.linkedList;
import structures.IndexList;
public class SLinkedList<E> implements IndexList<E> {
protected Node<E> head;
protected int count;
public SLinkedList() {
this.head = null;
count = 0;
}
Iniciamos nosso construtor sem argumentos e com o head apontando para null, visto que, em uma lista recém-criada (sem elementos), a cabeça é nula e o count inicia em zero.
Inserindo um elemento na Lista Ligada
Para inserirmos elementos na lista, temos 2 possibilidades: inserção no início ou em qualquer outro lugar da lista. Logo, precisamos garantir que nosso código cubra os 2 cenários.
@Override
public void insert(int index, E element) throws IndexOutOfBoundsException {
if (index < 0 || index > this.count) {
throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + this.count);
}
Node<E> newNode = new Node<>(element);
if (index == 0) {
this.head = newNode;
} else {
Node<E> previous = this.getElementAt(index - 1);
Node<E> current = previous.getNext();
newNode.setNext(current);
previous.setNext(newNode);
}
this.count++;
}
O método insert recebe como argumento o elemento em questão e um índice. Por mais que a lista ligada não seja indexada nativamente, a forma como a implementaremos facilitará a identificação e a inserção em posições específicas. O primeiro passo é verificar os limites: se o índice passado é menor do que zero ou maior que o tamanho atual da lista, lançamos uma exceção.
Após validar o índice, instanciamos nosso novo nó. Neste momento, sua referência next aponta para null, pois ele ainda não foi conectado à lista.
Em seguida, verificamos se a inserção será na cabeça da lista (index == 0). Caso seja, simplesmente atribuímos o novo nó à variável head e fazemos o nó antigo da cabeça ser o next desse novo nó.
Caso contrário, significa que queremos inserir no meio ou no final da lista. O desafio aqui é a manipulação de referências: precisamos desconectar os nós adjacentes e reconectá-los de forma a incluir o novo nó no meio deles.
Para isso, utilizamos duas referências auxiliares para não perdermos o rastro dos objetos em memória. Percorremos a lista até o nó anterior à posição de inserção utilizando nosso método getElementAt (falaremos dele mais adiante). Chamaremos esse nó de previous. A variável current será o nó que sucede o previous. Nosso objetivo é encaixar o novo nó exatamente entre previous e current.
A lógica é simples: configuramos o next do novo nó para apontar para current, e atualizamos o next de previous para apontar para o novo nó. Isso funciona perfeitamente até mesmo se a inserção for no final da lista (onde current será null). Por fim, incrementamos nossa variável contadora (count++).
Removendo elementos na lista
Para a remoção, também lidaremos com dois cenários principais: remover o primeiro elemento (cabeça) e remover um elemento em qualquer outra posição.
@Override
public E removeAt(int index) throws IndexOutOfBoundsException {
if (index < 0 || index >= this.count) {
throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + this.count);
}
Node<E> current = this.head;
if (index == 0) {
this.head = current.getNext();
} else {
Node<E> previous = this.getElementAt(index - 1);
current = previous.getNext();
previous.setNext(current.getNext());
}
this.count--;
return current.getValue();
}Novamente, a primeira etapa é a verificação de limites. Se o índice for inválido, lançamos uma exceção. Para manter o controle das referências, declaramos uma variável chamada current e atribuímos a ela o head de nossa lista.
Se o elemento a ser removido for o primeiro (index == 0), a solução é direta: basta atualizar a referência head para apontar para o próximo nó da lista (current.getNext()), desconectando o nó inicial.
O segundo cenário é um pouco mais trabalhoso. Para remover elementos em outras posições, precisamos resgatar o nó antecessor (previous) ao que queremos remover. Atualizamos nossa variável current para ser o nó que será removido (previous.getNext()). O “pulo do gato” é simplesmente fazer o next de previous ignorar o current e apontar direto para o next de current. Com isso, o nó current fica isolado e é removido da estrutura.
Por fim, decrementamos o nosso count e devolvemos o valor que estava armazenado no nó removido.
Buscando elementos através do método getElementAt
Este é um dos métodos mais úteis da nossa implementação. Seu objetivo é buscar um nó específico a partir de um índice. Sua presença economiza linhas de código repetitivas em métodos como insert e removeAt, mantendo a legibilidade e respeitando o Princípio da Responsabilidade Única (Single Responsibility Principle - SRP).
public Node<E> getElementAt(int index) {
if (index >= 0 && index < this.count) {
Node<E> current = this.head;
for (int i = 0; i < index && current != null; i++) {
current = current.getNext();
}
return current;
}
return null;
}Após validar se o índice está dentro dos limites, declaramos uma variável current recebendo o head. Como a lista ligada não é indexada na memória como um Array, não podemos acessar posições diretamente. Em vez disso, criamos um loop que “salta” de nó em nó utilizando a referência next até alcançar a posição desejada, retornando esse nó no final.
O método IndexOf
Quem já está familiarizado com as estruturas de dados nativas do Java e de qualquer outra linguagem de programação certamente conhece o indexOf. Ele recebe um elemento e retorna a sua posição na lista. Caso não o encontre, devolve -1.
public int indexOf(E element) {
Node<E> current = this.head;
for (int i = 0; i < this.count && current != null; i++) {
if (current.getValue().equals(element)) {
return i;
}
current = current.getNext();
}
return -1;
}Push e Remove element
Com os métodos insert, removeAt e indexOf prontos, adicionar um elemento ao final da lista ou removê-lo a partir de seu valor tornam-se tarefas muito mais simples.
O método push, por exemplo, consiste em apenas chamar o nosso insert passando o tamanho total da lista (count) como índice. Como as posições baseadas em zero vão até count - 1, inserir na posição count o coloca exatamente no final.
public void push(E element) {
this.insert(this.count, element);
}No método remove sobrecarregado (que recebe o elemento em si), utilizamos o indexOf para descobrir onde o elemento está e repassamos esse índice para o nosso já testado removeAt.
public E remove(E element) {
int index = this.indexOf(element);
return this.removeAt(index);
}ToString
Para facilitar os testes e a visualização no terminal, sobrescrevemos o método toString(). Caso a lista esteja vazia, retornamos ”[]”.
Caso contrário, iteramos sobre os nós, utilizando a classe utilitária StringJoiner do Java para concatenar os valores separados por vírgula, simulando a impressão de um Array convencional. Isso proporciona um log limpo e amigável para quem está consumindo a estrutura.
@Override
public String toString() {
if (this.head == null) {
return "[]";
}
StringJoiner sj = new StringJoiner(", ", "[", "]");
Node<E> current = this.head;
for (int i = 1; i <= this.count || current != null; i++) {
sj.add((current.getValue().toString()));
current = current.getNext();
}
return sj.toString();
}GetHead, IsEmpty e Size
Por fim, temos métodos utilitários clássicos de consulta. Os métodos size() e isEmpty() seguem a mesma lógica trivial que usamos quando implementamos Arrays, apenas retornando o valor de count e verificando se ele é igual a zero, respectivamente.
@Override
public boolean isEmpty() {
return this.count == 0;
}
@Override
public int size() {
return this.count;
}Adicionamos também o método getHead(), que nos permite inspecionar diretamente a cabeça da lista. Se estivéssemos implementando uma Lista Duplamente Ligada ou com controle de cauda, teríamos também um getTail().
public Node<E> getHead() {
return this.head;
}Graças ao método toString() que sobrescrevemos lá na classe Node, ao chamarmos o getHead(), podemos inspecionar visualmente como os nós se encadeiam em cascata armazenando a referência do próximo nó.
Conclusão
Implementar uma Lista Ligada do zero é um exercício fascinante para entender como a memória e as referências funcionam por baixo dos panos na programação. Nossa estrutura demonstrou como criar ligações dinâmicas, o que oferece uma grande vantagem em inserções e remoções comparado aos Arrays estáticos tradicionais.
O código implementado nesta publicação está disponivel no seguinte repositório: https://github.com/ThalesSilva67/data-structure
Referências
- GOODRICH, Michael T.; TAMASSIA, Roberto. Estruturas de Dados e Algoritmos em Java. 5. ed. Porto Alegre: Bookman, 2013.
- GRONER, Loiane. Estruturas de dados e algoritmos com JavaScript: escreva um código JavaScript complexo e eficaz usando os recursos mais recentes do ECMAScript. 2. ed. São Paulo: Novatec Editora, 2019. 408 p