java

Question

这就是我所拥有的：

class Node {

    Integer value;
    ArrayList<Integer> adjList;

    public Node(Integer val, ArrayList<Integer> l) {
        value = val;
        Collections.sort(l);
        adjList = l;
    }
}

这就是我想要的:

class Node {

    Integer value;
    ArrayList<Node> adjList;

    public Node(Integer val, ArrayList<Integer> l) {
        value = val;
        Collections.sort(l,/*some comparator*/);
        adjList = l;
    }
}

所以我可以这样做:

private void process(){
    Random r = new Random(System.currentTimeMillis());
    while(vertices.size() > 2){
        Node v1 = vertices.get(r.nextInt(vertices.size()));
        Node v2 = v1.adjList.get(r.nextInt(v1.adjList.size()));
        contract(v1,v2); // Randomized contraction algorithm aka Karger's Min Cut algorithm
    }
}

但这就是困扰我的问题：

如果我将邻接列表声明为 ArrayList<Node> 类型，那么此列表的每个元素将存储一个指针或保留节点的完整副本（因此将一个数组列表嵌套在另一个数组列表中...无穷！）？

我希望将其存储为指针。在这里做什么？

Answer 1

与 C(++) 不同，Java 总是对对象使用指针。这意味着该列表将只存储那些引用。

然后，您节点中的列表还将存储对其他列表的引用，但每个列表在内存中只存在一次。

java - 使用 Arraylist 实现邻接列表

java - Implementing Adjacency lists using Arraylist

nested

arraylist