using base r to extract linked list nodes

Question

I have a linked list like data,

d <- data.frame(prev=c(NA, "a", "c", "b", "e", "f", NA),
                `next`=c("a", "b", "d", "c", "f", "g", "e")
        ,stringsAsFactors = FALSE)
# > d
#   prev next.
# 1 <NA>     a
# 2    a     b
# 3    c     d
# 4    b     c
# 5    e     f
# 6    f     g
# 7 <NA>     e

if the column "prev" is NA, the column "next" is the head node. And I want to extract the linked list nodes like this:

list(c("a", "b", "c", "d"),
     c("e", "f", "g"))

I try to use while loop to do it, which I think it is not a good idea. What I want to do is using base r and vectorising function to do it.

Answer 1

Try the following option with igraph package

library(igraph)

d %>%
  mutate(prev = coalesce(prev, next.)) %>%
  graph_from_data_frame() %>%
  components() %>%
  membership() %>%
  split(names(.), .)

which gives

$`1`
[1] "a" "c" "b" "d"

$`2`
[1] "e" "f" "g"

---

If you want base R only, here is an option using dynamic programming (DP)

res <- c()
while (nrow(d)) {
  r <- na.omit(unlist(d))[1]
  repeat {
    idx <- rowSums(`dim<-`(as.matrix(d) %in% r, dim(d)), na.rm = TRUE) > 0
    if (all(!idx)) break
    r <- union(r, na.omit(unlist(subset(d, idx))))
    d <- subset(d, !idx)
  }
  res <- c(res, list(r))
}

which gives

> res
[[1]]
[1] "a" "b" "c" "d"

[[2]]
[1] "e" "f" "g"