Faster and efficient information retrieval is the primary objective of most computer programs. Data structures and algorithms help us in achieving the objective by processing and retrieving data faster. Information retrieval can easily be integrated with algorithms to answer inferential questions from data such as:

How are sales increasing over time?

What is customer's arrival distribution over time?

Out of all the customers who visit between 3:00 and 6:00 PM, how many order Asian versus Chinese?

Of all the customers visiting, how many are from the same city?

In the efficient processing of the preceding queries, especially in big data scenarios, data structures and algorithms utilized for data retrieval play a significant role. This book will introduce primary data structures such as lists, queues, and stacks, which are used for information retrieval and trade-off of different data structures. We will also introduce the data structure and algorithms evaluation approach for retrieval and processing of defined data structures.

Algorithms are evaluated based on complexity and efficiency, where complexity refers to an algorithm design which is easy to program and debug, and efficacy ensures that the algorithm is utilizing computer resources optimally. This book will focus on the efficiency part of algorithms using data structures, and the current chapter introduces the importance of data structure and the algorithms used for retrieval of data from data structures.

Moore's law in 1965 observed that the number of transistors per square inch in a dense **integrated circuit** (**IC**) had doubled every year since its invention, thus enhancing computational power per computer. He revised his forecast in 1975, stating that the number of transistors would double every 2 years, instead of every year, due to saturation:

Figure 1.1: Moore's law (Ref: data credit - Transistor count, Wikipedia)

Also, although the computational power has been increasing, problem complexity and data sources have also been increasing exponentially over the decade, enforcing the need for efficient algorithms:

Figure 1.2: Increase in size of unstructured data (Ref: Enterprise strategy group 2010)

This explosion in data from 2008 to 2015 has led to a new field of data science where people put in a lot of effort to derive insights using all kinds of datasets such as structured, semi-structured, and unstructured. Thus, to efficiently deal with data scalability, it is important to efficiently store and retrieve datasets. For example, searching for a word in a dictionary would take a long time if the data is randomly organized; thus, sorted list data structures are utilized to ensure a faster search of words. Similarly, searching for an optimal path in a city based on the input location requires data about road network, position, and so on to be stored in the form of geometries. Ideally, even a variable stored as any built-in data type such as character, integer, or float can be considered as a data structure of scalar nature. However, data structure is formally defined as a scheme of organizing related information in a computer so that it can be used efficiently.

Similarly, for algorithms, given sufficient space and time, any dataset can be stored and processed to answer questions of interest. However, selecting the correct data structure will help you save a lot of memory and computational power. For example, assigning a float to integer data type, such as the number of customers coming in a day, will require double the memory. However, in the real-world scenario, computers are constrained by computational resources and space. Thus, a solution can be stated as efficient if it is able to achieve the desired goal in the given resources and time. Thus, this could be used as a cost function to compare the performance of different data structures while designing algorithms. There are two major design constraints to be considered while selecting the data structure:

Analyze the problem to decide on the basic operation that must be supported into the selected data structure, such as inserting an item, deleting an item, and searching for an item

Evaluate the resource constraint for each operation

The data structure is selected depending on the problem scenario, for example, a case where complete data is loaded at the beginning, and there is no change/insertion in data, requires similar data structure. However, similar including deletion into data structure will make data structure implementation more complex.

### Tip

Detailed steps to download the code bundle are mentioned in the Preface of this book. Please have a look. The code bundle for the book is also hosted on GitHub at https://github.com/PacktPublishing/R-Data-Structures-and-Algorithms. We also have other code bundles from our rich catalog of books and videos available at https://github.com/PacktPublishing/. Check them out!

The **abstract data type** (**ADT**) is used to define high-level features and operations for data structure, and is required before we dig down into details of implementation of data structure. For example, before implementing a linked list, it would be good to know what we want to do with the defined linked list, such as:

I should be able to insert an item into the linked list

I should be able to delete an item from the linked list

I should be able to search an item in the linked list

I should be able to see whether the linked list is empty or not

