用R滚动你自己的链表/树

Question

我试图把我的头脑围绕R编程语言的基本概念，我发现这很难，因为R是面向统计而不是通用编程的。我找不到类似于指针/引用的东西。如何在R语言中实现链表、搜索树等?

注意:我明白，如果你实际上是在R中滚动你自己的自引用数据结构，可能有更好的方法来完成你想要完成的事情。但是，我相信一个答案会帮助我更好地理解这门语言的整体结构和概念。

编辑:关于Matt Shotwell的评论，这个问题的重点是我希望在 R内干净地编写链表和树，而不是用C或其他语言编写的扩展。将其作为扩展或与解释器的神秘细节相混淆会破坏目的。

Answer 1

R中的链表可以表示为一个向量，通常是一个list。你不需要编写特殊的代码来引用下一项和上一项，因为R通过索引为你完成了。

要向列表中添加新项，只需跟踪其长度并将其分配给下一行。

lst <- list() # creates an empty (length zero) list
lst[[1]] <- 1 # automagically extends the lst
lst[[2]] <- 2 # ditto

由于R处理内存的方式，这对于长列表可能是低效的。如果可能的话，提前创建列表，并在它们可用时分配它们的内容。

lst <- list(1, 2, 3, 4, 5)    # a list of 5 items
lst <- vector("list", 10000)  # 10000 NULLs
lst[[1]] <- 1
lst[[10000]] <- 10000  # lst now contains 1, NULL, ..., NULL, 10000

从列表中删除项目可以使用负索引来完成。

lst <- list(1, 2, 3, 4, 5)
lst <- lst[-2]  # now contains 1, 3, 4, 5

树就是一个包含其他列表的列表。

tree <- list(list(1, 2), list(3, list(4, 5)))
# left child: list(1, 2)
tree[[1]]
# right child
tree[[2]]
# right child of right child:list(4, 5)
tree[[2]][[2]]

默认情况下，没有内置的强制结构，例如二叉树的每个节点只有两个子节点。更结构化的方法可以通过S4类获得，但这将在紧要关头完成工作。