java - 获取特定位置的所有元素的数据结构

Question

我有一个Grid具有一定高度和宽度的正方形。它包含类的成员Item。每一个Item都有一定的Position。我希望能够在恒定时间内将所有项目放在某个位置，并且我希望能够在摊销恒定时间内将项目放置在网格上。

什么（Java）结构可以做到这一点，同时使用与已使用位置（至少有 1 个项目的位置）数量成正比的内存量？

Answer 1

如果您的 Grid 具有固定大小，我将使用数组。

Item[][] itemArray = new Item[3][3];
itemArray[0][0] = new Item();
System.out.println(itemArray[0][0]);

我会把它包装到课堂上Grid

public final class Grid {

    private Item[][] grid;

    public Grid(int width, int height) {
        grid = new Item[width][height];
    }

    public void setItemAt(Position position, Item item) {
        int x = position.getX();
        int y = position.getY();

        grid[x][y] = item;
    }

    public Item getItemAt(Position position) {
        int x = position.getX();
        int y = position.getY();

        return grid[x][y];
    }
}

Answer 2

上面的用户是对的，您可以在内部使用数组。当然它应该是 type List<Item>[][]。无论你使用ArrayList或LinkedList，加法都会摊销常数时间。尽管我建议您选择 a LinkedList，因为您Grid的人口可能很少（ArrayList总是从已经分配的几个空间开始）。

如果Grid需要能够增长，只需​​使用相同的技巧ArrayList：跟踪当前的宽度/高度，如果您需要更多空间，只需将可用空间乘以合适的值（对于 2D 数组，加倍可能有点多，但这取决于可能的增长类型）。