Data structures manage how data is stored and accessed,

while Algorithms focus on processing this data. Examples of data structures

are Array, Linked List, Tree and Heap, and examples of algorithms are Binary
Search, Quick Sort and Merge Sort.

Why to Learn DSA?

 Foundation for almost every software like GPS, Search Engines, AI

ChatBots, Gaming Apps, Databases, Web Applications, etc

 Top Companies like Google, Microsoft, Amazon, Apple, Meta and many
other heavily focus on DSA in interviews.

 Learning DSA boosts your problem-solving abilities and make you a

stronger programmer.

Data Structures is about how data can be stored in different

structures.

Algorithms is about how to solve different problems, often by

searching through and manipulating data structures.

Theory about Data Structures and Algorithms (DSA) helps us to

use large amounts of data to solve problems efficiently.

What are Data Structures?

A data structure is a way to store data.

We structure data in different ways depending on what data we

have, and what we want to do with it.

Family tree
First, let's consider an example without computers in mind, just
to get the idea.

If we want to store data about people we are related to, we use

a family tree as the data structure. We choose a family tree as
the data structure because we have information about people
we are related to and how they are related, and we want an
overview so that we can easily find a specific family member,
several generations back.

Data structures give us the possibility to manage large

amounts of data efficiently for uses such as large databases
and internet indexing services.

Data structures are essential ingredients in creating fast and

powerful algorithms. They help in managing and organizing
data, reduce complexity, and increase efficiency.

In Computer Science there are two different kinds of data

structures.

Primitive Data Structures are basic data structures provided

by programming languages to represent single values, such as
integers, floating-point numbers, characters, and booleans.

Abstract Data Structures are higher-level data structures

that are built using primitive data types and provide more
complex and specialized operations. Some common examples
of abstract data structures include arrays, linked lists, stacks,
queues, trees, and graphs.

What are Algorithms?

An algorithm is a set of step-by-step instructions to solve a

given problem or achieve a specific goal.
 Pommes Frites Recipe

A cooking recipe written on a piece of paper is an example of

an algorithm, where the goal is to make a certain dinner. The
steps needed to make a specific dinner are described exactly.

When we talk about algorithms in Computer Science, the step-

by-step instructions are written in a programming language,
and instead of food ingredients, an algorithm uses data
structures.

Algorithms are fundamental to computer programming as they

provide step-by-step instructions for executing tasks. An
efficient algorithm can help us to find the solution we are
looking for, and to transform a slow program into a faster one.

By studying algorithms, developers can write better programs.

Algorithm examples:

 Finding the fastest route in a GPS navigation system

 Navigating an airplane or a car (cruise control)
 Finding what users search for (search engine)
 Sorting, for example sorting movies by rating

The algorithms we will look at in this tutorial are designed to

solve specific problems, and are often made to work on specific
data structures. For example, the 'Bubble Sort' algorithm is
designed to sort values, and is made to work on arrays.

Data Structures together with Algorithms

Data structures and algorithms (DSA) go hand in hand. A data

structure is not worth much if you cannot search through it or
manipulate it efficiently using algorithms, and the algorithms in
this tutorial are not worth much without a data structure to
work on.

DSA is about finding efficient ways to store and retrieve data,

to perform operations on data, and to solve specific problems.

By understanding DSA, you can:

 Decide which data structure or algorithm is best for a

given situation.
 Make programs that run faster or use less memory.
 Understand how to approach complex problems and solve
them in a systematic way.

Where is Data Structures and Algorithms Needed?

Data Structures and Algorithms (DSA) are used in virtually

every software system, from operating systems to web
applications:

 For managing large amounts of data, such as in a social

network or a search engine.
 For scheduling tasks, to decide which task a computer
should do first.
 For planning routes, like in a GPS system to find the
shortest path from A to B.
 For optimizing processes, such as arranging tasks so they
can be completed as quickly as possible.
 For solving complex problems: From finding the best way
to pack a truck to making a computer 'learn' from data.
 DSA is fundamental in nearly every part of the software
world:
 Operating Systems
 Database Systems
 Web Applications
 Machine Learning
 Video Games
 Cryptographic Systems
 Data Analysis
 Search Engines
  Arrays
 An array is a data structure used to store multiple
elements.
 Arrays are used by many algorithms.

Array is a collection of items of the same variable type that are

stored at contiguous memory locations. It is one of the most
popular and simple data structures used in programming.

Basic terminologies of Array

 Array Index: In an array, elements are identified by their

