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

Ben Bolker bolker at ufl.edu
Wed Mar 1 15:37:21 CET 2006

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

>
> Hi,
>
> In a second try I will ask this list to give me some useful pointers.

[There is a general problem with the list, because of its
volunteer nature: easy questions and questions that catch peoples'
but wasn't sufficiently clear on the distinction between "linear
lists" and lists as implemented in R to know what you needed that
an R list() couldn't do ... and I don't have Wirth on my shelf
and didn't have time to go look for a copy.]

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

cons would seem to be roughly equivalent to c() (except
that you have to make sure that the arguments are lists:
c("pine",list("fir","oak","maple")) won't work, you have
to do c(list("pine"),list("fir","oak","maple"))).
car(x) is x[1]
cdr(x) is x[-1]

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

I don't know Modula.  What determines the length of the
list you are constructing here?  It looks like this is more
or less analogous to a while() { mylist <- c(mylist,newelement) }
(although there are probably more efficient ways to do it)

Setting a list element to NULL deletes it; you can also use
negative indexing to drop one or more elements from a list.
(pages 28 and 29 of "introduction to R"
I don't know offhand if there's a simple way to modify
a list by inserting an element into the middle, bumping
up all the other indices; R deals much more with indices
than with pointer references.  If you wanted to insert
an element between items w and w+1 you could say
newlist <- c(oldlist[1:w],newelement,oldlist[(w+1):length(oldlist)])
but I appreciate that this may not be what you're looking
for.

```