The OP (in the April 2012 updated revision of the question) is interested in knowing if there's a way to add to a list in amortized constant time, such as can be done, for example, with a C++ vector<> container. The best answer(s?) here so far only show the relative execution times for various solutions given a fixed-size problem, but do not address any of the various solutions' algorithmic efficiency directly. Comments below many of the answers discuss the algorithmic efficiency of some of the solutions, but in every case to date (as of April 2015) they come to the wrong conclusion.

算法效率捕获随着问题规模增长的时间(执行时间)或空间(内存消耗量)的增长特征。给定一个固定大小的问题，为各种解决方案运行性能测试并不能解决各种解决方案的增长速度。OP感兴趣的是知道是否有一种方法可以在“平摊常数时间”中将对象追加到R列表中。这是什么意思?为了解释，首先让我描述一下“常数时间”:

Constant or O(1) growth: If the time required to perform a given task remains the same as the size of the problem doubles, then we say the algorithm exhibits constant time growth, or stated in "Big O" notation, exhibits O(1) time growth. When the OP says "amortized" constant time, he simply means "in the long run"... i.e., if performing a single operation occasionally takes much longer than normal (e.g. if a preallocated buffer is exhausted and occasionally requires resizing to a larger buffer size), as long as the long-term average performance is constant time, we'll still call it O(1). For comparison, I will also describe "linear time" and "quadratic time": Linear or O(n) growth: If the time required to perform a given task doubles as the size of the problem doubles, then we say the algorithm exhibits linear time, or O(n) growth. Quadratic or O(n2) growth: If the time required to perform a given task increases by the square of the problem size, them we say the algorithm exhibits quadratic time, or O(n2) growth.

还有很多其他效率算法;我参考维基百科的文章进行进一步讨论。

我感谢@CronAcronis的回答，因为我是R的新手，很高兴有一个完整的代码块来对本页上提供的各种解决方案进行性能分析。我借用了他的代码用于我的分析，我复制了下面(包装在一个函数中):

library(microbenchmark)
### Using environment as a container
lPtrAppend <- function(lstptr, lab, obj) {lstptr[[deparse(substitute(lab))]] <- obj}
### Store list inside new environment
envAppendList <- function(lstptr, obj) {lstptr$list[[length(lstptr$list)+1]] <- obj} 
runBenchmark <- function(n) {
    microbenchmark(times = 5,  
        env_with_list_ = {
            listptr <- new.env(parent=globalenv())
            listptr$list <- NULL
            for(i in 1:n) {envAppendList(listptr, i)}
            listptr$list
        },
        c_ = {
            a <- list(0)
            for(i in 1:n) {a = c(a, list(i))}
        },
        list_ = {
            a <- list(0)
            for(i in 1:n) {a <- list(a, list(i))}
        },
        by_index = {
            a <- list(0)
            for(i in 1:n) {a[length(a) + 1] <- i}
            a
        },
        append_ = { 
            a <- list(0)    
            for(i in 1:n) {a <- append(a, i)} 
            a
        },
        env_as_container_ = {
            listptr <- new.env(parent=globalenv())
            for(i in 1:n) {lPtrAppend(listptr, i, i)} 
            listptr
        }   
    )
}

@CronAcronis发布的结果显然表明，a <- list(a, list(i))方法是最快的，至少对于10000大小的问题是这样，但是对于单个问题大小的结果并没有解决解决方案的增长问题。为此，我们需要针对不同的问题大小运行至少两个概要测试:

> runBenchmark(2e+3)
Unit: microseconds
              expr       min        lq      mean    median       uq       max neval
    env_with_list_  8712.146  9138.250 10185.533 10257.678 10761.33 12058.264     5
                c_ 13407.657 13413.739 13620.976 13605.696 13790.05 13887.738     5
             list_   854.110   913.407  1064.463   914.167  1301.50  1339.132     5
          by_index 11656.866 11705.140 12182.104 11997.446 12741.70 12809.363     5
           append_ 15986.712 16817.635 17409.391 17458.502 17480.55 19303.560     5
 env_as_container_ 19777.559 20401.702 20589.856 20606.961 20939.56 21223.502     5
