Dia 23

Trabalhar com estruturas de dados em Java

Michael Morrison

• Estrutura de dados Fundamentals
• O padrão estruturas de dados de Java
  • Listas
  • Jogos de brocas
  • Vetores
  • Pilhas
  • Dicionários
  • Tabelas hash
• A criação das suas próprias estruturas de dados
  • Fundamentos de lista ligados
  • Implementar uma lista ligada
• Sumário
• Perguntas e Respostas
  

Poucos programas podem desenvolver-se sem pelo menos algum uso de estruturas de dados, que são responsáveis por guardar e manter a informação usada por um programa. Se desenvolve as suas próprias estruturas de dados do zero ou confia nos desenvolvidos e testados por outros, precisará de usar indubitavelmente estruturas de dados em algum momento no seu Java programando diligências. A lição de hoje dá uma olhada em estruturas de dados como se relacionam a Java. Cobre os seguintes tópicos:

• Fundamentos de estrutura de dados
• As estruturas de dados de Java padrão
• A criação das suas próprias estruturas de dados

Até ao fim da lição de hoje, terá uma boa ideia de que estruturas de dados estão prontamente disponíveis nos pacotes de Java padrão, junto com algumas estruturas de dados que pode implementar você mesmo sem demasiada dor. Vamos começar!

Estrutura de dados Fundamentals

Como algoritmos em geral, as estruturas de dados são um daqueles conceitos gerais nas Ciências da Computação cuja utilidade se estende distante e largo. Consequentemente, uma compreensão sólida de estruturas de dados e quando aplicar certos é a marca de comércio de qualquer bom programador. A programação de Java é não diferente, e deve tomar estruturas de dados não menos seriamente em Java do que em qualquer outra língua. Somente porque muitos programas Java vêm na forma de applets, que parecem mais atraentes e menos auspiciosos do que C ou C ++ aplicações, não significa que não confiam em um meio sólido de armazenamento e manipulação de dados.

Quase cada Java applet trabalha com a informação até certo ponto. Mesmo a animação muito simples applets que expõem uma série de imagens deve guardar de qualquer maneira as imagens de tal modo que as imagens podem referir-se rapidamente. Neste exemplo, uma estrutura de dados muito elementar como uma tabela poderia ser a melhor solução, desde tudo que se necessita da estrutura de dados é o armazenamento de múltiplas imagens. Ainda assim, considere o fato que cada programa tem o seu próprio jogo de exigências de dados que muito afetam a aplicabilidade de estruturas de dados diferentes. Se não entender a variedade cheia de programar opções quanto a estruturas de dados, vai se encontrar que tenta usar uma tabela em cada programa que escreve. Esta tendência de confiar em uma solução de todos os seus problemas de programação terminará de adquiri-lo na preocupação. Em outras palavras, entendendo como usar uma grande variedade de estruturas de dados, alarga a sua perspectiva em como resolver os problemas inevitáveis que resultam de novos desafios de programação.

Mencionei tabelas que são uma estrutura de dados muito simples. De fato, do lado de fora de próprias variáveis de membro, as tabelas são a estrutura de dados mais simples apoiada por Java. Uma tabela é simplesmente uma série agregada de elementos de dados do mesmo tipo. Digo que as tabelas são agregadas porque se tratam como uma entidade única, como qualquer outra variável de membro. Contudo, de fato contêm múltiplos elementos que podem acessar-se independentemente. Baseado nesta descrição, é lógico que as tabelas sejam úteis qualquer tempo tem de guardar e acessar um grupo de informação que é todo do mesmo tipo. Por exemplo, pode guardar as suas picaretas de uma loteria em uma tabela de números inteiros. Contudo, a limitação notória de tabelas é que não podem modificar-se no tamanho para acomodar mais (ou menos) elementos. Isto significa que não pode acrescentar novos elementos a uma tabela que já é cheia.

Resulta que as exigências de dados de muitos programas práticos conseguem longe além o que as tabelas fornecem. Em outras línguas, muitas vezes é necessário desenvolver estruturas de dados alfandegárias sempre que as exigências ultrapassem tabelas. Contudo, a biblioteca de classe de Java fornece o grupo de estruturas de dados no pacote de java.util que lhe dão muito mais flexibilidade em como aproximar a organização e a manipulação de dados. Ainda podem haver situações nas quais estas estruturas de dados padrão não ajustam as suas necessidades, em que caso terá de escrever o seu próprio. Aprenderá como implementar as suas próprias estruturas de dados alfandegárias depois na lição de hoje.

O padrão estruturas de dados de Java

As estruturas de dados fornecidas pelo pacote de serviço de Java são muito potentes e executam uma ampla variação de funções. Estas estruturas de dados compõem-se da seguinte interface e cinco classes:

• Enumeration
• BitSet
• Vector
• Stack
• Dictionary
• Hashtable

A interface de Enumeration não é uma estrutura de dados, mas é muito importante dentro do contexto de outras estruturas de dados. A interface de Enumeration define um meio de recuperar elementos sucessivos de uma estrutura de dados. Por exemplo, Enumeration define um método chamado nextElement que se usa para adquirir o seguinte elemento em uma estrutura de dados que contém múltiplos elementos.

A classe de BitSet implementa um grupo de bits ou bandeiras, que podem estabelecer-se e compensar-se individualmente. Esta classe é muito útil em casos onde tem de acompanhar o grupo de valores booleanos; somente destina um bocado a cada valor e estabelece-o ou compensa-o como apropriado.

