Fala galera, tudo tranquilo?
Você já teve interesse de conhecer como são as implementações de
Listas ? (List do C#, Java)
Basicamente, as interfaces(List) definem os tipos de operações que podem ser realizadas nas Lista. Vou escrever algo bem bacana, faremos uma implementação de Lista Imutável.
Imutabilidade
Basicamente, é uma característica de um objeto permanecer
o mesmo sempre. Quer saber mais sobre Imutabilidade: Bruno Nardini
http://www.brunonardini.com.br/artigos/favoreca-a-imutabilidade-e-a-simplicidade
A classe
String, tanto do Java quanto C# , encapsula alguns métodos de manipulação de String, como o
toUpperCase() (C# =
ToUpper()), que têm o objetivo de converter sua string para maiúsculo. Porém por baixo dos panos, o que acontece é você receberá uma nova instância, com o conteúdo de sua string antiga convertida para maiúsculo. (Você pode verificar isso nos links acima)
Já definido o que é Imutabilidade, vamos ao conceito básico de Listas Ligadas (Linked List). (
http://www.caelum.com.br/apostila-java-estrutura-dados/listas-ligadas/#5-1-solucao-classica-de-lista-ligada)
Uma
Lista Ligada é uma lista onde o elemento atual "aponta"(tem o endereço) para/do o seu próximo irmão, analisem a fotografia abaixo:
Um conceito simples, agora vamos a prática, assim podemos misturar os dois conceitos! (Imutabilidade e Linked List). No exemplo vai rolar um pouco Generics, se já sabe legal, caso não:
http://en.wikipedia.org/wiki/Generic_programming#Generics_in_Java .
Primeiro, vamos criar uma interface para nossas listas, para isso, crie um projeto novo no Eclipse, dê um nome e vamos lá:
New -> Interface
public interface List {
T cabeca();
List cauda();
List adicionaNoComeco(T elemento);
T pegaPosicao(int position);
List removePrimeiraPosicao();
}
Bom e o que é cabeça e cauda?
Cabeça é o elemento superior de nossa lista, ou seja a head da Lista.
Cauda é todo o restante da lista, é composta por sua cabeça e outra cauda, e assim respectivamente.
Nosso método
adicionaNoComeco(T elemento) recebe um parâmetro e retorna uma nova Lista com o respectivo elemento adicionado. Bem parecido com o método
removePrimeiraPosicao() que remove o primeiro elemento e retorna a cauda da lista.
Bom vamos as implementações, vamos criar uma nova classe, que podemos chamar de
No, ou seja, serão os respectivos nós de nossa Lista:
public class No implements List {
private final T cabeca;
private final List cauda;
public No(T cabeca, List cauda) {
this.cabeca = cabeca;
this.cauda = cauda;
}
@Override
public T cabeca() {
return cabeca;
}
@Override
public List cauda() {
return cauda;
}
@Override
public List adicionaNoComeco(T elemento) {
return new No(elemento, this);
}
@Override
public T pegaPosicao(int position) {
if (position == 0)
return cabeca();
return cauda.pegaPosicao(position - 1);
}
@Override
public List removePrimeiraPosicao() {
return cauda();
}
}
Entenda:
Ao criar um No, nós receberemos a cabeça (elemento) e sua respectiva cauda (List). Fora o método pegaPosicao, o restante é bem trivial, por isso não entrarei em maiores detalhes.
pegaPosicao(T elemento)
Esse método faz uso recursivo de si próprio, ou seja, ele percorre a cauda, caso o posicao não seja 0, e recursivamente ele vai caminhando de cabeça em cabeça, das caudas, para encontrar o elemento desejado. Bem simples e objetivo.
Certo, feito isso, fica simples entender algumas coisas, a primeira de todas, como será o fim de nossa lista?
Temos que saber onde a Lista tem seu final e como o fazemos?
Faremos outra implementação de List, que agora chamaremos de Nil, será o
fim de nossa lista.
public class Nil implements List {
@Override
public T cabeca() {
throw new RuntimeException("Lista Vazia");
}
@Override
public List cauda() {
throw new RuntimeException("Lista Vazia");
}
@Override
public List adicionaNoComeco(T elemento) {
return new No(elemento, this);
}
@Override
public T pegaPosicao(int position) {
throw new RuntimeException("A lista não possui elementos");
}
@Override
public List removePrimeiraPosicao() {
throw new RuntimeException(
"Impossível remover elementos de uma lista vazia");
}
}
O
Nil, que como dito acima, tem o objetivo de ser o
fim da lista, a única coisa que podemos escrever interessante ao seu respeito é que a reescrita do método adicionaNoComeco vai retornar uma nova instância de No, ou seja, iniciaremos uma lista.
Feito isso, temos um
Container, o List, que armazena valores e
possui funções para alterar os dados internos, isso nos ajuda muito com a
Imutabilidade, nos sentimos mais seguros e sabemos que nosso objeto não será um mutante, que pode perder/alterar seus valores em tempo de execução.
Bom galera, o conceito de hoje foi bem bacana e construtivo, é o que tenho mais feito no meu treinamento com o Jonas, aqui na Lambda3. Espero que tenha ficado claro.
Para os C# manjadores, no meu
Github tem um exemplo parecido escrito em C#. Para os Javas, deixarei outro repositório no
GitHub já com os testes implementados.
Qualquer dúvida ou sugestão email-me:
abner.terribili@lambda3.com.br ou comente abaixo!
Valeu galera!
