Linked list

A list can be defined as a collection of a finite number, or as sequence of data items known as elements. Each element of a list will have a specific data type-in the simplest scenario, all elements of a list have the same data type. In R, list implementation is essentially arrays of R objects (SEXP). The array-based implementation of lists will be discussed in the next section. To implement the list data structure, we will use environments, also known as objects in R:

# Example list with array, data.frame, matrix, and character 
> elist <- list(vec=1:4,df=data.frame(a=1:3, b=4:6),mat=matrix(1:4,    nrow=2), name="pks")
> elist[["vec"]]
[1] 1 2 3 4

In a linked list, each item holds a relative position with respect to the others. In a list, there is no requirement for contiguous memory, thus, data can have non-contiguous allocation. For example, Figure 3.6 shows the implementation of contiguous and non-contiguous memory allocation:

Figure 3.10: Memory allocation

In non...