A classe de Vector é semelhante a uma tabela de Java tradicional, exceto que pode crescer segundo a necessidade para acomodar novos elementos. Como uma tabela, os elementos de um objeto de Vector podem acessar-se via um índice no vetor. A coisa bonita sobre a utilização da classe de Vector consiste em que não tem de incomodar-se com a colocação dele a um tamanho específico depois da criação; encolhe-se e cresce automaticamente quando necessário.

A classe de Stack implementa uma pilha de último em primeiro fora (LIFO) de elementos. Pode pensar em uma pilha literalmente como uma pilha vertical de objetos; quando acrescenta um novo elemento, empilha-se em cima dos outros. Quando puxa um elemento da pilha, solta o topo. Em outras palavras, o elemento último que acrescentou à pilha é o primeiro a voltar de.

A classe de Dictionary é uma classe abstrata que define uma estrutura de dados para fazer o mapa de chaves a valores. Isto é útil em casos onde quer ser capaz de acessar dados via uma determinada chave em vez de um índice de número inteiro. Desde que a classe de Dictionary é abstrata, só fornece a armação para uma estrutura de dados feita o mapa pela chave em vez de uma implementação específica.

Uma implementação real de uma estrutura de dados feita o mapa pela chave fornece-se pela classe de Hashtable. A classe de Hashtable fornece um meio de organizar dados baseados em alguma estrutura-chave definida pelos usuários. Por exemplo, em uma tabela hash de lista de endereços pode guardar e dados de tipo baseados em uma chave como código de CÓDIGO POSTAL em vez de no nome de uma pessoa. A significação específica de chaves com respeito a tabelas hash é totalmente dependente do uso da tabela hash e os dados que contém.

Isto bastante bem sumaria as estruturas de dados fornecidas pelo pacote de serviço de Java. Agora que tem uma compreensão superficial deles, vamos cavar em cada um em um pouco mais detalhe e ver como trabalham.

Listas

A interface de Enumeration fornece um meio padrão da repetição por uma lista de elementos em sequência guardados, que é uma tarefa comum de muitas estruturas de dados. Embora não possa usar a interface do lado de fora do contexto de uma determinada estrutura de dados, entendendo como trabalha o porá bem no seu caminho à compreensão de outras estruturas de dados de Java. Com isto em mente, dê uma olhada nos só dois métodos definidos pela interface de Enumeration:

public abstract boolean hasMoreElements();
public abstract Object nextElement();

O método de hasMoreElements usa-se para determinar se a lista contém mais elementos. Chamará tipicamente este método para ver se pode continuar repetindo por meio de uma lista. Um exemplo disto chama hasMoreElements na cláusula condicional de um laço de while que repete por meio de uma lista.

O método de nextElement é responsável por recuperar de fato o seguinte elemento em uma lista. Se não mais elementos estiverem na lista, nextElement lançará uma exceção de NoSuchElementException. Desde que quer evitar gerar exceções sempre que possível, sempre deve usar hasMoreElements em conjunto com nextElement para assegurar-se que há outro elemento para recuperar. O seguinte é um exemplo de um laço de while que usa estes dois métodos para repetir por um objeto de estrutura de dados que implementa a interface de Enumeration:

// e is an object that implements the Enumeration interface
while (e.hasMoreElements()) {
  Object o = e.nextElement();
  System.out.println(o);
}

Este código de mostra imprime os conteúdos de uma lista usando métodos de nextElement e o hasMoreElements. Bastante simples!

Jogos de brocas

A classe de BitSet é útil sempre que tenha de representar um grupo de bandeiras booleanas. A coisa bonita sobre a classe de BitSet consiste em que lhe permite usar bits individuais para guardar valores booleanos sem o desordem da necessidade de extrair valores de bit usando bitwise operações; simplesmente refere-se a cada bit usando um índice. Outra característica bonita sobre a classe de BitSet é que automaticamente cresce para representar o número de bits necessitados por um programa. A figura 23.1 mostra a organização lógica de um bocado a estrutura de dados de jogo.

A figura 23.1: A organização lógica de um bocado estrutura de dados de jogo.

Por exemplo, pode usar BitSet como um objeto que tem um número de atributos que podem modelar-se facilmente por valores booleanos. Desde que os bits individuais em um bocado o jogo acessam-se via um índice, pode definir cada atributo como um valor de índice constante:

class someBits {
  public static final int readable = 0;
  public static final int writeable = 1;
  public static final int streamable = 2;
  public static final int flexible = 3;
}

Note que os atributos se destinam aumentando valores, começando com 0. Pode usar estes valores para adquirir e estabelecer os bits apropriados em um bocado o jogo. Mas primeiro, tem de criar um objeto de BitSet:

BitSet bits = new BitSet();

Este construtor cria um bocado estabelecido sem tamanho especificado. Também pode criar um bocado estabelecido com um tamanho específico:

BitSet bits = new BitSet(4);

Isto cria um bocado o jogo que contém quatro campos de bit booleanos. Apesar do construtor usado, todos os bits em novos jogos de brocas estabelecem-se inicialmente em false. Uma vez que estabeleceu um bocado criado, pode estabelecer facilmente e compensar os bits usando o set e métodos de clear junto com as constantes de bit que definiu:

bits.set(someBits.writeable);
bits.set(someBits.streamable);
bits.set(someBits.flexible);
bits.clear(someBits.writeable);

Neste código, o writeable, streamable e os atributos de flexible estabelecem-se, e logo o writeable mordeu compensa-se. Note que o nome totalmente qualificado se usa para cada atributo, desde que os atributos se declaram como estáticos na classe de someBits.

