动态数组添加到底？ [英] Dynamic array add at the end?
问题描述
从初始长度为4且numElements = 0的动态数组开始，当我们在末尾添加以下数字时显示该数组：5、19、4、6，-1。
Starting with a dynamic array of initially length = 4 and numElements = 0, show the array when we add the followings numbers at the end: 5, 19, 4, 6, -1.
我收到的检查点（答案）是[5、19、4、6，-1，X，X，X]，其中X表示可以忽略的条目。
The checkpoint (answer) I receive is [5, 19, 4, 6, -1, X, X, X], where X denotes the entries which can be ignored.
我有2个愚蠢的问题：
-
我认为最后插入会使其[ X，X，X，5、19、4、6，-1]，而不是现在的答案？
I thought insert at the end would make it [X, X, X, 5, 19, 4, 6, -1] instead of what it looks like right now in the answer?
我最初是每次我们在数组中添加内容时，数组都会自动将其长度加倍，这就是为什么我们在末尾有3个X，使总结尾长度为8而不是初始大小为4。这是正确的吗？ / p>
I initially though every time we add something in the array, the array would automatically double the its length, that is why we have the 3 X's at the end, making the total ending length is 8 instead of the initial size of 4. Is this correct?
推荐答案
它的工作原理是这样的。
It works like this.
在末尾添加表示追加到数组的末尾。
"Adding at the end" means appending to the end of the array. Let's do it first without worrying about the internals.
首先，列表为空
[]
然后插入5
[5]
然后19
[5, 19]
然后是4，然后是6，然后是-1
Then 4 then 6 then -1
[5, 19, 4]
[5, 19, 4, 6]
[5, 19, 4, 6, -1]
现在，当我们拥有容量为4的倍数的数组时，它的外观如何。正如您所说，当数组填满时它们的大小会加倍。所以这就是进度：
Now how does this look when we have arrays whose capacities are in multiples of 4. As you say, they do double in size when they fill up. So this is the progression:
X X X X
5 X X X
5 19 X X
5 19 4 X
5 19 4 6
5 19 4 6 -1 X X X
插入前四个元素时，将填满4个块。插入第5个元素时，我们没有空间，因此我们必须将容量增加一倍至8，然后将第5个元素放在第一个可用插槽中。
When inserting the first 4 elements, the block of 4 fills up. When inserting the 5th, we don't have room, so we have to double the capacity to 8, then put the 5th element in the first available slot.
所以是的您将容量翻倍是正确的。但是，数组元素始终从头开始填充，最后使用未使用的插槽。如果将值放在末尾，则每次插入时都必须将其移到左侧，这会非常无效率。
So yes you are correct about doubling the capacity. But the array elements are always filled from the beginning with the unused slots at the end. If you put values at the end, you would have to shift them over to the left on every insertion, which would be very inefficient.
这篇关于动态数组添加到底？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