The defined ADT will then be utilized to define the implementation strategy. We will discuss ADT for different data structures in more detail later in this book. Before getting into definitions of ADT, it's important to understand data types and their characteristics, as they will be utilized to build an ecosystem for the data structures.

Data type is a way to classify various types of data such as Boolean, integer, float, and string. To efficiently classify a dataset, the following characteristics are needed in any data type:

**Atomic**: It should define a single concept**Traceable**: It should be able to map with the same data type**Accurate**: It should be unambiguous**Clear and concise**: It should be understandable

Data types can be classified into two types:

Built-in data type

Derived data type

Data types for which a language has built-in support are known as built-in data types. For example, R supports the following data types:

Integers

Float

Boolean

Character

Data types which are obtained by integrating the built-in data types with associated operations such as insertion, deletion, sorting, merging, and so on are referred to as derived data types, such as:

List

Array

Stack

Queue

Derived data types or data structures are studied on two components:

Abstract data type or mathematical/logical models

Programming implementation

ADT is the realization of a data type in software. In ADT, we usually look into high-level features and operations used by users for a data structure, but do not know how these features run in the background. For example, say a user using banking software with search functionality is searching for the transaction history of Mr. Smith, using the search feature of the software. The user does not have any idea about the operations performed, or the implementation details of the data structures. Thus, the behavior of ADT is managed by input and output only:

Figure 1.3: Framework for ADT

Thus, ADT does not know how the data type is implemented, as these details are hidden by the user and protected from outside access, a concept referred to as encapsulation. A data structure is the implementation part of ADT, which can be implemented in any programming language. ADT can be achieved by multiple implementation strategies, as shown in *Figure 1.4*:

Figure 1.4: Illustration of stack and queue implementation using array with integer data type

The abstraction provided by ADT helps to manage programming complexity. The ADT is also referred to as logical form, as it decides the type and operations required for implementation. The ADT is implemented by using a particular type of data structure. The data structure used to implement ADT is referred to as the physical form of data type, as it manages storage using the implementation subroutine.

Problem can be defined as the task to be performed. The execution of the task to be performed can be divided primarily into two components:

Data

Algorithm

However, there could be other controlling factors which could affect your approach development, such as problem constraints, resource constraints, computation time allowed, and so on.

The data component of the problem represents the information we are dealing with, such as numbers, text, files, and so on. For example, let's assume we want to maintain the company employee records, which include the employee name and their associated work details. This data needs to be maintained and updated regularly.

The algorithm part of a problem represents more of implementation details. It entails how we are going to manage the current data. Depending on the data and problem requirements, we select the data structure. Depending on the data structure, we have to define the algorithm to manage the dataset. For example, we can store the company employees dataset into a linked list or dictionary. Based on the defined data structure to store data approach for searching, insertion, and deletion and so on operations performed on data structure changes which is control by algorithms and implemented as program. Thus, we could state that a program is the step-by-step instructions given to a computer to do some operations:

Program = f(Algorithm, Data Structure)

To summarize, we could state that a program is the group of step-by-step instructions to solve a defined problem using the algorithm selected considering all problems and resource constraints. This book will use program representations using R to demonstrate the implementation of different data structures and algorithms.

R is a statistical programming language designed and created by Ross Ihaka and Robert Gentleman. It is a derivative of the S language created at the AT&T Bell laboratories. Apart from statistical analysis, R also supports powerful visualizations. It is open source, freely distributed under a **General Public License** (**GPL**). **Comprehensive R Archive Network** (**CRAN**) is an ever-growing repository with more than 8,400 packages, which can be freely installed and used for various kinds of analysis.

R is a high-level language based on interpretations and intuitive syntax. It runs on system's or server's active memory (RAM) and stores all files, functions, and derived results in its environment as objects. The architecture utilized in R computation is shown in *Figure 1.5:*

Figure 1.5: Illustrate architecture of R in local/server mode