Pode adquirir o valor de bits individuais em um bocado o jogo usando o método de get:

boolean canIWrite = bits.get(someBits.writeable);

Pode descobrir quantos bits se estão representando por um bocado o jogo usando o método de size. Um exemplo disto segue:

int numBits = bits.size();

A classe de BitSet também fornece outros métodos para executar comparações e operações bitwise em jogos de brocas como AND, OR e XOR. Todos estes métodos tomam um objeto de BitSet como o seu único parâmetro.

Vetores

A classe de Vector implementa uma tabela growable de objetos. Desde que a classe de Vector é responsável por crescer-se segundo a necessidade para apoiar mais elementos, tem de decidir quando e por quanto crescer como os novos elementos se acrescentam. Pode controlar facilmente este aspecto de vetores depois da criação. Antes de entrar isto, contudo, dá uma olhada em como criar um vetor básico:

Vector v = new Vector();

Isto é quase tão simples como vem! Este construtor cria um vetor à revelia que não contém nenhum elemento. De fato, todos os vetores são vazios depois da criação. Um dos atributos importantes para como uns tamanhos de vetor ele mesmo são a capacidade inicial de um vetor, que é para quantos os elementos o vetor alocam a memória à revelia.

O seguinte código mostra como criar um vetor com uma capacidade especificada:

Vector v = new Vector(25);

Este vetor cria-se para apoiar imediatamente até 25 elementos. Em outras palavras, o vetor progredirá e alocará bastante memória para apoiar 25 elementos. Uma vez que 25 elementos acrescentaram-se, contudo, o vetor deve decidir como cultivar-se para aceitar mais elementos. Pode especificar o valor pelo qual um vetor cultiva a utilização ainda outro construtor de Vector:

Vector v = new Vector(25, 5);

Este vetor tem um tamanho inicial de 25 elementos e crescerá em incrementos de 5 elementos sempre que o seu tamanho cresça a mais de 25 elementos. Isto significa que o vetor pulará primeiro para 30 elementos no tamanho, então 35, e assim por diante. Um mais pequeno cresce o valor de um vetor resulta na gestão de memória mais eficiente, mas à custa de mais execução em cima desde que mais alocações de memória se realizam. De outro lado, um maior crescem o valor resulta em menos alocações de memória, mas às vezes a memória pode desperdiçar-se se não usar todo o extra espaço criado.

Diferentemente de com tabelas, somente não pode usar suportes de forma triangular quadrados ([]) para acessar os elementos em um vetor; tem de usar métodos definidos na classe de Vector. Para acrescentar um elemento a um vetor, usa o método de addElement:

v.addElement("carrots");
v.addElement("broccoli");
v.addElement("cauliflower");

Este código mostra como acrescentar algumas cadeias vegetais a um vetor. Para acrescentar a cadeia última ao vetor, pode usar o método de lastElement:

String s = (String)v.lastElement();

O método de lastElement recupera o elemento último acrescentado ao vetor. Note que tem de lançar o valor de retorno de lastElement, desde que a classe de Vector se projeta para trabalhar com a classe de Object genérica. Embora lastElement certamente tenha a sua utilidade, encontrará provavelmente mais uso com o método de elementAt, que lhe permite ao índice em um vetor recuperar um elemento. O seguinte é um exemplo de usar o método de elementAt:

String s1 = (String)v.elementAt(0);
String s2 = (String)v.elementAt(2);

Desde que os vetores são zero baseado, a primeira chamada a elementAt recupera a cadeia de "carrots", e a segunda chamada recupera a cadeia de "cauliflower". Tão como pode recuperar um elemento em um determinado índice, também pode acrescentar e retirar elementos em um índice usando métodos de removeElementAt e o insertElementAt:

v.insertElementAt("squash", 1);
v.insertElementAt("corn", 0);
v.removeElementAt(3);

A primeira chamada a insertElementAt insere um elemento no índice 1, entre cadeias de "broccoli" e o "carrots". O "broccoli" e as cadeias de "cauliflower" sobem-se um espaço no vetor para acomodar a cadeia de "squash" inserida. A segunda chamada a insertElementAt insere um elemento no índice 0, que é o começo do vetor. Neste caso, todos os elementos existentes sobem-se um espaço no vetor para acomodar a cadeia de "corn" inserida. Neste ponto, os conteúdos do vetor parecem a isto:

"corn"
"carrots"
"squash"
"broccoli"
"cauliflower"

A chamada a removeElementAt retira o elemento no índice 3, que é a cadeia de "broccoli". Os conteúdos resultantes do vetor compõem-se das seguintes cadeias:

"corn"
"carrots"
"squash"
"cauliflower"

Pode usar o método de setElementAt para modificar um elemento específico:

v.setElementAt("peas", 1);

Este método substitui a cadeia de "carrots" com a cadeia de "peas", resultando nos seguintes conteúdos de vetor:

"corn"
"peas"
"squash"
"cauliflower"

Se quiser desocupar o vetor completamente, pode retirar todos os elementos com o método de removeAllElements:

v.removeAllElements();

A classe de Vector também fornece alguns métodos para trabalhar com elementos sem usar índices. Estes métodos de fato pesquisam no vetor por um determinado elemento. O primeiro destes métodos é o método de contains, que simplesmente verifica para ver se um elemento está no vetor:

boolean isThere = v.contains("celery");

Outro método que trabalha nesta maneira é o método de indexOf, que acha o índice de um elemento baseado no próprio elemento:

int i = v.indexOf("squash");

