Kann kein Array von LinkedLists in Java erstellen ...?

Ich arbeite an einer Sparse - Matrix - Klasse , die benötigt ein Array von verwenden , um LinkedListdie Werte einer Matrix zu speichern. Jedes Element des Arrays (dh jedes LinkedList) repräsentiert eine Zeile der Matrix. Und jedes Element im LinkedListArray repräsentiert eine Spalte und den gespeicherten Wert.

In meiner Klasse habe ich eine Deklaration des Arrays als:

private LinkedList<IntegerNode>[] myMatrix;

Und in meinem Konstruktor für SparseMatrixversuche ich zu definieren:

myMatrix = new LinkedList<IntegerNode>[numRows];

Der Fehler, den ich am Ende bekomme, ist

Es kann kein generisches Array von erstellt werden LinkedList<IntegerNode>.

Ich habe also zwei Probleme damit:

1. Was mache ich falsch und
2. Warum ist der Typ in der Deklaration für das Array akzeptabel, wenn er nicht erstellt werden kann?

IntegerNodeist eine Klasse, die ich erstellt habe. Und alle meine Klassendateien sind zusammen gepackt.

Sie können keine generische Array-Erstellung verwenden. Es ist ein Fehler / Merkmal von Java-Generika.

Die Wege ohne Warnungen sind:

1. Verwenden der Listenliste anstelle des Listenarrays:

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

2. Deklarieren der speziellen Klasse für Array of Lists:

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

Aus irgendeinem Grund müssen Sie den Typ umwandeln und die Deklaration wie folgt abgeben:

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

Abgesehen von den Syntaxproblemen erscheint es mir seltsam, ein Array und eine verknüpfte Liste zur Darstellung einer Matrix zu verwenden. Um auf beliebige Zellen der Matrix zugreifen zu können, möchten Sie wahrscheinlich, dass ein tatsächliches Array oder zumindest ein ArrayListdie Zeilen enthält, da LinkedListdie gesamte Liste vom ersten Element zu einem bestimmten Element, einer O(n)Operation, durchlaufen werden muss , im Gegensatz zu viel schneller O(1)mit ArrayListoder einem tatsächlichen Array.

Da Sie erwähnt haben, dass diese Matrix spärlich ist, können Sie die Daten möglicherweise besser als Karte mit Karten speichern, wobei ein Schlüssel in der ersten Karte einen Zeilenindex darstellt und sein Wert eine Zeilenzuordnung ist, deren Schlüssel ein Spaltenindex sind , wobei der Wert Ihre IntegerNode-Klasse ist. So:

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

Wenn Sie in der Lage sein müssen, die Matrix zeilenweise zu durchlaufen, können Sie den Zeilenzuordnungstyp a festlegen TreeMap, und dasselbe gilt für das Durchlaufen der Spalten in Indexreihenfolge. Wenn Sie diese Fälle jedoch nicht benötigen, HashMapist dies schneller als TreeMap. Hilfsmethoden zum Abrufen und Festlegen einer beliebigen Zelle, die nicht festgelegte Nullwerte verarbeiten, wären natürlich nützlich.

class IntegerNodeList extends LinkedList<IntegerNode> {}

IntegerNodeList[] myMatrix = new IntegerNodeList[numRows]; 

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

Das Casting auf diese Weise funktioniert, hinterlässt aber dennoch eine böse Warnung:

"Typensicherheit: Der Ausdruck vom Typ Liste [] muss deaktiviert konvertiert werden."

Deklarieren einer speziellen Klasse für Array of Lists:

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

ist eine clevere Idee, um die Warnung zu vermeiden. Vielleicht ist es ein bisschen schöner, eine Schnittstelle dafür zu verwenden:

public interface IntegerNodeList extends List<IntegerNode> {}

dann

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

Kompiliert ohne Warnungen.

sieht nicht schlecht aus, oder?

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

Keine Warnungen. NetBeans 6.9.1, jdk1.6.0_24

In Java 1.5 gibt es keine generische Array-Erstellung (oder 1.6, soweit ich das beurteilen kann). Siehe https://community.oracle.com/message/4829402 .

Wenn ich Folgendes tue, wird die betreffende Fehlermeldung angezeigt

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

Aber wenn ich nur den Listentyp in der Deklaration entferne, scheint er die gewünschte Funktionalität zu haben.

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

Unterscheiden sich diese beiden Erklärungen drastisch, was mir nicht bewusst ist?

BEARBEITEN

Ah, ich glaube, ich bin jetzt auf dieses Problem gestoßen.

Das Iterieren über die Matrix und das Initialisieren der Listen in einer for-Schleife scheint zu funktionieren. Obwohl es nicht so ideal ist wie einige der anderen angebotenen Lösungen.

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

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

Sie benötigen eine Reihe von Listen. Eine Alternative besteht darin, Folgendes zu versuchen:

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

Dann node_array[i]speichert den Kopf (ersten) Knoten ein ArrayList<IntegerNode>oder LinkedList<IntegerNode>(was auch immer Ihre Favoritenliste Implementierung).

Bei diesem Entwurf verlieren Sie die Direktzugriffsmethode list.get(index), können dann jedoch die Liste beginnend mit dem Kopf- / Faustknotenspeicher im Typ-Safe-Array durchlaufen.

Dies kann je nach Anwendungsfall eine akzeptable Designwahl sein. Zum Beispiel verwende ich dieses Design, um eine Adjazenzliste eines Diagramms darzustellen. In den meisten Anwendungsfällen muss die Adjazenzliste ohnehin für einen bestimmten Scheitelpunkt durchlaufen werden, anstatt zufällig auf einen Scheitelpunkt in der Liste zuzugreifen.