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

Question

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

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

编辑:关于Matt Shotwell的评论,这个问题的关键在于我希望在 R中干净地编写链表和树,而不是用C或其他语言编写的扩展.做它作为一个扩展或通过与解释器的神秘细节混淆失败的目的.

Answer 1

R中的链表可以表示为矢量,通常是a 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课程可以获得更多结构化方法,但这样做可以解决这个问题.