O método de indexOf devolve o índice do elemento em questão se estiver no vetor, ou
-1 se não. O método de removeElement trabalha de mesmo modo em que retira um elemento baseado no próprio elemento em vez de em um índice:

v.removeElement("cauliflower");

Se se interessar no trabalho com todos os elementos em um vetor em sequência, pode usar o método de elements, que devolve uma lista dos elementos:

Enumeration e = v.elements();

Lembre de antes na lição de hoje que pode usar uma lista para dar passos por elementos em sequência. Neste exemplo, pode trabalhar com a lista e usando os métodos definidos pela interface de Enumeration.

Pode encontrar-se que quer trabalhar com o tamanho de um vetor. Afortunadamente, a classe de Vector fornece alguns métodos para determinar e manipular o tamanho de um vetor. Em primeiro lugar, o método de size determina o número de elementos no vetor:

int size = v.size();

Se quiser estabelecer explicitamente o tamanho de um vetor, pode usar o método de setSize:

v.setSize(10);

O método de setSize expande-se ou trunca o vetor para acomodar o novo tamanho especificado. Se o vetor se estender por causa de um tamanho maior, os elementos nulos inserem-se como os elementos recentemente acrescentados. Se o vetor for truncado, qualquer elemento em índices além do tamanho especificado descarta-se.

Se lembrar, os vetores têm dois atributos diferentes que se relacionam com tamanho: tamanho e capacidade. O tamanho é o número de elementos no vetor e a capacidade é o montante da memória alocada para manter todos os elementos. A capacidade sempre é maior do que ou igual ao tamanho. Pode forçar a capacidade de combinar exatamente com o tamanho usando o método de trimToSize:

v.trimToSize();

Também pode verificar para ver qual a capacidade é, usando o método de capacity:

int capacity = v.capacity();

Encontrará que a classe de Vector é uma das estruturas de dados mais úteis fornecidas em Java API. Esperamos que esta viagem da classe dá-lhe uma ideia de como os vetores potentes são e como fácil deve usá-los.

Pilhas

As pilhas são uma estrutura de dados clássica usada para modelar a informação que se acessa em uma ordem específica. A classe de Stack em Java implementa-se como uma pilha de último em primeiro fora (LIFO), que significa que o item último acrescentado à pilha é o primeiro a voltar de. A figura 23.2 mostra a organização lógica de uma pilha.

A figura 23.2: A organização lógica de uma estrutura de dados de pilha.

Pode estar admirando-se da Figura 23.2 porque os números dos elementos não combinam com a sua posição do topo da pilha. Tenha em mente que os elementos se acrescentam ao topo, portanto Element0, que está no fundo, foi o primeiro elemento acrescentado à pilha. De mesmo modo, Element3, que está no topo, é o elemento último acrescentado à pilha. Também, desde que Element3 está em cima da pilha, será o primeiro em voltar de.

A classe de Stack só define um construtor, que é um construtor à revelia que cria uma pilha vazia. Usa este construtor para criar uma pilha como isto:

Stack s = new Stack();

Acrescenta novos elementos a uma pilha usando o método de push, que empurra um elemento para o topo da pilha:

s.push("One");
s.push("Two");
s.push("Three");
s.push("Four");
s.push("Five");
s.push("Six");

Este código empurra seis cadeias para a pilha, com a cadeia última ("Six") resto no topo. Estoura os elementos derrubam a pilha usando o método de pop:

String s1 = (String)s.pop();
String s2 = (String)s.pop();

Este código põe de repente duas cadeias últimas da pilha, deixando quatro primeiro resto de cadeias. Este código resulta na variável de s1 que contém a cadeia de "Six" e a variável de s2 que contém a cadeia de "Five".

Se quiser adquirir o elemento superior na pilha sem pô-lo de repente de fato da pilha, pode usar o método de peek:

String s3 = (String)s.peek();

Esta chamada a peek devolve a cadeia de "Four" mas deixa a cadeia na pilha. Pode procurar um elemento na pilha usando o método de search:

int i = s.search("Two");

O método de search devolve a distância do topo da pilha do elemento se se encontrar, ou -1 se não. Neste caso, a cadeia de "Two" é o terceiro elemento do topo, portanto o método de search devolve 2 (zero baseado).

O único outro método definido na classe de Stack é empty, que determina se uma pilha é vazia:

boolean isEmpty = s.empty();

Embora talvez não exatamente tão útil como a classe de Vector, a classe de Stack forneça a funcionalidade para uma estrutura de dados muito comum e estabelecida.

Dicionários

A classe de Dictionary define uma armação para implementar uma estrutura de dados feita o mapa pela chave básica. Embora não possa criar de fato objetos de Dictionary desde que a classe é abstrata, ainda pode aprender muito sobre a modelagem de dados feita o mapa pela chave aprendendo como a classe de Dictionary trabalha. Pode pôr a aproximação feita o mapa pela chave de trabalhar usando a classe de Hashtable, que se consegue de Dictionary, ou conseguindo a sua própria classe de Dictionary. Aprende sobre a classe de Hashtable na seguinte seção da lição de hoje.

A classe de Dictionary define um meio de guardar a informação baseada em uma chave. Isto é semelhante de alguns modos a como a classe de Vector trabalha, nisto os elementos em um vetor acessam-se via um índice, que é um tipo específico da chave. Contudo, as chaves na classe de Dictionary podem ser quase algo. Pode criar a sua própria classe para usar como as chaves para acessar e manipular dados em um dicionário. A figura 23.3 mostra como as chaves fazem o mapa a dados em um dicionário.

