[R] linear lists, creation, insertion, deletion, traversal *someone?*

[Charles C. Berry]

Christian Hoffmann <christian.hoffmann <at> wsl.ch> writes:

> 
> Hi,
> 
> In a second try I will ask this list to give me some useful pointers.
> 
> Linear lists, as described e.g. by N.Wirth in "Algorithms and Data
> Structures", seem not to be implemented in S/R, although in lisp we have 
> cons, car, cdr.
> 
[snip description of ops on linked list]

> Mapping this list management to R's list() is possible, but may not be 
> so transparent. Insertions and deletions from a list may be more convoluted.
> 

If the linked list you are using will be large and involve lots of manipulation,
you might want to store and implement it in C. 

But if you do it in native R ...

You might use new.env(hash=TRUE) to create an environment() as the linked-list.

It would contain one object that contains the name of (serving as the pointer
to) the first node. (or it would contain NULL or FALSE if the linked-list was of
length zero.)

Each node would be a list() with two components: the value and the name of (i.e.
the pointer to) the next element. 

To add a node you would create a name that is unique (within the environment at
least), use assign() once to place the new node in the environment and once more
to rewrite the preceeding nodes pointer to contain the name of the new node.

Initialize and add data to a linked list:

> linklist <- new.env(hash=TRUE)
> assign('start',FALSE,envir=linklist)
> for (i in 1:10000 ){
+ assign(as.character(i), list( ptr=get('start',linklist), value=rnorm(1) ), 
+ envir=linklist)
+ assign('start',as.character(i), envir=linklist )
+ }
> get("501",linklist) # example of one node
$ptr
[1] "500"

$value
[1] -0.7022237

Of course, you would write a function to do those two assignments.

To delete a node you would use assign() to reset the pointer from the previous
to the succeeding node, then rm() to delete the defunct node.

> to.delete <- get("501", linklist)$ptr
> assign( "501", list(ptr = get( to.delete, linklist )$ptr, 
+ val = get("501", linklist)$val ), linklist )
> rm( list=to.delete, envir=linklist )
> get("501",linklist)
$ptr
[1] "499"

$val
[1] -0.7022237

>


> Does anybody have experience in this? I could not find any reference in
> R resources, also the Blue Book is mute here.
> 
> Thank you
> Christian