Impossible de créer un tableau de LinkedLists en Java…?

Je travaille sur une classe de matrice clairsemée qui doit utiliser un tableau de LinkedListpour stocker les valeurs d'une matrice. Chaque élément du tableau (c'est-à-dire chacun LinkedList) représente une ligne de la matrice. Et, chaque élément du LinkedListtableau représente une colonne et la valeur stockée.

Dans ma classe, j'ai une déclaration du tableau comme:

private LinkedList<IntegerNode>[] myMatrix;

Et, dans mon constructeur pour le SparseMatrix, j'essaye de définir:

myMatrix = new LinkedList<IntegerNode>[numRows];

L'erreur que je finis par obtenir est

Impossible de créer un tableau générique de LinkedList<IntegerNode>.

Donc, j'ai deux problèmes avec ceci:

1. Qu'est-ce que je fais de mal, et
2. Pourquoi le type est-il acceptable dans la déclaration du tableau s'il ne peut pas être créé?

IntegerNodeest une classe que j'ai créée. Et, tous mes fichiers de classe sont emballés ensemble.

Vous ne pouvez pas utiliser la création de tableau générique. C'est une faille / fonctionnalité des génériques Java.

Les moyens sans avertissements sont:

1. Utilisation de la liste de listes au lieu du tableau de listes:

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

2. Déclarer la classe spéciale pour Array of Lists:

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

Pour une raison quelconque, vous devez convertir le type et faire la déclaration comme ceci:

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

Mis à part les problèmes de syntaxe, il me semble étrange d'utiliser un tableau et une liste chaînée pour représenter une matrice. Pour pouvoir accéder à des cellules arbitraires de la matrice, vous voudrez probablement qu'un tableau réel ou au moins un ArrayListcontienne les lignes, car il LinkedListdoit parcourir toute la liste du premier élément à un élément particulier, une O(n)opération, par opposition à beaucoup plus rapide O(1)avec ArrayListou un tableau réel.

Puisque vous avez mentionné que cette matrice est clairsemée, cependant, la meilleure façon de stocker les données est peut-être sous la forme d'une carte de cartes, où une clé dans la première carte représente un index de ligne et sa valeur est une carte de ligne dont les clés sont un index de colonne , la valeur étant votre classe IntegerNode. Donc:

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

Si vous avez besoin de pouvoir parcourir la matrice ligne par ligne, vous pouvez faire en sorte que le mappage de ligne soit de type a TreeMap, et de même pour parcourir les colonnes dans l'ordre d'index, mais si vous n'avez pas besoin de ces cas, HashMapc'est plus rapide que TreeMap. Des méthodes d'aide pour obtenir et définir une cellule arbitraire, gérant des valeurs nulles non définies, seraient bien sûr utiles.

class IntegerNodeList extends LinkedList<IntegerNode> {}

IntegerNodeList[] myMatrix = new IntegerNodeList[numRows]; 

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

le casting de cette façon fonctionne mais vous laisse toujours un mauvais avertissement:

"Sécurité de type: l'expression de type List [] nécessite une conversion non cochée."

Déclarer une classe spéciale pour Array of Lists:

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

est une idée intelligente pour éviter l'avertissement. peut-être un peu plus agréable est d'utiliser une interface pour cela:

public interface IntegerNodeList extends List<IntegerNode> {}

puis

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

compile sans avertissement.

n'a pas l'air trop mal, n'est-ce pas?

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

Aucun avertissement. NetBeans 6.9.1, jdk1.6.0_24

Il n'y a pas de création de tableau générique dans Java 1.5 (ou 1.6 pour autant que je sache). Voir https://community.oracle.com/message/4829402 .

Si je fais ce qui suit, j'obtiens le message d'erreur en question

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

Mais si je supprime simplement le type de liste dans la déclaration, il semble avoir la fonctionnalité souhaitée.

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

Ces deux déclarations sont-elles radicalement différentes d'une manière dont je ne suis pas au courant?

ÉDITER

Ah, je pense que j'ai rencontré ce problème maintenant.

Itérer sur la matrice et initialiser les listes dans une boucle for semble fonctionner. Bien que ce ne soit pas aussi idéal que certaines des autres solutions proposées.

for(int i=0; i < matrix.length; i++){

    matrix[i] = new LinkedList<>();
}

Vous avez besoin d'un tableau de List, une alternative est d'essayer:

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

node_array[i]Stocke ensuite le nœud principal (premier) d'un ArrayList<IntegerNode>ou LinkedList<IntegerNode>(quelle que soit votre implémentation de liste préférée).

Dans cette conception, vous perdez la méthode d'accès aléatoire list.get(index), mais vous pouvez toujours parcourir la liste en commençant par le magasin de nœuds head / fist dans le tableau de type sécurisé.

Cela peut être un choix de conception acceptable en fonction de votre cas d'utilisation. Par exemple, j'utilise cette conception pour représenter une liste de graphes de contiguïté, dans la plupart des cas d'utilisation, il faut de toute façon traverser la liste de contiguïté pour un sommet donné au lieu d'accéder au hasard à un sommet de la liste.