terça-feira, 26 de fevereiro de 2008

Estruturas de dados com JAVA - Lista encadeada circular

Em uma lista circular, não existem o primeiro e o último nó da mesma forma como explicado nos posts sobre listas simplesmente encadeadas e duplamente encadeadas. Geralmente usamos sentinelas de cabeçalho e rodapé nas estruturas anteriores, porém em uma lista circular, o último elemento possui como próximo, o primeiro elemento. Para percorrer uma lista circular, então é necessário definir um tipo de cursor, que nada mais é do que um nó(elemento) corrente na lista.

Então como nos outros posts, seguem os códigos para melhor entendimento:
A estrutura de dado já está definida conforme o post Lista Simplesmente Encadeada.

A implementação da lista circular segue abaixo:


public class CircleList {

private Node cursor;
private int size;

/** Creates a new instance of CircleList */
public CircleList() {
cursor = null;
size = 0;
}

public int size() {
return size;
}

public Node getCursor() {
return cursor;
}

public void advance() {
cursor = cursor.getNext();
}

public void add(Node v) {
if (cursor == null) {
v.setNext(v);
cursor = v;
} else {
v.setNext(cursor.getNext());
cursor.setNext(v);
}
size++;
}

public Node remove() throws IllegalArgumentException {

if (cursor == null)
throw new IllegalArgumentException("lista vazia");

Node aux = cursor.getNext();
if (aux == cursor)
cursor = null;
else {
cursor.setNext(aux.getNext());
aux.setNext(null);
}

size--;
return aux;
}
}



e o exemplo de utilização segue também abaixo:


public class Principal {

private CircleList lista;

public Principal() {
lista = new CircleList();

lista.add(new Node("A", null));
lista.add(new Node("B", null));
lista.add(new Node("C", null));
}

public void printLista() {
Node node = lista.getCursor();
for(int i=0; i<lista.size(); i++) {
System.out.println("elemento " + i + " = " + node.getElement());
lista.advance(); node = lista.getCursor();
}
}

public void clear() {
while(true) {
try {
Node node = lista.remove();
System.out.println("elemento removido = " + node.getElement());
} catch (IllegalArgumentException e) {
System.out.println(e.getMessage());
break;
}
}
}

public static void main(String[] args) {
Principal me = new Principal();
me.printLista();

// apos imprimir os elementos testa remover tudo
me.clear();
}

}



No próximo post, demonstrarei como implementar um tipo de ordenação em uma lista duplamente encadeada.

2 comentários:

  1. achei legal, ajuda os iniciantes. Gostaria tbm de uma ideia para inserir e remover. Obrigada

    ResponderExcluir