Videolivro 4 - listas encadeadas

1. Conceito de lista encadeada

Lista encadeada é um conjunto de elementos dispostos em uma organização não linear.

A figura de Goodrich e Tamassia (2013) apresenta a estrutura de uma lista simplesmente encadeada.

Observe que nó ou nodo são sinônimos. Alguns autores chamam de nó e outros de nodo. Cada nó apresenta o conteúdo e o link para o próximo nó.

2. Criação das classes

Na figura a seguir temos um exemplo de lista encadeada.

Utilizaremos o exemplo proposto por Puga e Russeti (2016) para implementar uma lista encadeada, com duas classes: 

1o.) NoSimples é a classe que vai implementar cada elemento do nó.

2o.) ListaSimples é uma classe para definir os objetos do tipo lista que é formada por objetos do tipo NoSimples.

3. Inserção no início da lista

	ListaSimples(){
		primeiro = null;
		ultimo = null;
	}

public void inserirInicio (NoSimples novoNo) {
	if (primeiro==null) {
		primeiro = novoNo;
		ultimo = novoNo;
		}
	else
	{
		novoNo.proximo = primeiro;
		primeiro = novoNo;
	}

}

4. Exibir os elementos da lista

Antes de criarmos a classe Principal que vai instanciar o objeto do tipo listaSimples, com seu método main, veremos como exibir os elementos da lista.

A função em Java para exibir os elementos da lista, é implementado por Puga e Risseti (2016, p. 221) da seguinte forma:

public String mostrarLista() {
	int i = 0;
	NoSimples noTemp = primeiro;
	String msg = "";
	while (noTemp != null) {
		msg = msg + "Posição: " + i + " , valor do nó: " + noTemp.valor + "\n";
		noTemp = noTemp.proximo;
		i++;
	}
	return msg;
}

5. Programa Principal

Nosso programa Principal irá instanciar objetos do tipo noSimples e listaSimples, inserir elementos na lista (através do procedimento inserirInicio) e listar os elementos da lista (através da função mostrarLista).

Para tal, criaremos uma lista com 5 valores digitados pelo usuário.

package exemploListaEncadeada;
import javax.swing.JOptionPane;
public class Principal {

	public static void main(String[] args) {
		ListaSimples lista = new ListaSimples();
		Object valor;
		String resultadoLista;
		int cont;
		
		for (cont=0;cont<5;cont++) {
			valor = JOptionPane.showInputDialog("Digite um valor: ");
			lista.inserirInicio(new NoSimples(valor));
					
		}
		resultadoLista = lista.mostrarLista();	
		System.out.println(resultadoLista);
	}

}

6. Contar os elementos da lista

Agora que sabemos inserir um elemento na lista e imprimir, que tal contar quantos elementos a lista possui?

Vamos à criação do função contarNos () que vai retornar o número de elementos que a lista possui.

A lógica é simples:

1o.) Um nó que vamos chamar de noTemp vai apontar para o primeiro.

2o.) Contamos mais um 

3o.) O noTemp aponta para o próximo

4o.) Repetimos enquanto noTempo seja diferente de null.

public int contarNos() {
	int contador = 0;
	NoSimples noTemp = primeiro;
	while (noTemp != null) {
		contador++;
		noTemp = noTemp.proximo;
	}
	return contador;
}

Fonte: Puga e Risseti (2016, p. 216)

		cont = lista.contarNos();
		System.out.println("O número de nós na lista é: " + cont);

7. Inserção no final da lista

Veja a figura seguinte, adaptada de Puga e Risseti (2016, p. 214):

Ela representa uma lista na qual o primeiro valor inserido foi o 1 e o último foi o 7.

Fazer uma inserção no final da lista, significa inserir após o 7, ou seja, o valor que entra passa a ser o último da lista.

Uma inserção do valor 2 no final da lista, deixa a lista da seguinte forma:

Assim:

1o.) O elemento novo deverá apontar para nul.

2o.) Se o primeiro estiver vazio, então ele aponta para o novo; senão o último aponta para o novo [é este o caso do nosso exemplo].

Vejamos então o procedimento inserirFinal (NoSimples novoNo)

public void inserirFinal (NoSimples novoNo) {
	novoNo.proximo = null;
	if (primeiro==null){
		primeiro = novoNo;
		ultimo = novoNo;
	}
		
	else {
		ultimo.proximo = novoNo;
		ultimo = novoNo;
	}
		
}

Fonte: adaptado de Puga e Risseti (2016, p. 214)

8. Inserir elemento em uma posição específica

No exemplo anterior, nossa lista era formada pelos valores 1, 3, 5 e 7. Inserimos no final o número 2. Suponhamos que a ideia fosse inserir o número 2 entre o 1 e 3, ou seja, o novo elemento não seria inserido no início, nem no final, como já vimos antes, mas em uma posição específica, como mostra nosso desenho adaptado de Puga e Risseti (2016, p. 217):

Note que precisamos quebrar o vínculo entre o primeiro e segundo elemento (valores 1 e 3) para inserir outro no meio.  

Desta vez, os parâmetros passam a ser não somente o valor a ser inserido, como também o número da posição.

Os números 1, 3, 5 e 7 estão nas posições 0, 1, 2 e 3 respectivamente.

		1) Número de nós = chamar a função contarNos
		2) Em seguida:
		se posição informada = 0
		   então chamar o procedimento para inserir no início [que já construímos]
		   senão se posição informada > Número de nós
			    então chamar o procedimento para inserir no final
                            senão percorrer a lista até a posição informada para inserir.
                         fimse;
                 fimse;

public void inserirPosicao (NoSimples novoNo, int posicao) {
	NoSimples noTemp = primeiro;
	int posAuxiliar;
	int numNos = contarNos();
	
	if (posicao==0)
		inserirInicio (novoNo);
	else 	if (posicao>numNos) 
	   	inserirFinal (novoNo);
			else {
				posAuxiliar = 1;
				while (posicao>posAuxiliar) {
					noTemp = noTemp.proximo;
					posAuxiliar++;
				
				}
				novoNo.proximo = noTemp.proximo;
				noTemp.proximo = novoNo;
			
	}
	
}

9. Referências

GOODRICH, Michael T.; TAMASSIA, Roberto. Estruturas de Dados e Algoritmos em Java.  5. ed. Porto Alegre: Bookman, 2013.

PUGA, Sandra; RUSSETI, Gerson. Lógica de programação e estruturas de dados. 3. ed. São Paulo: Pearson Education do Brasil, 2016.