A figura 23.3: A organização lógica de uma estrutura de dados de dicionário.

A classe de Dictionary define vários métodos para trabalhar com os dados guardados em um dicionário. Todos estes métodos definem-se como resumo, significando que as classes derivadas terão de implementar todos eles para ser de fato úteis. O put e os métodos de get usam-se para pôr objetos no dicionário e recobrá-los. A assunção de dict é um Dictionary - classe derivada que implementa estes métodos, as seguintes demonstrações de código como usar o método de put para acrescentar elementos a um dicionário:

dict.put("small", new Rectangle(0, 0, 5, 5));
dict.put("medium", new Rectangle(0, 0, 15, 15));
dict.put("large", new Rectangle(0, 0, 25, 25));

Este código acrescenta três retângulos ao dicionário, usando cadeias como as chaves. Para adquirir um elemento do dicionário, usa o método de get e especifica a chave apropriada:

Rectangle r = (Rectangle)dict.get("medium");

Também pode retirar um elemento do dicionário com uma chave usando o método de remove:

dict.remove("large");

Pode descobrir quantos elementos estão no dicionário usando o método de size, muito como fez com a classe de Vector:

int size = dict.size();

Também pode verificar se o dicionário é a utilização vazia do método de isEmpty:

boolean isEmpty = dict.isEmpty();

Finalmente, a classe de Dictionary inclui dois métodos para enumerar as chaves e valoriza contido dentro de: keys e elements. O método de keys devolve uma lista que contém todas as chaves contidas em um dicionário, enquanto o método de elements devolve uma lista de todos os valores feitos o mapa pela chave contidos. O seguinte é um exemplo de recuperar ambas as listas:

Enumeration keys = dict.keys();
Enumeration elements = dict.elements();

Observe que desde que fazem o mapa de chaves a elementos em uma base individual, estas listas são do comprimento igual.

Tabelas hash

A classe de Hashtable consegue-se de Dictionary e fornece uma implementação completa de uma estrutura de dados feita o mapa pela chave. Semelhante a dicionários, as tabelas hash permitem-lhe guardar dados baseados em algum tipo da chave. Diferentemente de dicionários, as tabelas hash mandam associar uma eficiência com eles definido pelo fator de carga da mesa.

O fator de carga de uma tabela hash é um número entre 0,0 e 1.0 que determina como e quando a tabela hash aloca o espaço de mais elementos.

Como vetores, as tabelas hash têm uma capacidade, que é o montante da memória alocada para a mesa. As tabelas hash alocam mais memória comparando o tamanho atual da mesa com o produto da capacidade e o fator de carga. Se o tamanho da tabela hash exceder este produto, a mesa aumenta a sua capacidade refazendo-se.

Os fatores de carga mais perto a 1,0 resultam em um uso mais eficiente da memória à custa de um tempo de busca mais longo de cada elemento. Semelhantemente os fatores de carga mais perto a 0,0 resultam em buscas mais eficientes mas também tendem a ser mais desperdiçadores com a memória. Determinar o fator de carga das suas próprias tabelas hash é realmente dependente do uso da tabela hash e se a sua prioridade está em eficiência de memória ou realização.

Cria tabelas hash usando um de três métodos. O primeiro método cria uma tabela hash à revelia:

Hashtable hash = new Hashtable();

O segundo construtor cria uma tabela hash com a capacidade inicial especificada:

Hashtable hash = new Hashtable(20);

Finalmente, o terceiro construtor cria uma tabela hash com a capacidade inicial especificada e fator de carga:

Hashtable hash = new Hashtable(20, 0.75);

Todos os métodos abstratos definidos em Dictionary implementam-se na classe de Hashtable. Desde que estes métodos executam o exato a mesma função em Hashtable, não há necessidade de cobri-los novamente. Contudo, enumeram-se aqui somente portanto terá uma ideia de que suporte Hashtable fornece:

elements
get
isEmpty
keys
put
remove
size

Além destes métodos, a classe de Hashtable implementa alguns outros que executam funções específicas para o apoio de tabelas hash. Um destes é o método de clear, que compensa uma tabela hash de todas as suas chaves e elementos:

hash.clear();

O método de contains usa-se para ver se um objeto se guarda na tabela hash. Este método procura um valor de objeto na tabela hash em vez de uma chave. O seguinte código mostra como usar o método de contains:

boolean isThere = hash.contains(new Rectangle(0, 0, 5, 5));

Semelhante a contains, o método de containsKey procura uma tabela hash, mas procura baseado em uma chave em vez de um valor:

boolean isThere = hash.containsKey("Small");

Mencionei antes que uma tabela hash se refará quando decide que deve aumentar a sua capacidade. Pode forçar uma coisa refeita você mesmo chamando o método de rehash:

hash.rehash();

Isto bastante bem sumaria os métodos importantes implementados pela classe de Hashtable. Embora tenha visto todos os métodos, ainda pode estar admirando-se exatamente como a classe de Hashtable é útil. O uso prático de uma tabela hash está de fato na representação de dados que são demasiado demorados para procurar ou referir pelo valor. Em outras palavras, as tabelas hash muitas vezes entram práticas quando trabalha com dados complexos, onde é muito mais eficiente acessar os dados usando uma chave em vez de comparando os próprios objetos de dados. Além disso, as tabelas hash tipicamente computam uma chave de elementos, que se chama um código de bagunça. Por exemplo, um objeto como uma cadeia pode ter um código de bagunça de número inteiro computado para ele que unicamente representa a cadeia. Quando um ramo de cadeias se guarda em uma tabela hash, a mesa pode acessar as cadeias usando códigos de bagunça de número inteiro ao contrário da utilização dos conteúdos das próprias cadeias. Isto resulta na procura muito mais eficiente e recuperar capacidades.

