如题。显然它不只是个动态列表，比如下面这段 fortran 代码在我机子上要花11秒：
program tst
implicit none
integer(8),allocatable:: lst(:)
integer(8)::o1
lst=[integer(8)::]
do o1=1,60000*2
lst=[lst,o1]
end do
print *, size(lst)
end program
而这段 Mathematica 代码只要0.006秒：
$ContextPath = DeleteDuplicates@Append[$ContextPath, "Internal`"];
dat = Compile[{},
Module[{list = Bag@Most@{0}}, Do[StuffBag[list, index], {index, 6 10^4 2}];
BagPart[list, All]]][]; // AbsoluteTiming

顺便说一句，这个问题是在研究 @草红样 给SE问题《Insert +, −, ×, /, (, ) into 123456789 to make it equal to 100》（编号15021）写的新答案的过程中产生的。在此期间令（我这个孤陋寡闻的）人惊讶的事情有不少，但大都不太适合在这个吧里谈（比如，至少在当前，在 IJulia 里调用大脚本会发生假死），就暂且不表吧。

换到Chrome后居然不需要APP验证也能回帖了，那就回复下吧
对Fortran的动态列表实现不太了解，但在C++里用vector的push_back实现这个需求速度是非常快的，我这里试了下长度1e6时用时4ms左右，而相应的mma代码即使减去Compile时间，也要20ms了
#include <ctime>
#include <iostream>
#include <vector>
int main(){
clock_t t_start = clock();
std::vector<int> list;
for (int i = 1; i <= 1e6; ++i){
list.push_back(i);
}
std::cout << "Vector size: " << int(list.size()) << std::endl;
std::cout << "Time used: " << double(clock() - t_start) / CLOCKS_PER_SEC * 1000 << "ms" << std::endl;
return 0;
}

对于原因猜测如下：
vector生成时会预留部分空白内存空间，push_back时直接把元素存入空白空间，然后改变vector的size和结尾指针位置即可，复杂度O(1)。只有当空白空间满了之后才会需要重新申请内存+整个复制列表，此时复杂度O(n)，n为当前size。大量push_back时只有少数几次需要扩充，所以速度比较快。具体原理可以参考这个网页：https://www.cnblogs.com/yao2yaoblog/p/7170239.html
而fortran的写法，我怀疑是每次都做了重新申请内存+复制列表的过程，所以才会这么慢

4楼有一个外链地址，果然被屏蔽了，删掉重发下吧
对于原因猜测如下：
vector生成时会预留部分空白内存空间，push_back时直接把元素存入空白空间，然后改变vector的size和结尾指针位置即可，复杂度O(1)。只有当空白空间满了之后才会需要重新申请内存+整个复制列表，此时复杂度O(n)，n为当前size。大量push_back时只有少数几次需要扩充，所以速度比较快。具体原理可以参考这个网页：
`链接删除，请自行搜索“STL vector push_back详解”`
而fortran的写法，我怀疑是每次都做了重新申请内存+复制列表的过程，所以才会这么慢

julia 的 append! 疑似是有相应的优化的：
lst=[]
@time(for i in 1:120000
append!(lst,i)
end)
length(lst)
但是，在使用 julia 处理 2 楼所提问题时出现了严重的效率问题，理由不明。（julia 对大函数优化有问题？搞不清楚。）总之把代码放一下。Mathematica侧：
n = 9;
original = Groupings[Table[x, n], f -> 2];
expr = Block[{i = 1, j = 1}, # /. f[x, x] -> froot[x, x] /.
{(head : f | froot) :> (head[#, o[i++], #2] &), x :> j++}] & /@ original;
string = "exprfunc(" <>
StringTake[StringTemplate["o``::Int64"] /@ Range[8] // ToString, {2, -2}] <>
")::Vector{Float64}=[" <>
StringTake[expr /. o[i_] :> Symbol@StringTemplate["o``"]@i // CForm //
ToString, {6, -2}] <> "]"; // AbsoluteTiming
Export[FileNameJoin@{$HomeDirectory,"exprfuncjulia.jl"}, string, "Text"] // AbsoluteTiming
julia侧：
f(x::Float64,o::Int64,y::Float64)=
begin
if o==1
x+y
elseif o==2
x-y
elseif o==3
x*y
elseif o==4
if y==0
pi
else
x/y
end
elseif o==5
y-x
else
pi
end
end
froot(x::Float64,o::Int64,y::Float64)=
begin
if o==1
x+y
elseif o==2
x-y
elseif o==3
x*y
elseif o==4
if y==0
pi
else
x/y
end
elseif o==5
y-x
elseif o==6
10*x+y
end
end
possiblelst=[]
#注意exprfuncjulia.jl文件的路径可能要改
include("exprfuncjulia.jl")
#注意以下代码在IJulia中会引发不明原因的假死，请使用命令行执行——不过就算用命令行也是慢得要命
for o1 in 1:6,o2 in 1:6,o3 in 1:6,o4 in 1:6,o5 in 1:6,o6 in 1:6,o7 in 1:6,o8 in 1:6
mid=exprfunc(o1,o2,o3,o4,o5,o6,o7,o8)
for index in 1:1430
if mid[index]==100
append!(possiblelst,[o1,o2,o3,o4,o5,o6,o7,o8,index])
end
end
end

操作系统在分配内存的时候每次只能分配固定长度的内存。为了兼顾内存和速度，所以一般这种可以动态增长的表都是先分配一个长度8的，不够了就分配一个16的，然后把老的内容拷过去，后面就是32、64这种。

可以查查动态顺序表啥的