在R中滾動您自己的鏈接列表/樹？

Question

我試圖環繞R編程語言的基本概念，我的頭，我發現很難由於R是着眼於統計的，而不是通用的編程。我找不到任何類似於指針/引用的東西。你將如何在R語言中實現鏈表，搜索樹等？

注：我明白，如果你實際上滾動自己自引用的數據結構中R，有可能是一個更好的方式來完成你想要完成的任務。不過，我相信一個答案會幫助我更好地理解語言的整體結構和概念。

編輯：關於馬特·斯托克韋爾的評論，這個問題的關鍵是我正在尋找編寫鏈接列表和樹乾淨，在 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課程可以學到更多結構化的方法，但是這樣做可以做到這一點。