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

[Duncan Murdoch]

On 3/1/2006 8:09 AM, Christian Hoffmann wrote:
> 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.

They are in R as "pairlists" (see ?pairlist), and are used internally, 
but are rarely used at the R level; I'd suggest avoiding them.

One other problem with that style of programming is that there is 
(almost) no way to have a pointer or reference to an object.  (The 
"almost" refers to the fact that you can have references to 
environments, and could wrap objects in environments to make references 
to objects, but this is cumbersome and you probably want to avoid it.)


> 
> Nevertheless I want to implement an algorithm using such linear lists, 
> porting a trusted program to R (S). I need:
> 
> (from Modula/Oberon)
> 	pSC* = POINTER TO SC;
> 	SC* = RECORD	Next*: pSC; ......
> ...     END;
> 
> # generate and fill a linked list:
> VAR   p, pA, Kol: pSC;
> 	NEW( Kol);
> 	pA := Kol;
> 	while () {
> 		NEW( p );
> 		pA.Next := p;
> 		pA := p;
> 		...
> 	}
> 
> 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.

Insertions and deletions are relatively easy; the difficult part comes 
in doing the things that involve references, like your pA.Next above. 
You'll need to use vector indexing instead, e.g. you could translate the 
code above to

Kol <- list()
repeat {
    p <- new_pSC;
    Kol <- c(Kol, p)
    ...
}

and then refer to objects in the list as Kol[[i]], to the tail of the 
list as Kol[i:length(Kol)], etc.  (Note the distinction between [[ ]] 
and [ ]:  single brackets give a list, double brackets extract an 
element from the list.)  Remember that each of these makes a *copy* of 
the object; saying

x <- Kol[[2]]
x <- newvalue

has no effect on x.

Duncan Murdoch

> 
> 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