R can be installed on any operating system, such as Windows, Mac OS X, and Linux. The installation files of the most recent version can be downloaded from any one of the mirror sites of CRAN: https://cran.r-project.org/. It is available under both 32-bit and 64-bit architectures.

The installation of `r-base-dev`

is also highly recommended as it has many built-in functions. It also enables us to install and compile new R packages directly from the R console using the `install.packages()`

command.

Upon installation, R can be called from program files, desktop shortcut, or from the command line. With default settings, the R console looks as follows:

Figure 1.6: The R console in which one can start coding and evaluate results instantly

R can also be used as a kernel within Jupyter Notebook. Jupyter Notebook is a web-based application that allows you to combine documentation, output, and code. Jupyter can be installed using `pip`

:

**pip3 install -upgrade pip
pip3 install jupyter**

To start Jupyter Notebook, open a shell/terminal and run this command to start the Jupyter Notebook interface in your browser:

**jupyter notebook**

To start a new R Notebook, click on right hand side New tab and select **R** kernel as shown in Figure 1.7. **R** kernel does not come as default in Jupyter Notebook with Python as prerequisite. Anaconda distribution is recommended to install python and Jupyter and can be downloaded from https://www.continuum.io/downloads. R essentials can be installed using below command.

**conda install -c r r-essentials **

Figure 1.7: Jupyter Notebook for creating R notebooks

Once notebook is opened, you could start organizing your code into cells. As R does not require formal compilation, and executes codes on runtime, one can start coding and evaluate instant results. The console view can be modified using some options under the **Windows** tab. However, it is highly recommended to use an **Integrated Development Environment **(**IDE**), which would provide a powerful and productive user interface for R. One such widely used IDE is RStudio, which is free and open source. It comes with its own server (RStudio Server Pro) too. The interface of RStudio is as seen in the following screenshot:

Figure 1.8: RStudio, a widely used IDE for R

R supports multiple types of data, which can be organized by dimensions and content type (homogeneous or heterogeneous), as shown in Table 1.1:

Table 1.1 Basic data structure in R

Homogeneous data structure is one which consists of the same content type, whereas heterogeneous data structure supports multiple content types. All other data structures, such as data tables, can be derived using these foundational data structures. Data types and their properties will be covered in detail in Chapter 3, *Linked Lists*.

The syntax of operators in R is very similar to other programming languages. The following is a list of operators along with their explanations.

The following table defines the various arithmetic operators:

Table 1.2 Basic arithmetic operators in R

The following table defines the various logical operators:

Table 1.3 Basic logical operators in R

An example of assigned in R is shown below. Initially a column vector `V`

is assigned followed by operations on column vector such as addition, subtraction, square root and log. Any operation applied on column vector is element-wise operation.

> V <- c(1,2,3,4,5,6) ## Assigning a vector V> V[1] 1 2 3 4 5 6> V+10 ## Adding each element in vector V with 10[1] 11 12 13 14 15 16> V-1 ## Subtracting each element in vector V with 1[1] 0 1 2 3 4 5> sqrt(V) ## Performing square root operation on each element in vector V[1] 1.000000 1.414214 1.732051 2.000000 2.236068 2.449490> V1 <- log(V) ## Storing log transformed of vector V as V1> V1[1] 0.0000000 0.6931472 1.0986123 1.3862944 1.6094379 1.7917595

Control structures such as loops and conditions form an integral part of any programming language, and R supports them with much intuitive syntax.

The syntax for the `if`

condition is as follows:

if (test expression) { Statement upon condition is true }

If the test expression is `true`

, the statement is executed. If the statement is `false`

, nothing happens.

In the following example, an atomic vector `x`

is defined, and it is subjected to two conditions separately, that is, whether `x`

is greater than `5`

or less than `5`

. If either of the conditions gets satisfied, the value `x`

gets printed in the console following the corresponding `if`

statement:

> x <- 10> if (x < 5) print(x)> if (x > 5) print(x)[1] 10

The syntax for the `if...else`

condition is as follows:

if(test expression) { Statement upon condition is true } else { Statement upon condition is false }

In this scenario, if the condition in the test expression is `true`

