Listas encadeadas
Uma lista encadeada é uma representação de uma sequência de objetos na memória do computador. Cada elemento da sequência é armazenado em uma célula da lista: o primeiro elemento na primeira célula, o segundo na segunda e assim por diante.
Uma lista encadeada é uma sequência de células; cada célula contém um objeto de algum tipo e o endereço da célula seguinte.
public class Nodo {
private int dado;
private Nodo proximo;
/**
* Construtor padrao; Dado = 0; Proximo = null;
*/
public Nodo() {
dado = 0;
proximo = null;
}
/**
* Construtor sobrescrito; Dado = Dado ; Proximo = null;
*/
public Nodo(int dadoNovo) {
setDado( dadoNovo );
proximo = null;
}
public int getDado() {
return dado;
}
public Nodo getProximo() {
return proximo;
}
public void setDado(int dadoNovo) {
dado = dadoNovo;
}
public void setProximo(Nodo nodoNovo) {
proximo = nodoNovo;
}
}
public class ListaEncadeada {
private Nodo primeiroNodo;
private int tamanhoLista;
/**
* Construtor padrao
*/
public ListaEncadeada() {
primeiroNodo = null;
tamanhoLista = 0;
}
public int getTamanhoLista() {
return tamanhoLista;
}
public void insert(int valor) {
Nodo novoNodo = new Nodo( valor );
novoNodo.setProximo( primeiroNodo );
primeiroNodo = novoNodo;
tamanhoLista++;
}
public boolean delete(int valor) {
Nodo corrente = primeiroNodo;
Nodo anterior = null;
while (corrente != null && corrente.getDado() != valor) {
anterior = corrente;
corrente = corrente.getProximo();
}
if (corrente == null)
return false;
else {
if (corrente == primeiroNodo)
primeiroNodo = primeiroNodo.getProximo();
else
anterior.setProximo( corrente.getProximo() );
tamanhoLista--;
return true;
}
}
public String toString() {
String listString = "";
Nodo corrente = primeiroNodo;
for (int i = 0; i < tamanhoLista; i++) {
listString += "|"+corrente.getDado() + "| ";
//listString += "|"+corrente.getDado() + "|"+corrente.getProximo()+"| ";
corrente = corrente.getProximo();
}
return listString;
}
}
public class ListaEncadeadaTeste {
public static void main(String[] args) {
// Construindo uma lista vazia
ListaEncadeada numeros = new ListaEncadeada();
System.out.println( "Qtd de itens na lista: "
+ numeros.getTamanhoLista() + "\n \n" + numeros.toString() );
numeros.insert( 7 ); // Inserindo 7 na lista
System.out.println( "Qtd de itens na lista: "
+ numeros.getTamanhoLista() + "\n \n" + numeros.toString() );
numeros.insert( 2 ); // Inserindo 2 na lista
System.out.println( "Qtd de itens na lista: "
+ numeros.getTamanhoLista() + "\n \n" + numeros.toString() );
numeros.insert( 5 ); // Inserindo 5 na lista
System.out.println( "Qtd de itens na lista: "
+ numeros.getTamanhoLista() + "\n \n" + numeros.toString() );
numeros.delete( 2 ); //Deletando um nodo da lista
System.out.println( "Qtd de itens na lista: "
+ numeros.getTamanhoLista() + "\n \n" + numeros.toString() );
numeros.delete( 7 ); //Deletando um nodo da lista
System.out.println( "Qtd de itens na lista: "
+ numeros.getTamanhoLista() + "\n \n" + numeros.toString() );
}
}
Lista duplamente encadeada
Numa lista cada elemento, ou nó, é composto normalmente por uma variável que guarda a informação e dois ponteiros (referências a endereços de memória) que permitem a ligação entre os vários nós desta lista. Este tipo de lista é conhecido por "Duplamente ligada" ou "Duplamente encadeada" exatamente pelo fato de possuir duas variáveis de controle (ponteiros) ao contrário da lista simplesmente ligada que possui somente um, o qual aponta para o próximo elemento da lista.
A função destas variáveis é guardar o endereço de memória do nó anterior e do nó posterior.
public class DuploNodo {
private int
elemento;
private DuploNodo anterior;
private
DuploNodo proximo;
public
DuploNodo(int
elemento, DuploNodo anterior, DuploNodo proximo)
{
this.elemento =
elemento;
this.anterior =
anterior;
this.proximo =
proximo;
}
public int
getElemento() {
return elemento;
}
public void
setElemento(int
elemento) {
this.elemento
= elemento;
}
public DuploNodo getAnterior()
{
return anterior;
}
public void
setAnterior(DuploNodo anterior) {
this.anterior =
anterior;
}
public
DuploNodo getProximo() {
return
proximo;
}
public
void setProximo(DuploNodo proximo)
{
this.proximo =
proximo;
}
}
public class DuplaLista {
private int tamanhoLista;
private DuploNodo primeiroNodo;
private DuploNodo nodo;
/**
* Construtor da Lista duplamente encadeada
*/
public DuplaLista() {
tamanhoLista = 0;
primeiroNodo = new DuploNodo( 0, null, null );
nodo = new DuploNodo( 0, primeiroNodo, null );
primeiroNodo.setProximo( nodo );
}
public int getTamanhoLista() {
return tamanhoLista;
}
public boolean listaVazia() {
return ( tamanhoLista == 0 );
}
public DuploNodo getPrimeiro() throws IllegalArgumentException {
if (listaVazia()) throw new IllegalArgumentException();
return primeiroNodo.getProximo();
}
public DuploNodo getUltimo() throws IllegalArgumentException {
if (listaVazia()) throw new IllegalArgumentException();
return nodo.getAnterior();
}
public DuploNodo getAnterior(DuploNodo v) throws IllegalArgumentException {
if (v == primeiroNodo) throw new IllegalArgumentException();
return v.getAnterior();
}
public DuploNodo getProximo(DuploNodo v) throws IllegalArgumentException {
if (v == nodo) throw new IllegalArgumentException();
return v.getProximo();
}
public void addPrimeiro(DuploNodo v) {
addDepois( primeiroNodo, v );
}
public void addLast(DuploNodo v) {
addAntes( nodo, v );
}
public void addDepois(DuploNodo pivo, DuploNodo novoNodo) {
DuploNodo aux = getProximo( pivo );
pivo.setProximo( novoNodo );
aux.setAnterior( novoNodo );
novoNodo.setProximo( aux );
novoNodo.setAnterior( pivo );
tamanhoLista++;
}
public void addAntes(DuploNodo pivo, DuploNodo novoNodo) {
DuploNodo aux = getAnterior( pivo );
pivo.setAnterior( novoNodo );
aux.setProximo( novoNodo );
novoNodo.setAnterior( aux );
novoNodo.setProximo( pivo );
tamanhoLista++;
}
public void remover(DuploNodo v) {
DuploNodo anterior = getAnterior( v );
DuploNodo proximo = getProximo( v );
anterior.setProximo( proximo );
proximo.setAnterior( anterior );
v.setProximo( null );
v.setAnterior( null );
tamanhoLista--;
}
public boolean hasPrev(DuploNodo v) {
return ( v != primeiroNodo );
}
public boolean hasNext(DuploNodo v) {
return ( v != nodo );
}
}
public class DuplaListaApp {
public static void main(String[] args) {
DuplaLista lista = new DuplaLista();
// Adicionando o primeiro nodo
DuploNodo pivo = null;
DuploNodo node1 = new DuploNodo( 10, null, null );
lista.addPrimeiro( node1 );
pivo = node1;
// Adicionando novo nodo, depois do ultimo, que nesse caso e o primeiro
DuploNodo node2 = new DuploNodo( 20, null, null );
lista.addDepois( pivo, node2 );
pivo = node2;
// Adicionando novo nodo, depois do ultimo
DuploNodo node3 = new DuploNodo( 30, null, null );
lista.addDepois( pivo, node3 );
pivo = node3;
// Adicionando novo nodo, depois do ultimo
DuploNodo node4 = new DuploNodo( 40, null, null );
lista.addAntes( pivo, node4 );
pivo = node4;
lista.toRemove( node3 );
String listString = "";
DuploNodo corrente = lista.getPrimeiro();
for (int i = 0; i < lista.getTamanhoLista(); i++) {
System.out.println( listString += "{"
+ corrente.getAnterior().getElemento() + "|<-" + "|"
+ corrente.getElemento() + "|->" + "|"
+ corrente.getProximo().getElemento() + "} " );
corrente = corrente.getProximo();
}
}
}
Nenhum comentário:
Postar um comentário