不能用 Java 创建 LinkedList 数组... ？

我正在处理一个稀疏矩阵类，需求使用一个 LinkedList数组来存储矩阵的值。数组的每个元素(即每个 LinkedList)表示矩阵的一行。而且，LinkedList数组中的每个元素都表示一个列和存储的值。

在我的类中，我将数组声明为:

private LinkedList<IntegerNode>[] myMatrix;

在 SparseMatrix的构造函数中，我尝试定义:

myMatrix = new LinkedList<IntegerNode>[numRows];

我最终得到的错误是

无法创建 LinkedList<IntegerNode>的泛型数组。

所以，我有两个问题:

  1. 我做错了什么
  2. 如果不能创建数组，为什么在声明中可以接受该类型？

IntegerNode是我创建的一个类，所有的类文件都打包在一起。

75604 次浏览
小开

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

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

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.

小开
最佳答案

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

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.

小开

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?

小开 
class IntegerNodeList extends LinkedList<IntegerNode> {}


IntegerNodeList[] myMatrix = new IntegerNodeList[numRows];
小开 
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

小开

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<>();
}
小开

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.


提交答案