, the statement under the `if`

condition is executed, otherwise the statement under the `else`

condition is executed.

The following is an example in which we define an atomic vector `x`

with a value `10`

. Then, we verify whether `x,`

when divided by `2,`

returns `1`

(R reads `1`

as a Boolean True). If it is True, the value `x`

gets printed as an odd number, else as an even number:

> x=10> if (x %% 2)+ {+ print(paste0(x, " :odd number"))+ } else {+ print(paste0(x, " :even number"))+ }[1] "10 :even number"

An `ifelse()`

function is a condition used primarily for vectors, and it is an equivalent form of the `if...else`

statement. Here, the conditional function is applied to each element in the vector individually. Hence, the input to this function is a vector, and the output obtained is also a vector. The following is the syntax of the `ifelse`

condition:

ifelse (test expression, statement upon condition is true, statement upon condition is false)

In this function, the primary input is a test expression which must provide a logical output. If the condition is `true`

, the subsequent statement is executed, else the last statement is executed.

The following is example in which a vector `x`

is defined with integer values from 1 to 7. Then, a condition is applied on each element in vector `x`

to determine whether the element is an odd number or an even number:

> x <- 1:6> ifelse(x %% 2, paste0(x, " :odd number"), paste0(x, " :even number"))[1] "1 :odd number" "2 :even number" "3 :odd number"[4] "4 :even number" "5 :odd number" "6 :even number"

A `for`

loop is primarily used to iterate a statement over a vector of values in a given sequence. The vector can be of any type, that is, numeric, character, Boolean, or complex. For every iteration, the statement is executed.

The following is the syntax of the `for`

loop:

for(x in sequence vector) { Statement to be iterated }

The loop continues till all the elements in the vector get exhausted as per the given sequence.

The following example details a `for`

loop. Here, we assign a vector `x,`

and each element in vector `x`

is printed in the console using a `for`

loop:

> x <- c("John", "Mary", "Paul", "Victoria")> for (i in seq(x)) {+ print(x[i])+ }[1] "John"[1] "Mary"[1] "Paul"[1] "Victoria"

The nested `for`

loop can be defined as a set of multiple `for`

loops within each `for`

loop as shown here:

for( x in sequence vector) { First statement to be iterated for(y in sequence vector) { Second statement to be iterated ......... } }

In a nested `for`

loop, each subsequent `for`

loop is iterated for all the possible times based on the sequence vector in the previous `for`

loop. This can be explained using the following example, in which we define mat as a matrix (3x3), and our desired objective is to obtain a series of summations which will end up with the total sum of all the values within the matrix. Firstly, we initialize `sum`

to `0`

, and then subsequently, `sum`

gets updated by adding itself to all the elements in the matrix in a sequence. The sequence is defined by the nested `for`

loop, wherein for each row in a matrix, each of the values in all the columns gets added to sum:

> mat <- matrix(1:9, ncol = 3)> sum <- 0> for (i in seq(nrow(mat)))+ {+ for (j in seq(ncol(mat)))+ {+ sum <- sum + mat[i, j]+ print(sum)+ }+ }[1] 1[1] 5[1] 12[1] 14[1] 19[1] 27[1] 30[1] 36[1] 45

In R, `while`

loops are iterative loops with a specific condition which needs to be satisfied. The syntax of the `while`

loop is as follows:

while (test expression) { Statement upon condition is true (iteratively) }

Let's understand the `while`

loop in detail with an example. Here, an object `i`

is initialized to `1`

. The test expression which needs to be satisfied for every iteration is `i<10`

. Since `i`

= `1`

, the condition is TRUE, and the statement within the `while`

loop is evaluated. According to the statement, `i`

is printed on the console, and then increased by `1`

unit. Now `i`

increments to `2,`

and once again, the test expression, whether the condition (`i < 10`

) is true or false, is checked. If TRUE, the statement is again evaluated. The loop continues till the condition becomes false, which, in our case, will happen when `i`

increments to `10`

. Here, incrementing `i`

