[R] Linked List in R

[Martin Morgan]

On 02/12/2011 11:08 AM, Shing Hing Man wrote:
> Hi,
>   I am trying to create a linked list in R by defining a class Node which has a instance variable Node.
> 
> setClass("Node", representation(rate="numeric",  nextNode="ANY"))
> 
> The above works. But the following gives me a warning message.
> setClass("Node", representation(rate="numeric",  nextNode="Node"))
> 
> 
>>
>> setClass("Node", representation(rate="numeric",  nextNode="ANY"))
> [1] "Node"
>> removeClass("Node")
> [1] TRUE
>>
>> setClass("Node", representation(rate="numeric",  nextNode="Node"))
> [1] "Node"
> Warning message:
> undefined slot classes in definition of "Node": nextNode(class "Node")
>>
> 
> In the case when nextNode is type Node, is it possible to get ride of the above  "undefined slot classes" warning message ?
> 
> 
> Thanks in advance for any assistance!

Hi Shing --

Not really an answer to your question, but I guess linked lists give you
constant insert / linear search. The only data type in R with constant
insert time is an environment. Environments map keys to values, with
keys being character scalars. So (untested)

setClass("Node",representation(next="character", value="ANY"))
setClass("LinkedList",
    representation(store="environment", head="character")))

environments are tricky because of their pass-by-reference semantic, and
to initialize the LinkedList class you'll want to write an initialize
method that creates a new environment for each instance

setMethod(initialize, "LinkedList",
    function(.Object, ..., store=new.env(parent=emptyenv()))
{
    callNextMethod(.Object, ..., store=store)
})

you'd then write methods on the LinkedList class to insert / delete /
etc. Likely some new concepts in there but hopefully that helps...

For the node values, creating S4 objects can be very expensive and if
you are thinking of large linked lists that are frequently updated, you
might do well either to use simple lists or vectors to represent the
node values, or to rethink whether linked lists are what you need --
they're not a very friendly R data structure.

And since the LinkedList class is based on an environment, it has
reference semantics that will confuse R users.

Martin

> 
> Shing 
> 
> 
> 
> 
> ______________________________________________
> R-help at r-project.org mailing list
> https://stat.ethz.ch/mailman/listinfo/r-help
> PLEASE do read the posting guide http://www.R-project.org/posting-guide.html
> and provide commented, minimal, self-contained, reproducible code.


-- 
Computational Biology
Fred Hutchinson Cancer Research Center
1100 Fairview Ave. N. PO Box 19024 Seattle, WA 98109

Location: M1-B861
Telephone: 206 667-2793