segunda-feira, 22 de setembro de 2008

Estrutura de Dados Java - Lista encadeada / LinkedList

Começei ontem um algoritmo para Lista Encedeada, to estudando melhor as estruturas de dados, está implementada em Java, só para estudo mesmo. Vamos dizer que esta na versão 0.1. Vou postar o código pra quem quiser. Comentários?


import java.awt.FlowLayout;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import java.util.Iterator;
import java.util.NoSuchElementException;

import javax.swing.JButton;
import javax.swing.JFrame;
import javax.swing.JOptionPane;
import javax.swing.JTextField;

public class LinkedList implements Iterable {

private Node head = null;
private Node last = null;

private int size = 0;

public void initList() {
head = null;
last = null;
size = 0;
}

public boolean isEmpty() {
return head == null;
}

public void addFirst(V info) {
Node tmp = new Node(info, head);
if(isEmpty())
last = tmp;
head = tmp;
setSize(size + 1);
}

public void addLast(V info) {
Node tmp = new Node(info, null);
if(isEmpty())
head = tmp;
else
last.next = tmp;
last = tmp;
setSize(size + 1);
}

public void add(V info) {
addLast(info);
}

public V removeFirst() {
V obj = null;
if(!isEmpty()) {
obj = head.getInfo();

if(head == last)
last = null;
head = head.getNext();
}
setSize(size - 1);
return obj;
}

public V removeLast() {
V obj = null;
if(!isEmpty()) {
Node aux = head;
obj = last.info;
if(aux.next == null) {
head = null;
last = null;
} else {
while(aux.next != last)
aux = aux.next;
aux.next = null;
last = aux;
}
}
setSize(size - 1);
return obj;
}

public V get(int index) {
V obj = null;
if(index < size) {
int i = 0;
Node n = head;
while(i < index) {
n = head.next;
i++;
}
obj = n.info;
} else {
throw new NoSuchElementException();
}
return obj;
}

public V getHeadInfo() {
return head.info;
}

public boolean contains(V obj) {
Node aux = head;
while(aux != null)
if(obj.equals(aux.getInfo()))
return true;
else
aux = aux.getNext();

return false;
}

public int size() {
return size;
}

private void setSize(int size) {
this.size = size;
if(this.size < 0)
this.size = 0;
}

public Iterator iterator() {
return new Iterator() {
Node current = head; // utilizado apenas para iteração de elementos
public boolean hasNext() {
return current != null;
}

public V next() {
V obj = current.getInfo();
current = current.getNext();

return obj;
}

public void remove() {} //não utilizado ainda
};
}

class Node {
private V info;
private Node next;

public Node(V info, Node next) {
this.info = info;
this.next = next;
}

public V getInfo() {
return info;
}

public Node getNext() {
return next;
}
}

//------------------------------------------------------------------------------
public static void main(String args[]) {
JFrame frm = new JFrame("Bla");
final JTextField tx = new JTextField(25);

JButton btInit = new JButton("Reset Lista");
JButton btSize = new JButton("Tamanho");
JButton btAddIni = new JButton("Add Inicio");
JButton btRemoveIni = new JButton("Remove Inicio");
JButton btAddFim = new JButton("Add Fim");
JButton btRemoveFim = new JButton("Remove Fim");
JButton btContains = new JButton("Contem?");
JButton btGetNode = new JButton("Get Node");
JButton btShow = new JButton("Show");
final LinkedList list = new LinkedList();

btInit.addActionListener(new ActionListener() {
public void actionPerformed(ActionEvent e) {
list.initList();
}
});

btAddIni.addActionListener(new ActionListener() {
public void actionPerformed(ActionEvent e) {
String s = tx.getText();
list.addFirst(s);
tx.setText("");
tx.requestFocus();
}
});

btRemoveIni.addActionListener(new ActionListener() {
public void actionPerformed(ActionEvent e) {
String a = list.removeFirst();
tx.setText(a);
}
});

btAddFim.addActionListener(new ActionListener() {
public void actionPerformed(ActionEvent e) {
String s = tx.getText();
list.addLast(s);
tx.setText("");
tx.requestFocus();
}
});

btRemoveFim.addActionListener(new ActionListener() {
public void actionPerformed(ActionEvent e) {
String a = list.removeLast();
tx.setText(a);
}
});

btContains.addActionListener(new ActionListener() {
public void actionPerformed(ActionEvent e) {
String s = tx.getText();
boolean result = list.contains(s);
tx.setText(""+result);
}
});

btSize.addActionListener(new ActionListener() {
public void actionPerformed(ActionEvent e) {
JOptionPane.showMessageDialog(null, list.size());
}
});

btGetNode.addActionListener(new ActionListener() {
public void actionPerformed(ActionEvent e) {
String text = tx.getText();
int index = Integer.parseInt(text);
String result = list.get(index);

JOptionPane.showMessageDialog(null, result + " - " + index);
}
});

btShow.addActionListener(new ActionListener() {
public void actionPerformed(ActionEvent e) {
String s = "";
for(String a : list)
s += a + "\n";

JOptionPane.showMessageDialog(null, s);
}
});

frm.setLayout(new FlowLayout());
frm.add(tx);
frm.add(btInit);
frm.add(btSize);
frm.add(btAddIni);
frm.add(btRemoveIni);
frm.add(btAddFim);
frm.add(btRemoveFim);
frm.add(btContains);
frm.add(btGetNode);
frm.add(btShow);

frm.setDefaultCloseOperation(JFrame.DISPOSE_ON_CLOSE);
frm.setBounds(150, 50, 310, 200);
frm.setVisible(true);
}
}

Nenhum comentário: