如何在R语言及R Studio中创建双向链表？附节点函数代码示例

Hey there! R doesn’t come with a native doubly linked list structure, but we can build one ourselves using environments—since environments are reference-type objects, they let us create the mutual node references that make doubly linked lists work. Let’s walk through this, including fixing and explaining the code snippet you shared.

一、核心概念：双向链表在R中的实现逻辑 #

A doubly linked list is made up of nodes where each node holds three key pieces of information:

• A stored value (val)
• A reference to the previous node (prev)
• A reference to the next node (next)

In R, regular objects are passed by value, which makes them useless for node references (copying breaks the link between nodes). Environments, though, are passed by reference—so modifying an environment’s contents changes the original object, exactly what we need for linked nodes.

二、R Studio中实现双向链表的完整步骤 #

Let’s build this out in R Studio step by step:

1. 完善节点构造函数（基于你的代码） #

Your dlinkListNode function is a solid starting point, but it’s incomplete. Here’s the fixed, annotated version:

# 双向链表节点构造函数
dlinkListNode <- function(val, prev_node = NULL, next_node = NULL) {
  # 创建一个空父环境的新环境（避免意外继承全局变量）
  node_env <- new.env(parent = emptyenv())
  
  # 给节点赋值：存储值、前驱节点、后继节点
  node_env$value <- val
  node_env$prev <- prev_node
  node_env$next <- next_node
  
  # 返回这个环境作为节点对象
  return(node_env)
}

2. 实现链表的核心操作 #

We’ll add helper functions to create a list, append nodes, and traverse forward/backward:

# 创建一个新的双向链表（带头尾指针，方便操作）
create_dlink_list <- function(initial_val) {
  head_node <- dlinkListNode(initial_val)
  # 返回包含头尾指针的列表，方便后续操作
  list(head = head_node, tail = head_node)
}

# 在链表尾部插入新节点
append_node <- function(dlink_list, val) {
  # 新节点的前驱是当前尾节点
  new_node <- dlinkListNode(val, prev_node = dlink_list$tail)
  # 原尾节点的后继指向新节点
  dlink_list$tail$next <- new_node
  # 更新链表的尾节点为新节点
  dlink_list$tail <- new_node
}

# 正向遍历（从头到尾）
traverse_forward <- function(head_node) {
  current <- head_node
  while (!is.null(current)) {
    cat(current$value, " ")
    current <- current$next
  }
  cat("\n")
}

# 反向遍历（从尾到头）
traverse_backward <- function(tail_node) {
  current <- tail_node
  while (!is.null(current)) {
    cat(current$value, " ")
    current <- current$prev
  }
  cat("\n")
}

3. 在R Studio中测试运行 #

1. Open R Studio, paste all the above code into a new script file (.R).
2. Run the script (click the "Run" button or press Ctrl+Enter line by line).
3. Test with this code to verify functionality:

# 创建一个初始值为10的链表
my_dlist <- create_dlink_list(10)

# 插入两个新节点
append_node(my_dlist, 20)
append_node(my_dlist, 30)

# 测试遍历
cat("正向遍历结果：\n")
traverse_forward(my_dlist$head) # 输出：10 20 30 

cat("反向遍历结果：\n")
traverse_backward(my_dlist$tail) # 输出：30 20 10 

三、解析你提供的原始dlinkListNode函数 #

Let’s break down the incomplete code you shared:

dlinkListNode <- function(val, prevnode=NULL, node=NULL) { 
  llist <- new.env(parent=create_emptyenv()) 
}

关键亮点（正确的部分） #

• Using environments: new.env(parent=create_emptyenv()) is a smart choice. Creating an environment with an empty parent ensures the node doesn’t accidentally inherit variables from the global environment, keeping it self-contained. (Note: R’s native empty environment is emptyenv()—create_emptyenv() is likely a custom wrapper, but they serve the same purpose.)
• Parameter setup: The val, prevnode, and node parameters correctly align with the needs of a doubly linked list node (though node is a confusing name—nextnode would be much clearer for readability).

主要缺陷（为什么它不工作） #

1. No assignment to the environment: The function creates llist but never stores the val, prevnode, or node inside it. So the node has no data or references to other nodes.
2. No return value: The function doesn’t return llist, so when you call dlinkListNode(5), you get NULL instead of a usable node object.
3. Ambiguous parameter name: node should be renamed to nextnode to make the code’s intent obvious to anyone reading it.

内容的提问来源于stack exchange，提问作者Prince