Esta técnica de computação e utilização de códigos de bagunça de armazenamento de objeto e referência explora-se pesadamente em todas as partes do sistema de Java. Isto é evidente no fato que o pai de todas as classes, Object, define um método de hashCode que se ignora na maior parte de classes de Java padrão. Qualquer classe que define um método de hashCode pode guardar-se eficientemente e acessar-se em uma tabela hash. Uma classe que deseja picar-se também deve implementar o método de equals, que define um modo de contar se dois objetos são iguais. O método de equals normalmente somente executa uma comparação direta de todas as variáveis de membro definidas em uma classe.

As tabelas hash são uma estrutura de dados extremamente potente que quererá provavelmente integrar em alguns dos seus programas que manipulam grandes montantes de dados. O fato que assim se apoiam largamente em Java API via a classe de Object deve dar-lhe uma pista quanto à sua importância na programação de Java.

A criação das suas próprias estruturas de dados

Embora o pacote de serviço de Java forneça algumas estruturas de dados muito potentes e úteis, podem haver situações nas quais precisa de algo um pouco diferente. Estimulo-o a aproveitar ao máximo as estruturas de dados de Java padrão sempre que possível, desde a reutilização de código estável sempre é uma solução mais inteligente do que a escrita do seu próprio código. Contudo, em casos onde as estruturas de dados padrão somente não parecem ajustar-se, precisaria de chamar a sua atenção em direção a outras opções.

Durante o resto da lição de hoje aprenderá todos sobre uma destas outras opções. Mais especificamente, aprenderá sobre listas ligadas, que são um tipo muito útil da estrutura de dados não fornecida nas estruturas de dados de Java padrão. Não só aprenderá sobre listas ligadas, mas também desenvolverá a sua própria classe de lista ligada que pode reutilizar nos seus próprios programas Java. Verá que a criação de estruturas de dados alfandegárias não é tudo que difícil. Vamos começar!

Fundamentos de lista ligados

Como vetores e tabelas, as listas ligadas usam-se para guardar uma lista sequente de objetos. A diferença primária entre estas estruturas de dados é que as tabelas e os vetores são melhores no momento da referência de elementos via um índice numérico, ao passo que as listas ligadas são melhores no momento do acesso de dados em uma maneira puramente sequente. Em outras palavras, as listas ligadas não se ajustam para o tipo do acesso casual fornecido por tabelas e vetores. Isto pode parecer uma limitação de listas ligadas, mas é de fato o que os faz únicos como uma estrutura de dados; são muito mais eficientes quando vem a soma, inserção e remoção de elementos.

Para adquirir uma melhor ideia de porque as listas ligadas mandam mencionar as propriedades, dê uma olhada na organização lógica de listas ligadas mostradas na Figura 23.4.

A figura 23.4: A organização lógica de uma estrutura de dados de lista duplamente ligada.

Os dados mostram a lista ligada que tem uma partida distinta e fim, que é um tanto diferente de tabelas e vetores. Com certeza as tabelas e os vetores têm um primeiro elemento e um elemento último, mas os elementos não têm mais significação do que nenhum outro elemento. A partida e o fim de listas ligadas é uma exigência estrita desde que as listas ligadas não mantêm elementos em um montante fixo da memória. Isto de fato faz menção da diferença mais grande entre listas ligadas e vetores/tabelas. As listas ligadas simplesmente mantêm referências para a partida e elementos de fim contidos dentro de, ao passo que os vetores e as tabelas contêm referências para todos dos seus elementos.

Outro ponto principal para observar da Figura 23.4 é que cada elemento em uma lista ligada contém uma referência tanto para o elemento antes como para o elemento depois dele. Isto é como os elementos em listas ligadas se acessam: atravessando a lista pelas referências para elementos sucessivos. Em outras palavras, para adquirir o terceiro elemento em uma lista ligada, tem de começar com o primeiro elemento e seguir a sua referência para o segundo elemento, e logo repetir o processo para vir ao terceiro elemento. Isto pode parecer um processo tedioso, mas de fato trabalha bastante bem em algumas situações.

Na discussão até aqui, encobri uma delicadeza com respeito a listas ligadas, e é os dois tipos de listas ligadas. O tipo mostrado na Figura 23.4 chama-se uma lista duplamente ligada porque contém referências tanto para o elemento depois como para o elemento que precede um determinado elemento. Outro tipo popular da lista ligada é a lista isoladamente ligada, onde cada elemento contém só uma referência para o elemento depois dele. A figura 23.5 mostra a organização lógica de uma lista isoladamente ligada.

A figura 23.5: A organização lógica de uma estrutura de dados de lista isoladamente ligada.

Desde que as listas duplamente ligadas tendem a ser mais gerais e por isso têm uma mais larga variedade da aplicação, vai se concentrar neles na lição de hoje. Além disso, uma lista duplamente ligada é realmente somente uma lista isoladamente ligada com mais características, que significa que pode usá-la como uma lista isoladamente ligada se quiser.

Implementar uma lista ligada

