What is the internal implementation of lists?
list, r
Solution
Lists are essentially just arrays of R objects (`SEXP`). Resizing causes copies of the whole data and name lookup is linear.
Alternatively, you can use environments, which use hash tables internally.
Problem
I am curious how an object of type `list` is implemented. Is it - a dynamic vector that will automatically increase its size when it is full. - a linked list where appending an item is `O(1)`, but accessing an item is `O(n)`. - a tree structure with `O(log(n))` item access. - a hashtable with `O(1)` item access. I am curious because lists can have key-value pairs that make them look like hash tables, but the elements are in order, which looks like a vector. Edit: because `length(list(runif(1e4)))` is 1, so when append element to a list, it looks like that it copy the whole list every time, that makes it very slow: But the access speed is much slower than a vector: ``` z1 <- runif(1e4) system.time({ for(i in 1:10000) z1[[1 + i]] <- 1 }) ``` outputs: ``` user system elapsed 0.060 0.000 0.062 ``` but: ``` z1 <- list(runif(1e4)) system.time({ for(i in 1:10000) z1[[1 + i]] <- 1 }) ``` outputs: ``` user system elapsed 1.31 0.00 1.31 ``` init a list with 10000 elements: ``` z1 <- as.list(runif(1e4)) system.time({ for(i in 1:10000) z1[[1 + i]] <- 1 }) ``` outputs: ``` user system elapsed 0.060 0.000 0.065 ``` For the key & value access: ``` z1 <- list() for(i in 1:10000){key <- as.character(i); z1[[key]] <- i} system.time({ for(i in 1:10000) x <- z1[["1"]] }) system.time({ for(i in 1:10000) x <- z1[["10000"]] }) ``` The output is: ``` user system elapsed 0.01 0.00 0.01 user system elapsed 1.78 0.00 1.78 ``` It's not an `O(1)` access, so it's not a hash table. My conclusion is that it's not a dynamic array since appending items will cause memory accesses every time; it's not a hashtable since access by key is not `O(1)`.