becomes very critical, without which the loop can turn into infinite iterations:

> i <- 1> while (i < 10)+ {+ print(i)+ i <- i + 1+ }[1] 1[1] 2[1] 3[1] 4[1] 5[1] 6[1] 7[1] 8[1] 9

In R, the loops can be altered using `break`

or `next`

statements. This helps in inducing other conditions required within the statement inside the loop.

The syntax for the Break statement is `break`

. It is used to terminate a loop and stop the remaining iterations. If a `break`

statement is provided within a nested loop, then the innermost loop within which the `break`

statement is mentioned gets terminated, and iterations of the outer loops are not affected.

The following is an example in which a `for`

loop is terminated when i reaches the value `8`

:

> for (i in 1:30)+ {+ if (i < 8)+ {+ print(paste0("Current value is ",i))+ } else {+ print(paste0("Current value is ",i," and the loop breaks"))+ break+ }+ }[1] "Current value is 1"[1] "Current value is 2"[1] "Current value is 3"[1] "Current value is 4"[1] "Current value is 5"[1] "Current value is 6"[1] "Current value is 7"[1] "Current value is 8 and the loop breaks"

The syntax for a Next statement is `next`

. The `next`

statements are used to skip intermediate iterations within a loop based on a condition. Once the condition for the `next`

statement is met, all the subsequent operations within the loop get terminated, and the next iteration begins.

This can be further explained using an example in which we print only odd numbers based on a condition that the printed number, when divided by `2`

, leaves the remainder `1`

.

> for (i in 1:10)+ {+ if (i %% 2)+ {+ print(paste0(i, " is an odd number."))+ } else {+ next+ }+ }[1] "1 is an odd number."[1] "3 is an odd number."[1] "5 is an odd number."[1] "7 is an odd number."[1] "9 is an odd number."

The `repeat`

loop is an infinite loop which iterates multiple times without any inherent condition. Hence, it becomes mandatory for the user to explicitly mention the terminating condition, and use a `break`

statement to terminate the loop.

The following is the syntax for a `repeat`

statement:

repeat { Statement to iterate along with explicit terminate condition including break statement }

In the current example, `i`

is initialized to `1`

. Then, a `for`

loop iterates, within which an object cube is evaluated and verified using a condition whether the cube is greater than `729`

or not. Simultaneously, `i`

is incremented by `1`

unit. Once the condition is met, the `for`

loop is terminated using a `break`

statement:

> i <- 1> repeat+ {+ cube <- i ** 3+ i <- i + 1+ if (cube < 729)+ {+ print(paste0(cube, " is less than 729. Let's remain in the loop."))+ } else {+ print(paste0(cube, " is greater than or equal to 729. Let's exit the loop."))+ break+ }+ }[1] "1 is less than 729. Let's remain in the loop."[1] "8 is less than 729. Let's remain in the loop."[1] "27 is less than 729. Let's remain in the loop."[1] "64 is less than 729. Let's remain in the loop."[1] "125 is less than 729. Let's remain in the loop."[1] "216 is less than 729. Let's remain in the loop."[1] "343 is less than 729. Let's remain in the loop."[1] "512 is less than 729. Let's remain in the loop."[1] "729 is greater than 729. Let's exit the loop."

R is primarily a functional language at its core. In R, functions are treated just like any other data types, and are considered as first-class citizens. The following example shows that R considers everything as a function call.

Here, the operator `+`

is a function in itself:

> 10+20[1] 30> "+"(10,20)[1] 30

Here, the operator `^`

is also a function in itself:

> 4^2[1] 16> "^"(4,2)[1] 16

Now, let's dive deep into functional concepts, which are crucial and widely used by R programmers.

Vectorized functions are among the most popular functional concepts which enable the programmer to execute functions at an individual element level for a given vector. This vector can also be a part of dataframe, matrix, or a list. Let's understand this in detail using the following example, in which we would like to have an operation on each element in a given vector `V_in`

. The operation is to square each element within the vector and output it as vector `V_out`

