Non è possibile creare un array di LinkedList in Java ...?

Question

Sto lavorando su una classe di matrice sparsa che richiede per utilizzare un array di LinkedList per memorizzare i valori di una matrice. Ogni elemento dell'array (ad esempio, ogni LinkedList) rappresenta una riga della matrice. Inoltre, ogni elemento nell'array LinkedList rappresenta una colonna e il valore memorizzato.

Nella mia classe, ho una dichiarazione della matrice come:

private LinkedList<IntegerNode>[] myMatrix; 

E, a mio costruttore per la SparseMatrix, cerco di definire:

myMatrix = new LinkedList<IntegerNode>[numRows]; 

L'errore finisco ottenere è

Impossibile creare un array generico di LinkedList<IntegerNode>.

Così, ho due problemi con questo:

1. Che cosa sto facendo di sbagliato, e
2. Perché il tipo accettabile nella dichiarazione per la matrice, se non può essere creato?

IntegerNode è una classe che ho creato. E tutti i miei file di classe sono raggruppati insieme.

Answer 1

Non è possibile utilizzare la creazione di un array generico. È un difetto/caratteristica dei generici java.

Le vie senza avvisi sono:

1. Utilizzando lista di liste, invece di array di liste:

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

2. dichiarare la classe speciale per Array di Liste:

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

Answer 2

Per qualche ragione si deve lanciare il tipo e fare la dichiarazione come questa:

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

Answer 3

Non c'è creazione generico array in Java 1.5 (o 1.6 per quanto posso dire). Vedi https://community.oracle.com/message/4829402.

Answer 4

A parte f dai problemi di sintassi, mi sembra strano usare una matrice e una lista collegata per rappresentare una matrice. Per poter accedere a celle arbitrarie della matrice, probabilmente vorrai un array effettivo o almeno un ArrayList per contenere le righe, poiché LinkedList deve attraversare l'intera lista dal primo elemento a qualsiasi elemento particolare, un'operazione O(n), al contrario al molto più veloce O(1) con ArrayList o una matrice reale.

Dato che questa matrice è sparsa, tuttavia, forse un modo migliore per archiviare i dati è come una mappa di mappe, dove una chiave nella prima mappa rappresenta un indice di riga, e il suo valore è una mappa di riga le cui chiavi sono un indice di colonna, con il valore della classe IntegerNode.Così:

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 è necessario essere in grado di attraversare la riga di matrice per riga, è possibile rendere la mappa fila digitare un TreeMap, e lo stesso per attraversare le colonne in ordine di indice, ma se non è necessario questi casi, HashMap è più veloce di TreeMap. I metodi di supporto per ottenere e impostare una cella arbitraria, gestendo valori nulli non impostati, sarebbero utili, ovviamente.

Answer 5

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

colata questo modo i lavori, ma ancora ti lascia con un brutto avvertimento:

"di sicurezza di tipo: L'espressione di tipo List [] esigenze di conversione incontrollato .."

Dichiarazione di una classe speciale per la matrice di elenchi:

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

è un'idea intelligente per evitare l'avviso. forse un po 'più bello è quello di utilizzare un'interfaccia per esso:

public interface IntegerNodeList extends List<IntegerNode> {} 

poi

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

compila senza avvisi.

non sembra troppo male, vero?

Answer 6

class IntegerNodeList extends LinkedList<IntegerNode> {} 

IntegerNodeList[] myMatrix = new IntegerNodeList[numRows]; 

Answer 7

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

Nessun eventuali avvisi. NetBeans 6.9.1, jdk1.6.0_24

Answer 8

Se faccio il seguente ottengo il messaggio di errore in questione

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

Ma se ho appena rimuovere il tipo di lista nella dichiarazione sembra avere la funzionalità desiderata .

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

Queste due dichiarazioni sono drasticamente diverse in un modo di cui non sono a conoscenza?

EDIT

Ah, penso che ho incontrato questo problema ora.

L'iterazione sulla matrice e l'inizializzazione degli elenchi in un ciclo continuo sembrano funzionare. Anche se non è l'ideale come alcune delle altre soluzioni offerte.

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

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

Answer 9

È necessario un allineamento di List, un'alternativa è quella di provare:

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

Poi node_array[i] memorizza la testa (prima) nodo di una (qualunque sia il vostro implementazione lista dei favoriti) ArrayList<IntegerNode> o LinkedList<IntegerNode>.

In questo modello, si perde il metodo di accesso casuale list.get(index), ma si potrebbe comunque attraversare l'elenco a partire dall'archivio del nodo testa/pugno nell'array di tipo safe.

Questa potrebbe essere una scelta di progettazione accettabile a seconda del caso d'uso. Per esempio, io uso questo disegno per rappresentare un elenco di grafici di adiacenza, nella maggior parte dei casi d'uso, richiede comunque l'attraversamento dell'elenco di adiacenze per un dato vertice invece dell'accesso casuale ad alcuni vertici nell'elenco.