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?
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.
Edit: 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.
Best Answer
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.
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.
Deleting an item from the list can be accomplished with negative indexes.
A tree is just a list containing other lists.
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.