. We will implement them using three approaches as follows:

**Approach 1**: Here, the operations will be performed at the element level using a `for`

loop. This is the most primitive of all the three approaches in which vector allocation is being performed using the style of S language:

> V_in <- 1:100000 ## Input Vector> V_out <- c() ## Output Vector> for(i in V_in) ## For loop on Input vector+ {+ V_out <- c(V_out,i^2) ## Storing on Output vector+ }

**Approach 2**: Here, the vectorized functional concept will be used to obtain the same objective. The loops in vectorized programming are implemented in C language, and hence, perform much faster than `for`

loops implemented in R (*Approach 1*). The time elapsed to run this operation is instantaneous:

> V_in <- 1:100000 ## Input Vector> V_out <- V_in^2 ## Output Vector

**Approach 3**: Here, higher order functions (or nested functions) are used to obtain the same objective. As functions are considered first class citizens in R, these can be called as an argument within another function. The widely used nested functions are in the apply family. The following table provides a summary of the various types of functions within the apply family:

Table 1.4 Various types of functions in the apply family

Now, lets' evaluate the first class function through examples. An `apply`

function can be applied to a dataframe, matrix, or array. Let's illustrate it using a matrix:

> x <- cbind(x1 = 7, x2 = c(7:1, 2:5))> col.sums <- apply(x, 2, sum)> row.sums <- apply(x, 1, sum)

The `lapply`

is a first class function to be applied to a vector, list, or variables in a dataframe or matrix. An example of `lapply`

is shown below:

> x <- list(x1 = 7:1, x2 = c(7:1, 2:5))> lapply(x, mean)

The use of the `sapply`

function for a vector input using customized function is shown below:

> V_in <- 1:100000 ## Input Vector> V_out <- sapply(V_in,function(x) x^2) ## Output Vector

The function `mapply`

is a multivariate `sapply`

. The `mapply`

function is the first input, followed by input parameters as shown below:

**mapply(FUN, ..., MoreArgs = NULL, SIMPLIFY = T, USE.NAMES = T)**

An example of `mapply`

to replicated two vector can be obtained as:

**> mapply(rep, 1:6, 6:1)**

The function call `rep`

function in R with input from 1 to 6 and is replicated as 6 to 1 using the second dimension of the `mapply`

function. The `tapply`

applies a function to each cell of the ragged array. For example, let's create a list with a multiple array:

The output is a relationship between two vectors with position as a value. The function `rapply`

is a recursive function for lapply as shown below:

> X <- list(list(a = pi, b = list(c = 1:1)), d = "a test")> rapply(X, sqrt, classes = "numeric", how = "replace")

The function applies sqrt to all numeric classes in the list and replace it with new values.

Can you think of ways in which we can extract a few attributes (columns) and observations (rows) based on a certain condition?

Dataset - El Nino dataset from UCI KDD (https://kdd.ics.uci.edu/databases/el_nino/el_nino.html)

Filter for latitude and longitude with humidity > 88% and air temperature < 25.5 degree Celsius

10,000 iterations for evaluating each expression

Can we add multiple arguments within a function in the

`apply`

family? If yes, what is the syntax for assigning multiple arguments?A general notion states that

`for`

loops are slower than the`apply`

functions. Is it true or false? If false, what are the conditions in which the notion gets negated?Define ADT for calculating the area of any geometrical object, such as a circle, square, and so on.

Computational power has been continuously increasing in the last couple of decades, and so does the amount of data captured by different industries. To cope with data size, faster and efficient information retrieval is an eminent requirement.

In this chapter, you were introduced to ADT and data structure. ADT is used to define high-level features and operations representing different data structures, and algorithms are used to implement ADT. A data type should be atomic, traceable, accurate, and have clear and concise characteristic properties for efficiency along with unambiguity. You also learned the basics of R, including data type, conditional loops, control structure, and first class functions.

The computational time taken by an algorithm is most important objective considered while selecting data structures and algorithms. The next chapter will provide the fundamentals for the analysis of algorithms.