> runBenchmark(2e+4)
Unit: milliseconds
              expr         min         lq        mean    median          uq         max neval
    env_with_list_  534.955014  550.57150  550.329366  553.5288  553.955246  558.636313     5
                c_ 1448.014870 1536.78905 1527.104276 1545.6449 1546.462877 1558.609706     5
             list_    8.746356    8.79615    9.162577    8.8315    9.601226    9.837655     5
          by_index  953.989076 1038.47864 1037.859367 1064.3942 1065.291678 1067.143200     5
           append_ 1634.151839 1682.94746 1681.948374 1689.7598 1696.198890 1706.683874     5
 env_as_container_  204.134468  205.35348  208.011525  206.4490  208.279580  215.841129     5
> 

First of all, a word about the min/lq/mean/median/uq/max values: Since we are performing the exact same task for each of 5 runs, in an ideal world, we could expect that it would take exactly the same amount of time for each run. But the first run is normally biased toward longer times due to the fact that the code we are testing is not yet loaded into the CPU's cache. Following the first run, we would expect the times to be fairly consistent, but occasionally our code may be evicted from the cache due to timer tick interrupts or other hardware interrupts that are unrelated to the code we are testing. By testing the code snippets 5 times, we are allowing the code to be loaded into the cache during the first run and then giving each snippet 4 chances to run to completion without interference from outside events. For this reason, and because we are really running the exact same code under the exact same input conditions each time, we will consider only the 'min' times to be sufficient for the best comparison between the various code options.

请注意，我选择首先运行问题大小为2000，然后运行问题大小为20000，因此我的问题大小从第一次运行到第二次运行增加了10倍。

表解性能:O(1)(常数时间)

Let's first look at the growth of the list solution, since we can tell right away that it's the fastest solution in both profiling runs: In the first run, it took 854 microseconds (0.854 milliseconds) to perform 2000 "append" tasks. In the second run, it took 8.746 milliseconds to perform 20000 "append" tasks. A naïve observer would say, "Ah, the list solution exhibits O(n) growth, since as the problem size grew by a factor of ten, so did the time required to execute the test." The problem with that analysis is that what the OP wants is the growth rate of a single object insertion, not the growth rate of the overall problem. Knowing that, it's clear then that the list solution provides exactly what the OP wants: a method of appending objects to a list in O(1) time.

其他解决方案的性能

其他的解决方案都没有接近列表解决方案的速度，但无论如何，检查它们都是有信息的:

Most of the other solutions appear to be O(n) in performance. For example, the by_index solution, a very popular solution based on the frequency with which I find it in other SO posts, took 11.6 milliseconds to append 2000 objects, and 953 milliseconds to append ten times that many objects. The overall problem's time grew by a factor of 100, so a naïve observer might say "Ah, the by_index solution exhibits O(n2) growth, since as the problem size grew by a factor of ten, the time required to execute the test grew by a factor of 100." As before, this analysis is flawed, since the OP is interested in the growth of a single object insertion. If we divide the overall time growth by the problem's size growth, we find that the time growth of appending objects increased by a factor of only 10, not a factor of 100, which matches the growth of the problem size, so the by_index solution is O(n). There are no solutions listed which exhibit O(n2) growth for appending a single object.

这是一个简单的方法来添加项目到R列表:

# create an empty list:
small_list = list()

# now put some objects in it:
small_list$k1 = "v1"
small_list$k2 = "v2"
small_list$k3 = 1:10

# retrieve them the same way:
small_list$k1
# returns "v1"

# "index" notation works as well:
small_list["k2"]

或通过编程:

kx = paste(LETTERS[1:5], 1:5, sep="")
vx = runif(5)
lx = list()
cn = 1

for (itm in kx) { lx[itm] = vx[cn]; cn = cn + 1 }

print(length(lx))
# returns 5

如果你将列表变量作为一个带引号的字符串传入，你可以像这样从函数内部到达它:

push <- function(l, x) {
  assign(l, append(eval(as.name(l)), x), envir=parent.frame())
}