indexes. Array index starts from 0.

 Array element: Elements are items stored in an array and

can be accessed by their index.

 Array Length: The length of an array is determined by the

number of elements it can contain.

Memory representation of Array

In an array, all the elements are stored in contiguous memory

locations. So, if we initialize an array, the elements will be
allocated sequentially in memory. This allows for efficient
access and manipulation of elements.

Array is a linear data structure that is a collection of data

elements of same types. Arrays are stored in contiguous
memory locations. It is a static data structure with a fixed size.
Applications of Array Data Structure:

Arrays mainly have advantages like random access and cache

friendliness over other data structures that make them useful.

Below are some applications of arrays.

 Storing and accessing data: Arrays store elements in a

specific order and allow constant-time O(1) access to any
element.

 Searching: If data in array is sorted, we can search an

item in O(log n) time. We can also find floor(), ceiling(), kth
smallest, kth largest, etc efficiently.

 Matrices: Two-dimensional arrays are used for matrices in

computations like graph algorithms and image processing.

 Implementing other data structures: Arrays are used as

the underlying data structure for implementing stacks and
queues.

 Dynamic programming: Dynamic programming algorithms

often use arrays to store intermediate results of
subproblems in order to solve a larger problem.

 Data Buffers: Arrays serve as data buffers and queues,

temporarily storing incoming data like network packets,
file streams, and database results before processing.
Advantages of Array Data Structure:

 Efficient and Fast Access: Arrays allow direct and efficient

access to any element in the collection with constant
access time, as the data is stored in contiguous memory
locations.

 Memory Efficiency: Arrays store elements in contiguous

memory, allowing efficient allocation in a single block and
reducing memory fragmentation.

 Versatility: Arrays can be used to store a wide range of

data types, including integers, floating-point numbers,
characters, and even complex data structures such as
objects and pointers.

 Compatibility with hardware: The array data structure is

compatible with most hardware architectures, making it a
versatile tool for programming in a wide range of
environments.

Disadvantages of Array Data Structure:

 Fixed Size: Arrays have a fixed size set at creation.

Expanding an array requires creating a new one and
copying elements, which is time-consuming and memory-
intensive.

 Memory Allocation Issues: Allocating large arrays can

cause memory exhaustion, leading to crashes, especially
on systems with limited resources.

 Insertion and Deletion Challenges: Adding or removing

elements requires shifting subsequent elements, making
these operations inefficient.

 Limited Data Type Support: Arrays support only elements

of the same type, limiting their use with complex data
types.

 Lack of Flexibility: Fixed size and limited type support

make arrays less adaptable than structures like linked lists
or trees.
  Need for Arrays

 Arrays are used as solutions to many problems from the

small sorting problems to more complex problems like
travelling salesperson problem. There are many data
structures other than arrays that provide efficient time
and space complexity for these problems, so what makes
using arrays better? The answer lies in the random access
lookup time.

 Arrays provide O(1) random access lookup time. That

means, accessing the 1st index of the array and the
1000th index of the array will both take the same time.
This is due to the fact that array comes with a pointer and
an offset value. The pointer points to the right location of
the memory and the offset value shows how far to look in
the said memory.

 array_name[index]

 | |

 Pointer Offset

 Therefore, in an array with 6 elements, to access the 1st

element, array is pointed towards the 0th index. Similarly,
to access the 6th element, array is pointed towards the
5th index.

Array Representation

Arrays are represented as a collection of buckets where each

bucket stores one element. These buckets are indexed from '0'
to 'n-1', where n is the size of that particular array. For
example, an array with size 10 will have buckets indexed from
0 to 9.

This indexing will be similar for the multidimensional arrays as

well. If it is a 2-dimensional array, it will have sub-buckets in
each bucket. Then it will be indexed as array name[m][n],
where m and n are the sizes of each level in the array.
As per the above illustration, following are the important points
to be considered.

 Index starts with 0.

 Array length is 9 which means it can store 9 elements.
 Each element can be accessed via its index. For example,
we can fetch an element at index 6 as 23.

Basic Operations in Arrays

The basic operations in the Arrays are insertion, deletion,

searching, display, traverse, and update. These operations are
usually performed to either modify the data in the array or to
report the status of the array.

Following are the basic operations supported by an array.

 Traverse − print all the array elements one by one.

 Insertion − Adds an element at the given index.
 Deletion − Deletes an element at the given index.
 Search − Searches an element using the given index or by
the value.
 Update − Updates an element at the given index.
 Display − Displays the contents of the array.