不能在Java中创建一个链表数组…?

时间:2021-09-07 21:17:24

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.

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

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:

在我的SparseMatrix的构造函数中,我试图定义:

myMatrix = new LinkedList<IntegerNode>[numRows];

The error I end up getting is

我最终得到的错误是

Cannot create a generic array of LinkedList<IntegerNode>.

无法创建LinkedList 的泛型数组。

So, I have two issues with this:

我有两个问题

  1. What am I doing wrong, and
  2. 我做错了什么
  3. Why is the type acceptable in the declaration for the array if it can't be created?
  4. 如果不能创建数组,为什么在声明中可以接受类型?

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

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

9 个解决方案

#1


63  

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

不能使用泛型数组创建。这是java泛型的一个缺陷/特性。

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


134  

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

由于某些原因,您必须对类型进行强制转换,并作出如下声明:

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

#3


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.

除了语法问题之外,使用数组和链表来表示矩阵似乎很奇怪。能够访问任意矩阵的细胞,你可能想要一个真实的数组或至少一个ArrayList的行,LinkedList必须遍历整个列表从第一个元素到任何特定的元素,一个O(n)操作,而不是更快O(1)ArrayList或实际数组。

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:

既然你提到这个矩阵是稀疏的,不过,也许一个更好的方式来存储数据的地图地图,关键在第一个地图表示一行索引,和它的值是连续映射的键列索引值IntegerNode类。因此:

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.

如果您需要能够逐行遍历矩阵行,那么可以将行映射类型设置为TreeMap,按索引顺序遍历列也是如此,但是如果不需要这些情况,HashMap要比TreeMap快。获取和设置任意单元格(处理未设置的空值)的助手方法当然是有用的。

#4


4  

class IntegerNodeList extends LinkedList<IntegerNode> {}

IntegerNodeList[] myMatrix = new IntegerNodeList[numRows]; 

#5


3  

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

myMatrix = (LinkedList ])新的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; }

类IntegerNodeList {private final List< IntegerNode >节点;}

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?

看起来不错,是吗?

#6


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

没有任何警告。NetBeans 6.9.1,jdk1.6.0_24

#7


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.

Java 1.5中没有通用的数组创建(就我所知是1.6)。见https://community.oracle.com/message/4829402。

#8


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循环中初始化列表似乎是可行的。虽然它并不像其他的解决方案那样理想。

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

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

#9


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).

然后node_array[i]存储ArrayList 或LinkedList 的head(first)节点(无论您最喜欢的list实现是什么)。

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.

在这种设计下,您将丢失随机访问方法list.get(index),但是仍然可以遍历从类型安全数组中的head/fist节点存储开始的列表。

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.

根据您的用例,这可能是一个可接受的设计选择。例如,我使用这种设计来表示图的邻接列表,在大多数情况下,它需要遍历给定顶点的邻接列表,而不是随机访问列表中的某个顶点。

#1


63  

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

不能使用泛型数组创建。这是java泛型的一个缺陷/特性。

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


134  

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

由于某些原因,您必须对类型进行强制转换,并作出如下声明:

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

#3


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.

除了语法问题之外,使用数组和链表来表示矩阵似乎很奇怪。能够访问任意矩阵的细胞,你可能想要一个真实的数组或至少一个ArrayList的行,LinkedList必须遍历整个列表从第一个元素到任何特定的元素,一个O(n)操作,而不是更快O(1)ArrayList或实际数组。

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:

既然你提到这个矩阵是稀疏的,不过,也许一个更好的方式来存储数据的地图地图,关键在第一个地图表示一行索引,和它的值是连续映射的键列索引值IntegerNode类。因此:

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.

如果您需要能够逐行遍历矩阵行,那么可以将行映射类型设置为TreeMap,按索引顺序遍历列也是如此,但是如果不需要这些情况,HashMap要比TreeMap快。获取和设置任意单元格(处理未设置的空值)的助手方法当然是有用的。

#4


4  

class IntegerNodeList extends LinkedList<IntegerNode> {}

IntegerNodeList[] myMatrix = new IntegerNodeList[numRows]; 

#5


3  

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

myMatrix = (LinkedList ])新的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; }

类IntegerNodeList {private final List< IntegerNode >节点;}

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?

看起来不错,是吗?

#6


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

没有任何警告。NetBeans 6.9.1,jdk1.6.0_24

#7


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.

Java 1.5中没有通用的数组创建(就我所知是1.6)。见https://community.oracle.com/message/4829402。

#8


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循环中初始化列表似乎是可行的。虽然它并不像其他的解决方案那样理想。

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

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

#9


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).

然后node_array[i]存储ArrayList 或LinkedList 的head(first)节点(无论您最喜欢的list实现是什么)。

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.

在这种设计下,您将丢失随机访问方法list.get(index),但是仍然可以遍历从类型安全数组中的head/fist节点存储开始的列表。

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.

根据您的用例,这可能是一个可接受的设计选择。例如,我使用这种设计来表示图的邻接列表,在大多数情况下,它需要遍历给定顶点的邻接列表,而不是随机访问列表中的某个顶点。