在 R 中滚动你自己的链表/树? [英] Roll Your Own Linked List/Tree in R?

问题描述

我正在尝试围绕 R 编程语言的基本概念进行思考，但我发现这很困难，因为 R 面向统计而不是通用编程.我找不到任何类似于指针/引用的东西.您将如何在 R 语言中实现链表、搜索树等?

I'm trying to wrap my head around the basic concepts of the R programming language and am finding it difficult since R is geared towards statistics instead of general-purpose programming. I can't find anything similar to pointers/references. How would you implement a linked list, search tree, etc. within the R language?

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

Note: I understand that if you're actually rolling your own self-referential data structures in R, there's probably a better way to accomplish what you're trying to accomplish. However, I believe an answer will help me understand the overall structure and concepts of the language better.

关于 Matt Shotwell 的评论，这个问题的重点是我希望在 R 中干净地编写链表和树，而不是作为用 C 或其他语言编写的扩展其他语言.将其作为扩展或通过解释解释器的神秘细节来实现目的.

With regard to Matt Shotwell's comment, the point of this question is that I'm looking to write linked lists and trees cleanly, within R, not as an extension written in C or some other language. Doing it as an extension or by mucking with arcane details of the interpreter defeats the purpose.

推荐答案

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

A linked list in R can be represented as a vector, typically a list. You don't need to write special code to reference the next and previous items, because R does it for you via indexing.

要将新项目添加到列表中，只需跟踪其长度并分配给下一行即可.

To add a new item to the list, just keep track of its length and assign to the next in line.

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

由于 R 处理内存的方式，这对于长列表来说可能效率低下.如果可能，请提前创建列表，并在可用时分配其内容.

This can be inefficient for long lists because of the way R handles memory. If possible, create the list in advance, and assign their contents as they become available.

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

从列表中删除一个项目可以用负索引来完成.

Deleting an item from the list can be accomplished with negative indexes.

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

树只是一个包含其他列表的列表.

A tree is just a list containing other lists.

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 类可以获得更多结构化的方法，但这将在紧要关头完成这项工作.

By default there is no built-in enforcing of the structure, eg only two children per node for a binary tree. More structured approaches are available via S4 classes, but this will do the job in a pinch.

这篇关于在 R 中滚动你自己的链表/树?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！