Roll Your Own Linked List/Tree in 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) listlst[[1]] <- 1 # automagically extends the lstlst[[2]] <- 2 # ditto

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 itemslst <- vector("list", 10000)  # 10000 NULLslst[[1]] <- 1lst[[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 childtree[[2]]# right child of right child:list(4, 5)tree[[2]][[2]]

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.