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

Estou trabalhando em uma classe de matriz esparsa que precisa usar uma matriz de LinkedListpara armazenar os valores de uma matriz. Cada elemento da matriz (ou seja, cada um LinkedList) representa uma linha da matriz. E, cada elemento da LinkedListmatriz representa uma coluna e o valor armazenado.

Em minha aula, tenho uma declaração da matriz como:

private LinkedList<IntegerNode>[] myMatrix;

E, em meu construtor para o SparseMatrix, tento definir:

myMatrix = new LinkedList<IntegerNode>[numRows];

O erro que acabo recebendo é

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

Então, tenho dois problemas com isso:

1. O que estou fazendo de errado e
2. Por que o tipo é aceitável na declaração do array se ele não pode ser criado?

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

Você não pode usar a criação de array genérico. É uma falha / característica dos genéricos Java.

As maneiras sem avisos são:

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

   List< List<IntegerNode>> nodeLists = new LinkedList< List< IntegerNode >>();

2. Declarando a classe especial para Array of Lists:

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

Por algum motivo, você deve lançar o tipo e fazer a declaração assim:

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

Além dos problemas de sintaxe, parece-me estranho usar um array e uma lista vinculada para representar uma matriz. Para ser capaz de acessar células arbitrárias da matriz, você provavelmente desejaria um array real ou pelo menos um ArrayListpara conter as linhas, já que LinkedListdeve percorrer toda a lista do primeiro elemento a qualquer elemento em particular, uma O(n)operação, ao invés de muito mais rápido O(1)com ArrayListou uma matriz real.

Como você mencionou que esta matriz é esparsa, 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 classe IntegerNode. Portanto:

private Map<Integer, Map<Integer, IntegerNode>> myMatrix = new HashMap<Integer, Map<Integer, IntegerNode>>();

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

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

class IntegerNodeList extends LinkedList<IntegerNode> {}

IntegerNodeList[] myMatrix = new IntegerNodeList[numRows]; 

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

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

"Segurança de tipo: A expressão do tipo Lista [] precisa de conversão desmarcada .."

Declarando uma classe especial para Array of Lists:

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

é uma ideia inteligente para evitar o aviso. talvez um pouco mais agradável seja usar uma interface para isso:

public interface IntegerNodeList extends List<IntegerNode> {}

então

List<IntegerNode>[] myMatrix = new IntegerNodeList[numRows];

compila sem avisos.

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

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

Sem quaisquer avisos. NetBeans 6.9.1, jdk1.6.0_24

Não há criação de array genérico em Java 1.5 (ou 1.6 até onde posso dizer). Consulte https://community.oracle.com/message/4829402 .

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

LinkedList<Node>[] matrix = new LinkedList<Node>[5];

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

LinkedList<Node>[] matrix = new LinkedList[5];

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

EDITAR

Ah, acho que já me deparei com esse problema.

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 List, uma alternativa é tentar:

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

Em seguida, node_array[i]armazena o nó principal (primeiro) de um ArrayList<IntegerNode>ouLinkedList<IntegerNode> (qualquer que seja sua implementação de lista favorita).

Sob este design, você perde o método de acesso aleatório list.get(index) , mas então você ainda pode percorrer a lista começando com o armazenamento de nó head / fist no array de tipo seguro.

Esta pode ser uma escolha de design aceitável, dependendo do seu caso de uso. Por exemplo, eu uso este projeto para representar uma lista de adjacências de grafo, na maioria dos casos de uso, requer atravessar a lista de adjacências de qualquer maneira para um determinado vértice em vez de acessar aleatoriamente algum vértice na lista.