Cannot create an array of LinkedLists in Java...?

Question

I'm working on a sparse matrix class that needs to use an array of LinkedLists 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 LinkedLists 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?

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

Answer 1

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

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

Answer 2

There is no generic array creation in Java 1.5 (or 1.6 as far as I can tell). See http://forums.sun.com/thread.jspa?threadID=530823.

Answer 3

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;
   }
   

Answer 4

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.

Answer 5

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?

Answer 6

myMatrix = (LinkedList[]) new LinkedList[numRows];

This solution gives me a null pointer Exception

LinkedList<String>[] array = (LinkedList<String>[]) new LinkedList[6];
     array[0].add("Ahmed");