Nie można utworzyć tablicy LinkedLists w Javie…?

Pracuję nad rzadką klasą macierzy, która musi używać tablicy LinkedListdo przechowywania wartości macierzy. Każdy element tablicy (tj. Każdy LinkedList) reprezentuje wiersz macierzy. Każdy element LinkedListtablicy reprezentuje kolumnę i przechowywaną wartość.

W mojej klasie mam deklarację tablicy jako:

private LinkedList<IntegerNode>[] myMatrix;

W moim konstruktorze dla programu SparseMatrixpróbuję zdefiniować:

myMatrix = new LinkedList<IntegerNode>[numRows];

Błąd, który otrzymuję, to

Nie można utworzyć ogólnej tablicy LinkedList<IntegerNode>.

Mam z tym dwa problemy:

1. Co robię źle i
2. Dlaczego typ jest dopuszczalny w deklaracji tablicy, jeśli nie można jej utworzyć?

IntegerNodeto klasa, którą stworzyłem. Wszystkie pliki moich zajęć są spakowane razem.

Nie możesz użyć ogólnego tworzenia tablicy. Jest to wada / funkcja generycznych języków Java.

Sposoby bez ostrzeżeń to:

1. Korzystanie z listy list zamiast tablicy list:

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

2. Deklarowanie specjalnej klasy dla tablicy list:

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

Z jakiegoś powodu musisz rzutować typ i zrobić taką deklarację:

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

Pomijając problemy ze składnią, wydaje mi się dziwne używanie tablicy i połączonej listy do reprezentowania macierzy. Aby móc uzyskać dostęp do dowolnych komórek macierzy, prawdopodobnie chciałbyś, aby rzeczywista tablica lub przynajmniej ArrayListprzechowywała wiersze, ponieważ LinkedListmusi przejść całą listę od pierwszego elementu do dowolnego konkretnego elementu, O(n)operacji, w przeciwieństwie do dużo szybciej O(1)z ArrayListlub rzeczywistą tablicą.

Ponieważ wspomniałeś, że ta macierz jest rzadka, być może lepszym sposobem przechowywania danych jest mapa map, gdzie klucz w pierwszej mapie reprezentuje indeks wierszy, a jego wartością jest mapa wierszy, której klucze są indeksem kolumny , z wartością będącą Twoją klasą IntegerNode. A zatem:

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

Jeśli potrzebujesz mieć możliwość przechodzenia przez macierz wiersz po wierszu, możesz sprawić, że mapa wierszy będzie miała typ a TreeMapi to samo dla przechodzenia przez kolumny w kolejności indeksu, ale jeśli nie potrzebujesz tych przypadków, HashMapjest to szybsze niż TreeMap. Oczywiście przydatne byłyby metody pomocnicze do pobierania i ustawiania dowolnej komórki, obsługujące nieustawione wartości null.

class IntegerNodeList extends LinkedList<IntegerNode> {}

IntegerNodeList[] myMatrix = new IntegerNodeList[numRows]; 

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

przesyłanie w ten sposób działa, ale nadal pozostawia nieprzyjemne ostrzeżenie:

„Bezpieczeństwo typów: wyrażenie typu List [] wymaga niesprawdzonej konwersji.”

Deklarowanie specjalnej klasy dla tablicy list:

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

to sprytny pomysł, aby uniknąć ostrzeżenia. może trochę przyjemniej jest użyć do tego interfejsu:

public interface IntegerNodeList extends List<IntegerNode> {}

następnie

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

kompiluje się bez ostrzeżeń.

nie wygląda tak źle, prawda?

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

Żadnych ostrzeżeń. NetBeans 6.9.1, jdk1.6.0_24

Nie ma ogólnego tworzenia tablic w Javie 1.5 (lub 1.6, o ile wiem). Zobacz https://community.oracle.com/message/4829402 .

Jeśli wykonam następujące czynności, pojawi się odpowiedni komunikat o błędzie

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

Ale jeśli po prostu usunę typ listy w deklaracji, wydaje się, że ma ona pożądaną funkcjonalność.

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

Czy te dwie deklaracje różnią się drastycznie w sposób, którego nie jestem świadomy?

EDYTOWAĆ

Ach, myślę, że mam teraz ten problem.

Wydaje się, że Iterowanie po macierzy i inicjowanie list w pętli for działa. Chociaż nie jest tak idealny, jak niektóre inne oferowane rozwiązania.

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

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

Potrzebujesz tablicy List, jedną z alternatyw jest wypróbowanie:

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

Następnie node_array[i]przechowuje węzeł główny (pierwszy) ArrayList<IntegerNode>lub LinkedList<IntegerNode>(niezależnie od implementacji listy ulubionych).

W tym projekcie tracisz metodę dostępu swobodnego list.get(index), ale nadal możesz przeglądać listę, zaczynając od magazynu węzłów head / fist w tablicy typu safe.

Może to być akceptowalny wybór projektu w zależności od przypadku użycia. Na przykład, używam tego projektu do reprezentowania listy sąsiedztwa grafu, w większości przypadków użycia wymaga on i tak przejścia przez listę sąsiedztwa dla danego wierzchołka zamiast swobodnego dostępu do jakiegoś wierzchołka na liście.