LinkedList沒有動態內存分配

Question

讓我們假設我們正在使用沒有動態內存的開發環境（只有固定邊界的靜態數組）。如何實現List（或ArrayList）。 那麼，我想創建一個更大的新陣列，當我試圖添加元素到一個完整的數組，但我希望有更有效的方法。 P.S我沒有要求執行，我想要的想法:)

Answer 1

您可以檢查Sedgewick的關於動態數組的文檔並調整它們的大小。你可以看到在Dynamic Array - Wikipedia和總體思路更詳細的定義this paper which is written by Sedgewick 還存在ResizingArrayQueue by Sedgewick

樣本雖然示例中使用你可以使用這種機制也爲linkedlists隊列。 在這個示例中，當它達到極限時，他將其大小加倍。

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; 
    }