Agora que tem uma ideia de qual uma lista ligada é, vamos adiante e tome um golpe no momento do desenvolvimento da classe de lista ligada de um totalmente funcionamento. Antes de pular nos detalhes de uma implementação de lista ligada específica, contudo, consideram o fato que a classe de lista ligada que desenvolve é de fato uma extensão às estruturas de dados de Java padrão sobre as quais aprendeu antes hoje. Isto significa que é à sua vantagem para pretender a classe ajustar-se bem com o desenho das estruturas de dados existentes. Uma boa aproximação, então, seria modelar a classe de lista ligada em volta da classe de Vector, pelo menos com respeito a algumas técnicas básicas de manipular elementos por métodos. A razão disto é assim alguém mais que usa a sua classe de lista ligada pode ver facilmente como usar a classe baseada na sua compreensão de outras classes de Java padrão como Vector. Esta mentalidade quanto a aumento das classes de Java padrão é muito importante quando vem à escrita de código reutilizável.

Embora tenha discutido a implementação de lista ligada quanto a uma classe única, resulta que se precisa de algumas classes para construir realisticamente uma lista ligada completa. Estas classes compõem-se de uma classe de lista ligada, uma classe de entrada de lista ligada e uma classe de lista de lista ligada. A classe de lista ligada modela a própria lista e é a única classe com a qual cada um que usa a lista ligada entrará no contato. Outras duas classes são classes de ajudante que fornecem algum tipo de nos bastidores a funcionalidade da classe de lista ligada. A classe de entrada de lista ligada modela um elemento individual dentro da lista ligada, e a classe de enumerador de lista ligada fornece o suporte da interface de Enumeration.

Desde que é de muito o mais simples das três classes, vamos começar olhando para a classe de entrada de lista ligada, que se chama LinkedListEntry:

class LinkedListEntry {
  protected Object          val = null;
  protected LinkedListEntry next = null;
  protected LinkedListEntry prev = null;

  public LinkedListEntry(Object obj) {
    // Make sure the object is valid
    if (obj == null)
      throw new NullPointerException();

    val = obj;
  }
}

A classe de LinkedListEntry contém três variáveis de membro que acompanham o valor da entrada (o elemento que se guarda) e uma referência para os elementos seguintes e prévios. Esta classe manda definir um construtor único, que simplesmente verifica a validade do objeto que se guarda na entrada e a destina à variável de membro de val da entrada.

Baseado na simplicidade de LinkedListEntry, está adivinhando provavelmente que a maioria da funcionalidade da lista ligada se fornece pela classe de lista ligada principal. Acertou! Esta classe chama-se LinkedList e contém algumas variáveis de membro, que seguem:

protected LinkedListEntry start = null;
protected LinkedListEntry end = null;
protected int             numElements;

O start e as variáveis de membro de end mantêm referências para os elementos de fim e começo na lista, enquanto o membro de numElements acompanha o tamanho da lista. Também há vários métodos definidos na classe de LinkedList que se parecem com métodos na classe de Vector. Um dos métodos mais importantes é addElement, que acrescenta um novo elemento ao fim da lista. O texto fonte de addElement mostra-se na Listagem 23.1.

A listagem 23.1. A classe de LinkedList método de addElement.

 1: public void addElement(Object obj) {
 2:   // Make sure the object is valid
 3:   if (obj == null)
 4:     throw new NullPointerException();
 5:
 6:   // Create the new entry
 7:   LinkedListEntry newElement = new LinkedListEntry(obj);
 8:   numElements++;
 9:
10:   // See if the new element is the start of the list
11:   if (start == null) {
12:     start = newElement;
13:     end = newElement;
14:   }
15:   else {
16:     end.next = newElement;
17:     newElement.prev = end;
18:     end = newElement;
19:   }
20: }

Tão como o método de addElement é importante para acrescentar um novo elemento ao fim da lista, o método de insertElementAt é útil para inserir um novo elemento em qualquer ponto na lista. A listagem 23.2 contém o texto fonte de insertElementAt.

A listagem 23.2. A classe de LinkedList método de insertElementAt.

 1: public void insertElementAt(Object obj, Object pos) {
 2:   // Make sure the objects are valid
 3:   if (obj == null || pos == null)
 4:     throw new NullPointerException();
 5:
 6:   // Make sure the position object is in the list
 7:   LinkedListEntry posEntry = find(pos);
 8:   if (posEntry == null)
 9:     throw new NullPointerException();
10:
11:   // Create the new entry
12:   LinkedListEntry newElement = new LinkedListEntry(obj);
13:   numElements++;
14:
15:   // Link in the new entry
16:   newElement.next = posEntry;
17:   newElement.prev = posEntry.prev;
18:   if (posEntry == start)
19:     start = newElement;
20:   else
21:     posEntry.prev.next = newElement;
22:   posEntry.prev = newElement;
23: }

Neste ponto tem dois métodos que lhe permitem acrescentar e inserir elementos à lista ligada. Contudo, ainda não há meio de retirar elementos da lista. Entre no método de removeElement! A listagem 23.3 contém o texto fonte de removeElement, que lhe permite retirar um elemento especificando o próprio objeto.

A listagem 23.3. A classe de LinkedList método de removeElement.

 1: public boolean removeElement(Object obj) {
 2:   // Make sure the object is valid
 3:   if (obj == null)
 4:     throw new NullPointerException();
 5:
 6:   // Make sure the object is in the list
 7:   LinkedListEntry delEntry = find(obj);
 8:   if (delEntry == null)
 9:     return false;
10:
11:   // Unlink the entry
12:   numElements--;
13:   if (delEntry == start)
14:     start = delEntry.next;
15:   else
16:     delEntry.prev.next = delEntry.next;
17:   if (delEntry == end)
18:     end = delEntry.prev;
19:   else
20:     delEntry.next.prev = delEntry.prev;
21:   return true;
22: }

