LinkedList没有动态内存分配

让我们假设我们正在使用没有动态内存的开发环境（只有固定边界的静态数组）。如何实现List（或ArrayList）。那么，我想创建一个更大的新阵列，当我试图添加元素到一个完整的数组，但我希望有更有效的方法。 P.S我没有要求执行，我想要的想法:)LinkedList没有动态内存分配

来源

2015-11-18 Rahul Katrakhtalapali

一个常见的技巧是重新创建列表，如果它已满。不是只有一个元素，但很多，预计的规模增长。以这种方式，如果达到上限，你将只有很小的性能影响。 ...哦等等...这就是你建议的:-) – Stefan

另一种方法是为所有可能的类型创建一个容器，并为该容器（或一对）创建最大可能的列表。然后，您将能够从该大数组中创建子列表，并且该类型在该容器中定义。有点像旧的'VARIANT'（https://msdn.microsoft.com/en-us/library/windows/desktop/ms221627%28v=vs.85%29.aspx）容器。它会给你速度超过记忆，但通常这是不值得的。 – Stefan

您可以检查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; 
    }

来源

2015-11-18 08:35:08

LinkedList没有动态内存分配

回答

相关问题