103

I'm working on a sparse matrix class that needs to use an array of LinkedList to store the values of a matrix. Each element of the array (i.e. each LinkedList) represents a row of the matrix. And, each element in the LinkedList array represents a column and the stored value.

In my class, I have a declaration of the array as:

private LinkedList<IntegerNode>[] myMatrix;

And, in my constructor for the SparseMatrix, I try to define:

myMatrix = new LinkedList<IntegerNode>[numRows];

The error I end up getting is

Cannot create a generic array of LinkedList<IntegerNode>.

So, I have two issues with this:

  1. What am I doing wrong, and
  2. Why is the type acceptable in the declaration for the array if it can't be created?

IntegerNode is a class that I have created. And, all of my class files are packaged together.

9 Answers 9

145

For some reason you have to cast the type and make the declaration like this:

myMatrix = (LinkedList<IntegerNode>[]) new LinkedList<?>[numRows];
8
  • I researched a similar problem and read that the above cast is a very common 'hack' that is used all over the collections framework.
    – luke
    Oct 20, 2008 at 12:25
  • 17
    IMO, this should be the selected answer. I haven't experimented, but I have the gut feeling that Sergey's #2 method creates quite a bit of overhead; and I'm POSITIVE that #1 does. A list is not as efficient as an array in several ways which I won't detail here, but I HAVE done experiments and seen big slowdowns when using lists compared to arrays. It's faster to just manage your own arrays and reallocate them, than to add stuff to a List.
    – Ricket
    Jul 30, 2009 at 16:02
  • @Ricket I agree, taken from ibm.com/developerworks/java/library/j-jtp01255/index.html
    – Peteter
    Aug 1, 2011 at 15:39
  • 4
    I still get a "Type safety: unchecked cast" warning out of it. Bob's solution looks the cleanest to me. May 23, 2012 at 17:28
  • 3
    In JDK 7 the above gives a rawtypes warning. That can be fixed using the unbounded <?> type, but you still get an unchecked warning (which can be suppressed). e.g. <br> <code>myMatrix = (LinkedList<IntegerNode>[]) new LinkedList<?>[numRows];</code>
    – Neon
    Jan 4, 2013 at 14:28
66

You can't use generic array creation. It's a flaw/ feature of java generics.

The ways without warnings are:

  1. Using List of Lists instead of Array of Lists:

    List< List<IntegerNode>> nodeLists = new LinkedList< List< IntegerNode >>();
    
  2. Declaring the special class for Array of Lists:

    class IntegerNodeList {
        private final List< IntegerNode > nodes;
    }
    
2
  • 19
    A better alternative to the latter solution would be to: class IntegerNodeList extends List<IntegerNode> {}
    – kamasheto
    Apr 18, 2010 at 21:45
  • This implementation is outrageously slow. Getting the [1000][2000] element (nodeLists.get(1000).get(2000)) will make LinkedList iterate 3000 times! Avoid LinkedList if anyone may be indexing into it. ArrayList will index faster, but Fredrik's solution is better overall. Mar 9, 2017 at 20:08
5

Aside from the syntax issues, it seems strange to me to use an array and a linked list to represent a matrix. To be able to access arbitrary cells of the matrix, you would probably want an actual array or at least an ArrayList to hold the rows, as LinkedList must traverse the whole list from the first element to any particular element, an O(n) operation, as opposed to the much quicker O(1) with ArrayList or an actual array.

Since you mentioned this matrix is sparse, though, perhaps a better way to store the data is as a map of maps, where a key in the first map represents a row index, and its value is a row map whose keys are a column index, with the value being your IntegerNode class. Thus:

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

If you need to be able to traverse the matrix row by row, you can make the row map type a TreeMap, and same for traversing the columns in index order, but if you don't need those cases, HashMap is quicker than TreeMap. Helper methods to get and set an arbitrary cell, handling unset null values, would be useful, of course.

4
class IntegerNodeList extends LinkedList<IntegerNode> {}

IntegerNodeList[] myMatrix = new IntegerNodeList[numRows]; 
1
  • You missed the generics for LinkedList. Dec 19, 2012 at 16:29
3

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

casting this way works but still leaves you with a nasty warning:

"Type safety: The expression of type List[] needs unchecked conversion.."

Declaring a special class for Array of Lists:

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

is a clever idea to avoid the warning. maybe a little bit nicer is to use an interface for it:

public interface IntegerNodeList extends List<IntegerNode> {}

then

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

compiles without warnings.

doesn't look too bad, does it?

3
  • IntegerNodeList: what class would you use this with? For instance you could not assign an ArrayList <IntegerNode> to it. You would need to extend ArrayList as well... Apr 1, 2010 at 11:55
  • there is no need to use the interface IntegerNodeList outside the initialization of the array: List<IntegerNode>[] myMatrix = new IntegerNodeList[5]; for (int i = 0; i < myMatrix.length; i++) { myMatrix[i] = new ArrayList<IntegerNode>(); }
    – user306708
    Apr 1, 2010 at 14:18
  • 1
    List<IntegerNode>[] myMatrix = new IntegerNodeList[numRows]; This has a subtle but important problem. You can only put IntegerNodeList in the array. myMatrix[i] = new ArrayList<IntegerNode>(); will throw ArrayStoreException.
    – Radiodef
    Apr 8, 2015 at 18:47
2
List<String>[] lst = new List[2];
lst[0] = new LinkedList<String>();
lst[1] = new LinkedList<String>();

No any warnings. NetBeans 6.9.1, jdk1.6.0_24

1
  • 1
    True no warnings but with Oracle's Java SE 6 Update 32 I get the compiling error "The type List is not generic; it cannot be parameterized with arguments <String>". Removing the <String> argument generates another error "Type mismatch: cannot convert from LinkedList<String> to List". May 23, 2012 at 14:25
2

There is no generic array creation in Java 1.5 (or 1.6 as far as I can tell). See https://community.oracle.com/message/4829402.

0
0

If I do the following I get the error message in question

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

But if I just remove the list type in the declaration it seems to have the desired functionality.

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

Are these two declarations drastically different in a way of which I'm not aware?

EDIT

Ah, I think I've run into this issue now.

Iterating over the matrix and initializing the lists in a for-loop seems to work. Though it's not as ideal as some of the other solutions offered up.

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

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

You need an array of List, one alternative is to try:

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

Then node_array[i] stores the head(first) node of a ArrayList<IntegerNode> or LinkedList<IntegerNode> (whatever your favourite list implementation).

Under this design, you lose the random access method list.get(index), but then you could still traverse the list starting with the head/fist node store in the type safe array.

This might be an acceptable design choice depending on your use case. For instance, I use this design to represent an adjacency list of graph, in most use cases, it requires traversing the adjacency list anyway for a given vertex instead of random access some vertex in the list.

Not the answer you're looking for? Browse other questions tagged or ask your own question.