我正在上一堂CS入门课，其中一个最初的项目有以下限制：
您可能不会：
- 将您的程序作为程序包的一部分
- 添加其他公共方法或变量
- 在程序中的任何位置使用任何内置的Java Collections Framework类(例如，没有
ArrayList、LinkedList、HashSet等)- 在程序中的任何位置使用任何数组
- 添加任何额外的
import语句(或者使用"完全限定名称"来避免添加import语句)
看到该项目的限制，我想知道在这些限制范围内还能做些什么。我看到的主要限制是"；无阵列"；条款
是否可以设计受这些约束的数据结构，以模拟阵列的性能特征？具体地说，数据结构应该表示一个固定长度的序列，支持对"；得到"；或"；设置"；通过索引，这些操作应该花费O(1)时间，与序列的长度无关。
虽然可以构建类似图表的结构，如链表和树；得到"；以及"；设置"；对这些数据结构的操作将分别花费O(n)或O(logn)时间。我唯一能想到的另一件事是一个有几千个私有字段的类和一个CCD_；得到"；或"；设置"；按索引，但这只适用于固定长度以下的序列。
我认为，如果你遵循规则的精神，那么可以证明，你在获取或设置元素方面做得再好不过了。原因是，您实例化的每个对象最多可以存储固定数量的数据项和对其他对象的固定数量的引用，这些引用由该对象的字段数定义。
设D为对象所持有的数据项的(最大)数量，F为对象所拥有的引用字段的(最大的)数量。需要明确的是，D统计用于存储实际"数组"数据的字段，F统计用于数据结构本身的字段。
如果您的访问时间是O(1)，那么您最多可以遵循O(1个)引用来访问单元格，这意味着您的"数组"大小被限制为O(D*F^R)，其中R是允许执行一个操作的引用数量的固定限制。如果D、F和R这三个都是常数，那么"数组"的大小也是常数。因此，在给定约束的情况下，模拟任意大小的阵列数据结构的性能特性是不可能的。
这个论点可以进一步扩展一点，以证明R必须至少为O(logn)，才能达到n个不同的数据项；即您必须遵循至少O(logn)个引用才能访问项目。您可以使用一个完整的二叉树来实际实现这个界限。
也就是说，至少有一种方法可以在不遵循规则精神的情况下遵循规则的文字。
严格禁止使用数组或JCF库类，但关于第三方库类的唯一规则是不允许导入它们或使用完全限定的名称引用它们。您可以使用ClassLoader.loadClass方法从第三方库加载集合类，通过反射将其实例化，将其分配给Object类型的变量，然后通过反射调用其方法。这在技术上是允许的，因为loadClass采用的是要加载的类的"二进制名称"，而不是"完全限定名称"。(我将由律师来讨论是否需要加载一个二进制名称不是完全限定名称的类。)
对于学究们：我把关于数组的规则解释为，你的代码中不能有数组(大概除了主方法中的String[] args)，而不是你的代码调用的其他人的代码里不能有数组；否则，例如，您的程序被禁止打印任何输出，因为写入System.out的数据被缓冲在数组中。我认为这条规则不太可能是为了禁止打印任何输出。
如果没有任何可寻址空间，这将给您留下一个树结构，其中每个节点都有一个潜在值和多个子节点。每个节点一个子节点将使其成为链表，两个子节点将成为二进制树。每个节点允许的子节点越多，访问速度就越快——最终，当每个节点的子节点数符合或超过数组大小时，访问速度为O(1)。
阵列的操作包括：
- 使用初始插槽数进行初始化
- 获取数组的长度
- 获取索引处的元素
- 在索引处设置元素
我提出了以下解决方案(根据请求省略了二进制树、包和方法上的公共修饰符，这使得它只能在默认包中使用)：
public class Array<T> {
private final int length;
private final Cell<T> root = new Cell<>();
Array(int length) {
if (length < 0) {
throw new IllegalArgumentException("Array length must be >=0")
}
this.length = length;
}
T get(int index) {
return cell(index).value;
}
void set(int index, T value) {
cell(index).value = value;
}
int length() {
return length;
}
private Cell<T> cell(int index) {
if (index < 0 || index >= length) {
throw new ArrayIndexOutOfBoundsException(index);
}
Cell<T> pointer = root;
while (index > 0) {
pointer = (index & 1) == 0 ? pointer.left() : pointer.right();
index >>= 1;
}
return pointer;
}
private class Cell<T> {
private Cell<T> left;
private Cell<T> right;
private T value;
Cell<T> left() {
return left = left != null ? left : new Cell<>();
}
Cell<T> right() {
return right = right != null ? right : new Cell<>();
}
}
}