so:

> a <- list(1,2)
> a
[[1]]
[1] 1

[[2]]
[1] 2

> push("a", 3)
> a
[[1]]
[1] 1

[[2]]
[1] 2

[[3]]
[1] 3

> 

或者为了获得额外的学分:

> v <- vector()
> push("v", 1)
> v
[1] 1
> push("v", 2)
> v
[1] 1 2
> 

> LL<-list(1:4)

> LL

[[1]]
[1] 1 2 3 4

> LL<-list(c(unlist(LL),5:9))

> LL

[[1]]
 [1] 1 2 3 4 5 6 7 8 9

我运行了以下基准测试:

bench=function(...,n=1,r=3){
  a=match.call(expand.dots=F)$...
  t=matrix(ncol=length(a),nrow=n)
  for(i in 1:length(a))for(j in 1:n){t1=Sys.time();eval(a[[i]],parent.frame());t[j,i]=Sys.time()-t1}
  o=t(apply(t,2,function(x)c(median(x),min(x),max(x),mean(x))))
  round(1e3*`dimnames<-`(o,list(names(a),c("median","min","max","mean"))),r)
}

ns=10^c(3:7)
m=sapply(ns,function(n)bench(n=5,
  `vector at length + 1`={l=c();for(i in 1:n)l[length(l)+1]=i},
  `vector at index`={l=c();for(i in 1:n)l[i]=i},
  `vector at index, initialize with type`={l=integer();for(i in 1:n)l[i]=i},
  `vector at index, initialize with length`={l=vector(length=n);for(i in 1:n)l[i]=i},
  `vector at index, initialize with type and length`={l=integer(n);for(i in 1:n)l[i]=i},
  `list at length + 1`={l=list();for(i in 1:n)l[[length(l)+1]]=i},
  `list at index`={l=list();for(i in 1:n)l[[i]]=i},
  `list at index, initialize with length`={l=vector('list',n);for(i in 1:n)l[[i]]=i},
  `list at index, initialize with double length, remove null`={l=vector("list",2*n);for(i in 1:n)l[[i]]=i;l=head(l,i)},
  `list at index, double when full, get length from variable`={len=1;l=list();for(i in 1:n){l[[i]]=i;if(i==len){len=len*2;length(l)=len}};l=head(l,i)},
  `list at index, double when full, check length inside loop`={len=1;l=list();for(i in 1:n){l[[i]]=i;if(i==length(l)){length(l)=i*2}};l=head(l,i)},
  `nested lists`={l=list();for(i in 1:n)l=list(l,i)},
  `nested lists with unlist`={if(n<=1e5){l=list();for(i in 1:n)l=list(l,i);o=unlist(l)}},
  `nested lists with manual unlist`={l=list();for(i in 1:n)l=list(l,i);o=integer(n);for(i in 1:n){o[n-i+1]=l[[2]];l=l[[1]]}},
  `JanKanis better_env_as_container`={env=new.env(hash=T,parent=globalenv());for(i in 1:n)env[[as.character(i)]]=i},
  `JanKanis inlineLinkedList`={a=list();for(i in 1:n)a=list(a,i);b=vector('list',n);head=a;for(i in n:1){b[[i]]=head[[2]];head=head[[1]]}},
  `JanKanis inlineExpandingList`={l=vector('list',10);cap=10;len=0;for(i in 1:n){if(len==cap){l=c(l,vector('list',cap));cap=cap*2};len=len+1;l[[len]]=i};l[1:len]},
  `c`={if(n<=1e5){l=c();for(i in 1:n)l=c(l,i)}},
  `append vector`={if(n<=1e5){l=integer(n);for(i in 1:n)l=append(l,i)}},
  `append list`={if(n<=1e9){l=list();for(i in 1:n)l=append(l,i)}}
)[,1])

m[rownames(m)%in%c("nested lists with unlist","c","append vector","append list"),4:5]=NA
m2=apply(m,2,function(x)formatC(x,max(0,2-ceiling(log10(min(x,na.rm=T)))),format="f"))
m3=apply(rbind(paste0("1e",log10(ns)),m2),2,function(x)formatC(x,max(nchar(x)),format="s"))
writeLines(apply(cbind(m3,c("",rownames(m))),1,paste,collapse=" "))