O método de find é um método privado usado interiormente pela classe de LinkedList para achar entradas na lista baseadas no objeto que guardam. O seguinte é o texto fonte do método de find:

private LinkedListEntry find(Object obj) {
  // Make sure the list isn't empty and the object is valid
  if (isEmpty() || obj == null)
    return null;

  // Search the list for the object
  LinkedListEntry tmp = start;
  while (tmp != null) {
    if (tmp.val == obj)
      return tmp;
    tmp = tmp.next;
  }
  return null;
}

O método de find primeiro verifica para assegurar-se que a lista não é vazia e que o objeto em questão é válido. Então atravessa a lista usando um laço de while, verificando que a variável de membro de val de cada entrada contra o objeto passou em. Se houver um jogo, a entrada considerando que o objeto se devolve; de outra maneira, null devolve-se.

O método de find não é público porque não quer que usuários exteriores da classe de LinkedList saibam algo sobre a classe de LinkedListEntry. Em outras palavras, a classe de LinkedListEntry é uma classe de ajudante puramente interna, portanto o objeto de LinkedListEntry devolvido de find não faria nenhum sentido a um usuário de LinkedList. Embora find seja privado, há um método público que pode usar-se para ver se um objeto está na lista. Este método chama-se contains; o seu texto fonte segue:

public boolean contains(Object obj) {
  return (find(obj) != null);
}

Como pode ver, todo o método de contains faz é chamar find e comparar o valor de retorno com null. Desde que find só devolve um valor de non-null se um objeto se encontrar, este pequeno truque trabalha perfeitamente!

Pode ter notado antes que o método de find fez uma chamada ao método de isEmpty para ver se a lista foi vazia. O código deste método segue:

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

Desde que a referência de start em LinkedList só contém um valor de null se a lista for vazia, o método de isEmpty simplesmente verifica para ver se se estabelece de fato em null. Isto é um modo muito simples e eficaz de ver se a lista é vazia.

Isto bastante bem sumaria a classe de LinkedList, exceto como apoia a interface de Enumeration. Na decisão como apoiar a interface de Enumeration, a sua aposta melhor deve cuidar da classe de Vector. A classe de Vector apoia a interface de Enumeration por um método chamado elements. O método de elements devolve um objeto do tipo Enumeration que pode usar-se para enumerar os elementos em um vetor. Vamos usar esta mesma aproximação de acrescentar capacidades de lista à lista ligada. O seguinte é o texto fonte do método de elements na classe de LinkedList:

public Enumeration elements() {
  return new LinkedListEnumerator(this);
}

O método de elements é provavelmente muito mais simples do que esperou. É porque o trabalho de fato apoiar a interface de Enumeration deixa-se à classe de LinkedListEnumerator. A listagem 23.4 contém o texto fonte da classe de LinkedListEnumerator.

A listagem 23.4. A classe de LinkedListEnumerator.

 1: class LinkedListEnumerator implements Enumeration {
 2:   protected LinkedListEntry pos;
 3:
 4:   public LinkedListEnumerator(LinkedList list) {
 5:     pos = list.start;
 6:   }
 7:
 8:   public boolean hasMoreElements() {
 9:     return (pos != null);
10:   }
11:
12:   public Object nextElement() {
13:     // Make sure the current object is valid
14:     if (pos == null)
15:       throw new NoSuchElementException();
16:
17:     // Increment the list and return the object
18:     LinkedListEntry tmp = pos;
19:     pos = pos.next;
20:     return tmp.val;
21:   }
22: }

Outro do que o provérbio assim na definição de classe, implementando a interface de Enumeration implica o apoio de dois métodos: hasMoreElements e nextElement. O método de hasMoreElements simplesmente verifica para ver se o membro de pos é non-null, em que caso há mais elementos para enumerar. O método de nextElement assegura-se que a entrada atual é válida e logo devolve o objeto guardado nesta entrada. E isto é realmente tudo que há à classe de LinkedListEnumerator!

Agora tem uma classe de lista ligada completa que está pronta para pôr-se para usar em um programa Java prático. O deixarei até você para compreender uma aplicação arrumada dele. Incidentemente, todo o texto fonte das classes de lista ligadas localiza-se no CD-ROM acompanhante.

Sumário

Na lição de hoje aprendeu todos sobre estruturas de dados e a sua relevância para a programação de Java. Começou a lição com uma breve revisão de estruturas de dados em geral e porque é importante ter uma compreensão sólida de como usá-los. Então mudou à aprendizagem sobre as estruturas de dados padrão fornecidas no pacote de serviço de Java. Estas estruturas de dados padrão fornecem uma variedade de opções que cobrem muitos cenários de programação práticos. Contudo, para aqueles casos onde precisa de algo um pouco diferente para manter dados, também aprendeu sobre um tipo da estrutura de dados que não se fornece pelo pacote de serviço de Java: listas ligadas. Até implementou uma classe de lista ligada que pode reutilizar nos seus próprios programas Java. Este conhecimento, combinado com uma compreensão das estruturas de dados de Java padrão, deve servir de uma fundação sólida do seu manejo de dados em cenários de programação práticos.

Se pensou que o tópico de estruturas de dados foi um pouco seco, não se incomode, porque a lição de amanhã se torna muito mais excitante. Amanhã aprenderá sobre técnicas de animação promovidas e o manejo de meios de comunicação distribuídos. Até usará a sua compreensão recente de vetores de implementar algumas classes de animação realmente arrumadas!

Perguntas e Respostas