在 R 中滚动你自己的链表/树？

Question

我试图理解 R 编程语言的基本概念，但发现这很困难，因为 R 面向统计而不是通用编程。我找不到任何类似于指针/引用的内容。如何在 R 语言中实现链表、搜索树等？

注意:我知道，如果您实际上在 R 中滚动自己的自引用数据结构，那么可能有更好的方法来完成您想要完成的任务。不过，我相信答案将帮助我更好地理解该语言的整体结构和概念。

编辑:关于 Matt Shotwell 的评论，这个问题的要点是我希望在 R 中干净地编写链接列表和树，而不是作为用 C 或其他语言编写的扩展其他语言。将其作为扩展或通过解释器的神秘细节进行破坏会达不到目的。

Answer 1

R 中的链表可以表示为向量，通常是列表。您无需编写特殊代码来引用下一个和上一个项目，因为 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 类可以使用更结构化的方法，但这可以在紧要关头完成工作。