输出:

 1e3   1e4   1e5  1e6   1e7
2.35  24.5   245 2292 27146 vector at length + 1
0.61   5.9    60  590  7360 vector at index
0.61   5.9    64  587  7132 vector at index, initialize with type
0.56   5.6    54  523  6418 vector at index, initialize with length
0.54   5.5    55  522  6371 vector at index, initialize with type and length
2.65  28.8   299 3955 48204 list at length + 1
0.93   9.2    96 1605 13480 list at index
0.58   5.6    57  707  8461 list at index, initialize with length
0.62   5.8    59  739  9413 list at index, initialize with double length, remove null
0.88   8.4    81  962 11872 list at index, double when full, get length from variable
0.96   9.5    92 1264 15813 list at index, double when full, check length inside loop
0.21   1.9    22  426  3826 nested lists
0.25   2.4    29   NA    NA nested lists with unlist
2.85  27.5   295 3065 31427 nested lists with manual unlist
1.65  20.2   293 6505  8835 JanKanis better_env_as_container
1.11  10.1   110 1534 27119 JanKanis inlineLinkedList
2.66  26.3   266 3592 47120 JanKanis inlineExpandingList
1.22 118.6 15466   NA    NA c
3.64 512.0 45167   NA    NA append vector
6.35 664.8 71399   NA    NA append list

上表显示的是每种方法的中值时间，而不是平均时间，因为有时单个运行的时间比典型运行的时间长得多，这会扭曲平均运行时间。但是在第一次运行之后的后续运行中，没有一种方法变得更快，因此每种方法的最小时间和中值时间通常是相似的。

The method "vector at index" (l=c();for(i in 1:n)l[i]=i) was about 5 times faster than "vector at length + 1" (l=c();for(i in 1:n)l[length(l)]=i), because getting the length of the vector took longer than adding an element to the vector. When I initialized the vector with a predetermined length, it made the code about 20% faster, but initializing with a specific type didn't make a difference, because the type just needs to be changed once when the first item is added to the vector. And in the case of lists, when you compare the methods "list at index" and "list at index initialized with length", initializing the list with a predetermined length made a bigger difference as the length of the list increased, because it made the code about twice as fast at length 1e6 but about 3 times as fast at length 1e7.

方法“list at index”(l=list();for(i in 1:n)l[[i]]=i)比方法“list at length +1”(l=list();for(i in 1:n)l[[length(l)+1]]=i)快3-4倍。

JanKanis的链表和扩展列表方法比“索引列表”慢，但比“长度+ 1列表”快。链表比扩展表快。

有些人声称append函数比c函数快，但在我的基准测试中，append大约比c慢3-4倍。

在上表中，长度1e6和1e7和在三个方法中缺失:对于“c”，“append vector”和“append list”，因为它们具有二次时间复杂度，以及对于“带有unlist的嵌套列表”，因为它会导致堆栈溢出。

The "nested lists" option was the fastest, but it doesn't include the time that it takes to flatten the list. When I used the unlist function to flatten the nested list, I got a stack overflow when the length of the list was around 1.26e5 or higher, because the unlist function calls itself recursively by default: n=1.26e5;l=list();for(i in 1:n)l=list(l,list(i));u=unlist(l). And when I used repeated calls of unlist(recursive=F), it took about 4 seconds to run even for a list with only 10,000 items: for(i in 1:n)l=unlist(l,recursive=F). But when I did the unlisting manually, it only took about 0.3 seconds to run for a list with a million items: o=integer(n);for(i in 1:n){o[n-i+1]=l[[2]];l=l[[1]]}.

If you don't know how many items you are going to append to a list in advance but you know the maximum number of items, then you can try to initialize the list at the maximum length and then later remove NULL values. Or another approach is to double the size of the list every time the list becomes full (which you can do faster if you have one variable for the length of the list and another variable for the number of items you have added to the list, so then you don't have to check the length of the list object on each iteration of a loop):

