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