java - 使用 Arraylist 实现邻接列表

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总是使用对象指针。这意味着该列表将仅存储这些引用。

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