arrays - 没有动态内存分配的LinkedList

假设我们使用的开发环境没有动态内存（只有具有固定边界的静态数组）。如何实现List（或ArrayList）。
好吧，当我试图将元素添加到一个完整的数组中时，我想创建一个更大的新数组，但我希望有更有效的方法。
附：我不是在要求实施，我是在征求意见：）

最佳答案

您可以查看Sedgewick关于动态数组的文档并调整它们的大小您可以在Dynamic Array - Wikipedia中看到总体概念，在this paper which is written by Sedgewick中看到更详细的定义
还有一个样本在ResizingArrayQueue by Sedgewick
尽管如此，该示例用于队列，您也可以将此机制用于链接列表。
在这个样本中，当它达到极限时，它的大小是原来的两倍。

public void enqueue(Item item) {
        // double size of array if necessary and recopy to front of array
        if (N == q.length) resize(2*q.length);   // double size of array if necessary
        q[last++] = item;                        // add item
        if (last == q.length) last = 0;          // wrap-around
        N++;
    }

当限制降低到数组的四分之一时，他将数组减半。

 public Item dequeue() {
        if (isEmpty()) throw new NoSuchElementException("Queue underflow");
        Item item = q[first];
        q[first] = null;                            // to avoid loitering
        N--;
        first++;
        if (first == q.length) first = 0;           // wrap-around
        // shrink size of array if necessary
        if (N > 0 && N == q.length/4) resize(q.length/2);
        return item;
    }