ns=10^c(2:7)
m=sapply(ns,function(n)bench(n=5,
  `list at index`={l=list();for(i in 1:n)l[[i]]=i},
  `list at length + 1`={l=list();for(i in 1:n)l[[length(l)+1]]=i},
  `list at index, initialize with length`={l=vector("list",n);for(i in 1:n)l[[i]]=i},
  `list at index, initialize with double length, remove null`={l=vector("list",2*n);for(i in 1:n)l[[i]]=i;l=head(l,i)},
  `list at index, initialize with length 1e7, remove null`={l=vector("list",1e7);for(i in 1:n)l[[i]]=i;l=head(l,i)},
  `list at index, initialize with length 1e8, remove null`={l=vector("list",1e8);for(i in 1:n)l[[i]]=i;l=head(l,i)},
  `list at index, double when full, get length from variable`={len=1;l=list();for(i in 1:n){l[[i]]=i;if(i==len){len=len*2;length(l)=len}};l=head(l,i)},
  `list at index, double when full, check length inside loop`={len=1;l=list();for(i in 1:n){l[[i]]=i;if(i==length(l)){length(l)=i*2}};l=head(l,i)}
)[,1])

m2=apply(m,2,function(x)formatC(x,max(0,2-ceiling(log10(min(x)))),format="f"))
m3=apply(rbind(paste0("1e",log10(ns)),m2),2,function(x)formatC(x,max(nchar(x)),format="s"))
writeLines(apply(cbind(m3,c("",rownames(m))),1,paste,collapse=" "))

输出:

  1e4 1e5  1e6   1e7
  9.3 102 1225 13250 list at index
 27.4 315 3820 45920 list at length + 1
  5.7  58  726  7548 list at index, initialize with length
  5.8  60  748  8057 list at index, initialize with double length, remove null
 33.4  88  902  7684 list at index, initialize with length 1e7, remove null
333.2 393 2691 12245 list at index, initialize with length 1e8, remove null
  8.6  83 1032 10611 list at index, double when full, get length from variable
  9.3  96 1280 14319 list at index, double when full, check length inside loop

我对这里提到的方法做了一个小的比较。

n = 1e+4
library(microbenchmark)
### Using environment as a container
lPtrAppend <- function(lstptr, lab, obj) {lstptr[[deparse(substitute(lab))]] <- obj}
### Store list inside new environment
envAppendList <- function(lstptr, obj) {lstptr$list[[length(lstptr$list)+1]] <- obj} 

microbenchmark(times = 5,  
        env_with_list_ = {
            listptr <- new.env(parent=globalenv())
            listptr$list <- NULL
            for(i in 1:n) {envAppendList(listptr, i)}
            listptr$list
        },
        c_ = {
            a <- list(0)
            for(i in 1:n) {a = c(a, list(i))}
        },
        list_ = {
            a <- list(0)
            for(i in 1:n) {a <- list(a, list(i))}
        },
        by_index = {
            a <- list(0)
            for(i in 1:n) {a[length(a) + 1] <- i}
            a
        },
        append_ = { 
            a <- list(0)    
            for(i in 1:n) {a <- append(a, i)} 
            a
        },
        env_as_container_ = {
            listptr <- new.env(parent=globalenv())
            for(i in 1:n) {lPtrAppend(listptr, i, i)} 
            listptr
        }   
)

结果:

Unit: milliseconds
              expr       min        lq       mean    median        uq       max neval cld
    env_with_list_  188.9023  198.7560  224.57632  223.2520  229.3854  282.5859     5  a 
                c_ 1275.3424 1869.1064 2022.20984 2191.7745 2283.1199 2491.7060     5   b
             list_   17.4916   18.1142   22.56752   19.8546   20.8191   36.5581     5  a 
          by_index  445.2970  479.9670  540.20398  576.9037  591.2366  607.6156     5  a 
           append_ 1140.8975 1316.3031 1794.10472 1620.1212 1855.3602 3037.8416     5   b
 env_as_container_  355.9655  360.1738  399.69186  376.8588  391.7945  513.6667     5  a