Não é possível criar uma matriz de LinkedLists em Java…?

Eu estou trabalhando em uma class de matriz esparsa que precisa usar uma matriz de LinkedList para armazenar os valores de uma matriz. Cada elemento da matriz (ou seja, cada LinkedList ) representa uma linha da matriz. E cada elemento na matriz LinkedList representa uma coluna e o valor armazenado.

Na minha aula, tenho uma declaração do array como:

 private LinkedList[] myMatrix; 

E, no meu construtor para o SparseMatrix , eu tento definir:

 myMatrix = new LinkedList[numRows]; 

O erro que eu acabo recebendo é

Não é possível criar uma matriz genérica de LinkedList .

Então, eu tenho dois problemas com isso:

  1. O que estou fazendo errado e
  2. Por que o tipo é aceitável na declaração da matriz se não puder ser criado?

IntegerNode é uma class que eu criei. E todos os meus arquivos de class são empacotados juntos.

Você não pode usar a criação de matriz genérica. É uma falha / característica dos genéricos java.

As formas sem avisos são:

  1. Usando lista de listas em vez de matriz de listas:

     List< List> nodeLists = new LinkedList< List< IntegerNode >>(); 
  2. Declarando a class especial para Array of Lists:

     class IntegerNodeList { private final List< IntegerNode > nodes; } 

Por alguma razão você tem que lançar o tipo e fazer a declaração assim:

 myMatrix = (LinkedList[]) new LinkedList< ?>[numRows]; 

Além dos problemas de syntax, parece-me estranho usar uma matriz e uma linked list para representar uma matriz. Para poder acessar células arbitrárias da matriz, você provavelmente desejaria uma matriz real ou pelo menos uma ArrayList para manter as linhas, pois LinkedList deve percorrer toda a lista do primeiro elemento para qualquer elemento em particular, uma operação O(n) , ao contrário do muito mais rápido O(1) com ArrayList ou um array real.

Como você mencionou que essa matriz é escassa, talvez a melhor maneira de armazenar os dados seja como um mapa de mapas, onde uma chave no primeiro mapa representa um índice de linha e seu valor é um mapa de linha cujas chaves são um índice de coluna. , com o valor sendo sua class IntegerNode. Portanto:

 private Map> myMatrix = new HashMap>(); // access a matrix cell: int rowIdx = 100; int colIdx = 30; Map row = myMatrix.get(rowIdx); // if null, create and add to matrix IntegerNode node = row.get(colIdx); // possibly null 

Se você precisar atravessar a matriz linha por linha, você pode fazer o mapa de linha digitar um TreeMap , e o mesmo para percorrer as colunas na ordem de índice, mas se você não precisar desses casos, o HashMap será mais rápido que o TreeMap . Os methods auxiliares para obter e definir uma célula arbitrária, manipulando valores nulos não definidos, seriam úteis, é claro.

 class IntegerNodeList extends LinkedList {} IntegerNodeList[] myMatrix = new IntegerNodeList[numRows]; 

myMatrix = (LinkedList[]) new LinkedList[numRows];

lançando desta forma funciona, mas ainda deixa você com um aviso desagradável:

“Tipo de segurança: A expressão do tipo Lista [] precisa de conversão desmarcada.”

Declarando uma class especial para Array of Lists:

class IntegerNodeList { private final List< IntegerNode > nodes; }

é uma ideia inteligente para evitar o aviso. talvez um pouco melhor é usar uma interface para isso:

 public interface IntegerNodeList extends List {} 

então

 List[] myMatrix = new IntegerNodeList[numRows]; 

compila sem avisos.

não parece tão ruim, não é?

 List[] lst = new List[2]; lst[0] = new LinkedList(); lst[1] = new LinkedList(); 

Nenhum aviso. NetBeans 6.9.1, jdk1.6.0_24

Não há criação de matriz genérica no Java 1.5 (ou 1.6, tanto quanto eu posso dizer). Veja https://community.oracle.com/message/4829402 .

Se eu fizer o seguinte, recebo a mensagem de erro em questão

 LinkedList[] matrix = new LinkedList[5]; 

Mas se eu apenas remover o tipo de lista na declaração, parece ter a funcionalidade desejada.

 LinkedList[] matrix = new LinkedList[5]; 

Essas duas declarações são drasticamente diferentes de uma forma que eu não conheço?

EDITAR

Ah, acho que me deparei com essa questão agora.

Iterar sobre a matriz e inicializar as listas em um loop for parece funcionar. Embora não seja tão ideal quanto algumas das outras soluções oferecidas.

 for(int i=0; i < matrix.length; i++){ matrix[i] = new LinkedList<>(); } 

Você precisa de uma matriz de lista, uma alternativa é tentar:

 private IntegerNode[] node_array = new IntegerNode[sizeOfYourChoice]; 

Em seguida, node_array[i] armazena o nó principal (primeiro) de um ArrayList ou LinkedList (qualquer que seja sua implementação de lista de favoritos).

Sob esse design, você perde o método de access random list.get(index) , mas ainda pode percorrer a lista começando com o armazenamento do nó head / fist no array safe type.

Essa pode ser uma opção de design aceitável, dependendo do seu caso de uso. Por exemplo, eu uso este design para representar uma lista de adjacências do grafo, na maioria dos casos de uso, requer atravessar a lista de adjacências de qualquer maneira para um determinado vértice ao invés de acessar aleatoriamente algum vértice na lista.