What is Data Structure: Need, Types & Classification

Imagine a library without a filing system. Finding a specific book would be a nightmare. Data
structures are like the filing system for computer programs, organizing information for
efficient storage, retrieval, and manipulation. This article dives into the world of data
structures, explaining what they are, why they are important, and the different types you
will encounter.

A data structure is a collection of data values and the relationships between them. Data
structures allow programs to store and process data effectively. There are many different
data structures, each with its own advantages and disadvantages. Some of the most
common data structures are arrays, lists, trees, and graphs.

What is a Data Structure?

A data structure is a specialized format for organizing, storing, and accessing data within a
computer’s memory. Different data structures excel at different tasks. An array, for instance,
is ideal for storing a fixed-size collection of similar items, like a list of student grades. On the
other hand, a linked list is more flexible, enabling you to add or remove items dynamically,
making it perfect for tasks like managing a to-do list.

These algorithms are referred to as Abstract data types. Abstract data types are nothing but
a set of rules.

Why are Data Structures Important?

Data structures are the foundation of efficient programs. They play a crucial role in:

• Performance: Choosing the right data structure significantly impacts how quickly
your program can access and process information. For example, searching an
unsorted list takes much longer than searching a sorted array.

• Memory Management: Data structures help optimize memory usage, preventing

wasted space and improving program efficiency.

• Code Reusability: Well-defined data structures can be reused across different parts
of your program or even other programs, saving development time and promoting
consistency.

Types of Data Structure 3

 • Linear Data Structures: Items are arranged sequentially, like beads on a string.
Examples include:

1. Arrays: Store a fixed-size collection of elements of the same data type, accessed
using an index (position). They are efficient for random access but not ideal for
frequent insertions or deletions in the middle.

2. Linked Lists: Offer more flexibility than arrays, as elements (nodes) are not stored
contiguously in memory. Each node contains data and a reference (pointer) to the
next node in the list. This allows for dynamic insertion and deletion, but random
access is slower.

3. Stacks: Follow a Last-In-First-Out (LIFO) principle, similar to a stack of plates. The

most recently added element is accessed and removed first (like popping a plate off
the top). Stacks are useful for implementing undo/redo functionality or keeping track
of function calls.

4. Queues: Function on a First-In-First-Out (FIFO) basis, like a line at a coffee shop. The
added element is the first to be retrieved (think people leaving the line one by one).
Queues are often used to manage tasks or process requests in a specific order.

• Non-Linear Data Structures: Relationships between elements are not strictly linear.
They provide a more flexible way to organize complex data. Here are some common
examples:

1. Trees: Hierarchical structures with a root node, child nodes, and potentially sub-
trees. Binary trees have a maximum of two child nodes per parent, while N-ary trees
can have any number of children. Trees efficiently search and sort data, especially
when dealing with hierarchical relationships. Binary Search Trees (BSTs) are a specific
type of binary tree that keeps elements sorted for faster searching.

2. Graphs: Consist of nodes (vertices) connected by edges. Graphs model relationships

between objects, like social networks or transportation systems.

There are other 2 types of Data Structure :

• Primitive Data Structure

• Non – Primitive Data Structure

Primitive Data Structure –

Primitive Data Structures directly operate according to the machine instructions. These are
the primitive data types. Data types like int, char, float, double, and pointer are primitive
data structures that can hold a single value.

Non – Primitive Data Structure –

Non-primitive data structures are complex data structures that are derived from primitive
data structures. Non – Primitive data types are further divided into two categories.

• Linear Data Structure

• Non – Linear Data Structure

Linear Data Structure –

Linear Data Structure consists of data elements arranged in a sequential manner where
every element is connected to its previous and next elements. This connection helps to
traverse a linear arrangement in a single level and in a single run. Such data structures are
easy to implement as memory is additionally sequential. Some examples of Linear Data
Structure are List, Queue, Stack, Array etc.

Types of Linear Data Structure –

1] Arrays –

An array is a collection of similar data elements stored at contiguous memory locations. It is

the simplest data structure where each data element can be accessed directly by only using
its index number.

2] Linked List –

A linked list is a linear data structure that is used to maintain a list-like structure in the
computer memory. It is a group of nodes that are not stored at contiguous locations. Each
node of the list is linked to its adjacent node with the help of pointers.

3] Stack –

Stack is a linear data structure that follows a specific order during which the operations are
performed. The order could be FILO (First In Last Out) or LIFO (Last In First Out).

The basic operations performed in stack are as follows :

• Push – Adds an item within the stack.

• Pop – Deletes or removes an item from the stack.

• Top – Returns the topmost element of the stack.

 • IsEmpty – Returns true if the stack is empty.

4] Queue –

Queue is a linear data structure in which elements can be inserted from only one end which
is known as rear and deleted from another end known as front. It follows the FIFO (First In
First Out) order.

• Deque – Adds an element to the queue.

• Enqueue – Deletes or removes an element from the queue.

• IsFull – Returns true if the queue is full.

• IsEmpty – Returns true if the queue is empty.

Non-Linear Data Structure –

Non-linear Data Structures do not have any set sequence of connecting all its elements and
every element can have multiple paths to attach to other elements. Such data structures
support multi-level storage and sometimes can’t be traversed in a single run. Such data
structures aren’t easy to implement but are more efficient in utilizing memory. Some
examples of non-linear data structures are Tree, BST, Graphs etc.

Types of Non-Linear Data Structure

1] Tree –

A tree is a multilevel data structure defined as a set of nodes. The topmost node is named
root node while the bottom most nodes are called leaf nodes. Each node has only one
parent but can have multiple children.

Types of Trees in Data structure

 • General Tree

• Binary Tree

• Binary Search Tree

• AVL Tree

• Red Black Tree

• N-ary Tree

2] Graph

A graph is a pictorial representation of a set of objects connected by links known as edges.

The interconnected nodes are represented by points named vertices, and the links that
connect the vertices are called edges.

Types of Graph

• Finite Graph

• Infinite Graph

• Trivial Graph

• Simple Graph

• Multi Graph

• Null Graph

• Complete Graph

• Pseudo Graph

• Regular Graph

• Bipartite Graph

• Labeled Graph

• Diggraph Graph

• Subgraph

• Connected or Disconnected Graph

• Cyclic Graph

• Vertex Labelled Graph

• Directed Acyclic Graph

A graph is a pair of sets (V, E), where V is the set of vertices and E is the set of edges.

Classification of Data Structure

Data Structure can be further classified as

• Static Data Structure

• Dynamic Data Structure

Static Data Structure

Static Data Structures are data structures where the size is allocated at the compile time.
Hence, the maximum size is fixed and cannot be changed.

Dynamic Data Structure

Dynamic Data Structures are data structures where the size is allocated at the run time.
Hence, the maximum size is flexible and can be changed as per requirement.

Operations on different Data Structure:

There are different types of operations that can be performed for the manipulation
of data in every data structure. Some operations are explained and illustrated
below:

• Traversing: Traversing a Data Structure means to visit the element stored

in it. It visits data in a systematic manner. This can be done with any type
of DS.

• Searching: Searching means to find a particular element in the given

data-structure. It is considered as successful when the required element is
found. Searching is the operation which we can performed on data-
structures like array, linkedlist, tree, graph, etc.

• Insertion: It is the operation which we apply on all the data-structures.

Insertion means to add an element in the given data structure. The
operation of insertion is successful when the required element is added to
the required data-structure. It is unsuccessful in some cases when the size
of the data structure is full and when there is no space in the data-structure
to add any additional element. The insertion has the same name as an
insertion in the data-structure as an array, linked-list, graph, tree. In stack,
this operation is called Push. In the queue, this operation is called Enqueue.
• Deletion: It is the operation which we apply on all the data-structures.
Deletion means to delete an element in the given data structure. The
operation of deletion is successful when the required element is deleted
from the data structure. The deletion has the Advantages of same name as
a deletion in the data- structure as an array, linked-list, graph, tree, etc. In
stack, this operation is called Pop. In Queue this operation is called
Dequeue.

• Create: It reserves memory for program elements by declaring them. The

creation of data structure can be done during o Compile-time o Run-time.

• Selection: It selects specific data from present data. You can select any
specific data by giving condition in loop.
 • Update: It updates the data in the data structure. You can also update any
specific data by giving some condition in loop like select approach.

• Sort: Sorting data in a particular order (ascending or descending). We can

take the help of many sorting algorithms to sort data in less time. Example:
bubble sort which takes O (n^2) time to sort data. There are many
algorithms present like merge sort, insertion sort, selection sort, quick sort,
etc.

• Merge: Merging data of two different orders in a specific order may ascend
or descend. We use merge sort to merge sort data.

• Split Data: Dividing data into different sub-parts to make the process
complete in less time.
Data Structure –

1. Data structures allow storing the information on hard disks.

2. An appropriate choice of ADT (Abstract Data Type) makes the program more
efficient.

3. Data Structures are necessary for designing efficient algorithms.

4. It provides reusability and abstraction.

5. Using appropriate data structures can help programmers save a good amount of time
while performing operations such as storage, retrieval, or processing of data.

6. Manipulation of large amounts of data is easier.

Data Structure Applications

• Organization of data in a computer’s memory

• Representation of information in databases

• Algorithms that search through data (such as a search engine)

• Algorithms that manipulate data (such as a word processor)

• Algorithms that analyse data (such as a data miner)

• Algorithms that generate data (such as a random number generator)

• Algorithms that compress and decompress data (such as a zip utility)

• Algorithms that encrypt and decrypt data (such as a security system)

• Software that manages files and directories (such as a file manager)

• Software that renders graphics (such as a web browser or 3D rendering software)

Algorithm
What is an Algorithm? Algorithm Basics
The word Algorithm means” A set of finite rules or instructions to be followed in
calculations or other problem-solving operations” or” A procedure for solving a
mathematical problem in a finite number of steps that frequently involves
recursive operations”. Therefore, Algorithm refers to a sequence of finite steps
to solve a particular problem.
Algorithms can be simple and complex depending on what you want to achieve.

It can be understood by taking the example of cooking a new recipe. To cook a new
recipe, one reads the instructions and steps and executes them one by one, in the
given sequence. The result thus obtained is the new dish is coo ed perfectly. Every
time you use your phone, computer, laptop or calculator you are using Algorithms.
Similarly, algorithms help to do a task programming to get the expected output.
The Algorithm designed is language-independent, i.e. they are just plain
instructions that can be implemented in any language, and yet the output will be
the same, as expected.
What is the need for algorithms?
Algorithms are necessary for solving complex problems efficiently and effectively.
1. They help to automate processes and make them more reliable, faster and
easier to perform.
2. Algorithms also enable computers to perform tasks that would be difficult
or impossible for humans to do manually.

3. They are used in various field such as mathematics, computer science,

engineering, finance and 22many others to optimize cases, analyse data,
make predictions and provide solutions to problems.

What are the characteristics of an Algorithm?

As one would not follow any written instructions to cook the recipe, but only the
standard one. Similarly, not all written instructions for programming is an
algorithm. In order for some instructions to be an algorithm, it must have the
following characteristics:

• Clear and Unambiguous: The algorithm should be clear and unambiguous.

Each of its steps should be clear in all aspects and must lead to only one
meaning.

• Well-Defined Inputs: If an algorithm says to take inputs, it should be

welldefined inputs. It may or may not take input.

• Well-Defined Outputs: The algorithm must clearly define what output will
be yielded and it should be well-defined as well. It should produce at least
1 output.

• Feasible: The algorithm must be simple, generic, and practical, such that it
can be executed with the available resources. It must not contain some
future technology or anything.

• Language Independent: The Algorithm designed must be language-

independent,
i.e. it must be just plain instructions that can be implemented in any
language, and yet the output will be the same, as expected.

• Input: An algorithm has zero or more inputs. Each that contains a

fundamental operator must accept zero or more inputs.

• Output: An algorithm produces at least one output. Every instruction that

contains a fundamental operator must accept zero or more inputs.

• Definiteness: All instructions in an algorithm must be unambiguous,

precise, and easy to interpret. By referring to any of the instructions in an
algorithm one
can clearly understand what is to be done. Every fundamental operator in
instruction must be defined without any ambiguity.
 • Finiteness: An algorithm must terminate after a finite number of steps in all
test cases. Every instruction which contains a fundamental operator must
be terminated within a finite amount of time. Infinite loops or recursive
functions without base conditions do not possess finiteness.

• Effectiveness: An algorithm must be developed by using very basic, simple,

and feasible operations so that one can trace it out by using just paper and
pencil.
Properties of Algorithm:

• It should terminate after a finite time.  It should produce at least one

output.
• It should take zero or more input.
• It should be deterministic means giving the same output for the same input
case.
• Every step in the algorithm must be effective i.e. every step should do some
work.
Advantages of Algorithms:

• It is easy to understand.
• An algorithm is a step-wise representation of a solution to a given problem.
• In Algorithm the problem is broken down into smaller pieces or steps hence,
it is easier for the programmer to convert it into an actual program.
Disadvantages of Algorithms:

• Writing an algorithm takes a long time so it is time-consuming.

• Understanding complex logic through algorithms can be very difficult.
• Branching and Looping statements are difficult to show in Algorithms.
How to Design an Algorithm?
In order to write an algorithm, the following things are needed as a pre-requisite:
1. The problem that is to be solved by this algorithm i.e. clear problem definition.
2. The constraints of the problem must be considered while solving the problem.
3. The input to be taken to solve the problem.
4. The output to be expected when the problem is solved.
5. The solution to this problem, is within the given constraints.

Sub Algorithm :-
A sub-algorithm is an independent, smaller algorithm used as a component
within a larger, more complex algorithm or program to perform a specific, well-
defined task.
Key Concepts
• Modularization: The primary purpose of a sub-algorithm is to break a complex
problem into smaller, manageable sub-problems, a strategy known as "divide
and conquer".
• Reusability: A sub-algorithm is designed to be self-contained so that it can be
called multiple times within the same main algorithm or reused in entirely
different programs, avoiding code duplication.
• Encapsulation: The main algorithm doesn't need to know the specific internal
implementation details of the sub-algorithm; it only needs to know what task it
performs and how to interact with it (e.g., what parameters to pass and what
result to expect).
• Maintainability: By isolating functionality into separate modules, it becomes
easier to test, debug, and correct individual parts of the larger system without
affecting other components.

Common Types
In programming languages, sub-algorithms are typically implemented as
functions or procedures (sometimes referred to as methods or subroutines).
• Functions: Execute a set of instructions and return a single value to the calling
algorithm. They are useful for calculations (e.g., a function to calculate the sign
of a number).
• Procedures: Group a set of instructions that perform a task without returning a
specific value to the calling algorithm (e.g., a procedure to print a message to
the console).

Example
In a larger algorithm designed to find the median value in a list of numbers, a
sorting algorithm (like Bubble Sort or Merge Sort) would be used as a sub-
algorithm. The main algorithm calls the sorting sub-algorithm to arrange the
data efficiently, and once sorted, the main algorithm proceeds to find the
middle element

Asymptotic Notations for Analysis of Algorithms

We have discussed Asymptotic Analysis, and Worst, Average, and Best Cases of Algorithms.
The main idea of asymptotic analysis is to have a measure of the efficiency of algorithms
that don't depend on machine-specific constants and don't require algorithms to be
implemented and time taken by programs to be compared. Asymptotic notations are
mathematical tools to represent the time complexity of algorithms for asymptotic analysis.

Asymptotic Notations:

• Asymptotic Notations are mathematical tools used to analyze the performance of

algorithms by understanding how their efficiency changes as the input size grows.

• These notations provide a concise way to express the behavior of an algorithm's time
or space complexity as the input size approaches infinity.

• Rather than comparing algorithms directly, asymptotic analysis focuses on

understanding the relative growth rates of algorithms' complexities.
 • It enables comparisons of algorithms' efficiency by abstracting away machine-specific
constants and implementation details, focusing instead on fundamental trends.

• Asymptotic analysis allows for the comparison of algorithms' space and time
complexities by examining their performance characteristics as the input size varies.

• By using asymptotic notations, such as Big O, Big Omega, and Big Theta, we can
categorize algorithms based on their worst-case, best-case, or average-case time or
space complexities, providing valuable insights into their efficiency.

There are mainly three asymptotic notations:

1. Big-O Notation (O-notation)

2. Omega Notation (Ω-notation)

3. Theta Notation (Θ-notation)

1. Theta Notation (Θ-Notation):

Theta notation encloses the function from above and below. Since it represents the upper
and the lower bound of the running time of an algorithm, it is used for analyzing the
average-case complexity of an algorithm.

.Theta (Average Case) You add the running times for each possible input combination and
take the average in the average case.

Let g and f be the function from the set of natural numbers to itself. The function f is said to
be Θ(g), if there are constants c1, c2 > 0 and a natural number n0 such that c1* g(n) ≤ f(n) ≤
c2 * g(n) for all n ≥ n0

Theta notation

2. Big-O Notation (O-notation):

Big-O notation represents the upper bound of the running time of an algorithm. Therefore, it
gives the worst-case complexity of an algorithm.

.It is the most widely used notation for Asymptotic analysis.

.It specifies the upper bound of a function.
.The maximum time required by an algorithm or the worst-case time complexity.
.It returns the highest possible output value(big-O) for a given input.
.Big-O(Worst Case) It is defined as the condition that allows an algorithm to complete
statement execution in the longest amount of time possible.
If f(n) describes the running time of an algorithm, f(n) is O(g(n)) if there exist a positive
constant C and n0 such that, 0 ≤ f(n) ≤ cg(n) for all n ≥ n0

It returns the highest possible output value (big-O)for a given input.

The execution time serves as an upper bound on the algorithm's time complexity.

If we use Θ notation to represent the time complexity of Insertion sort, we have to use two
statements for best and worst cases:

• The worst-case time complexity of Insertion Sort is Θ(n2).

• The best case time complexity of Insertion Sort is Θ(n).

The Big-O notation is useful when we only have an upper bound on the time complexity of
an algorithm. Many times we easily find an upper bound by simply looking at the
algorithm.

3. Omega Notation (Ω-Notation):

Omega notation represents the lower bound of the running time of an algorithm. Thus, it
provides the best case complexity of an algorithm.

The execution time serves as a lower bound on the algorithm's time complexity.

It is defined as the condition that allows an algorithm to complete statement execution in

the shortest amount of time.

Let g and f be the function from the set of natural numbers to itself. The function f is said to
be Ω(g), if there is a constant c > 0 and a natural number n0 such that c*g(n) ≤ f(n) for all n ≥
n0
Algorithm Analysis

Analysis of efficiency of an algorithm can be performed at two different stages, before

implementation and after implementation, as

A priori analysis − This is defined as theoretical analysis of an algorithm. Efficiency of

algorithm is measured by assuming that all other factors e.g. speed of processor, are
constant and have no effect on implementation.

A posterior analysis − This is defined as empirical analysis of an algorithm. The chosen

algorithm is implemented using programming language. Next the chosen algorithm is
executed on target computer machine. In this analysis, actual statistics like running time and
space needed are collected.

Algorithm analysis is dealt with the execution or running time of various operations involved.
Running time of an operation can be defined as number of computer instructions executed
per operation.
Advertisement

Algorithm Complexity

Suppose X is treated as an algorithm and N is treated as the size of input data, the time and
space implemented by the Algorithm X are the two main factors which determine the
efficiency of X.

Time Factor − The time is calculated or measured by counting the number of key operations
such as comparisons in sorting algorithm.

Space Factor − The space is calculated or measured by counting the maximum memory
space required by the algorithm.

The complexity of an algorithm f(N) provides the running time and / or storage space
needed by the algorithm with respect of N as the size of input data.

Space Complexity

Space complexity of an algorithm represents the amount of memory space needed the
algorithm in its life cycle.

Space needed by an algorithm is equal to the sum of the following two components

A fixed part that is a space required to store certain data and variables (i.e. simple variables
and constants, program size etc.), that are not dependent of the size of the problem.

A variable part is a space required by variables, whose size is totally dependent on the size of
the problem. For example, recursion stack space, dynamic memory allocation etc.

Space complexity S(p) of any algorithm p is S(p) = A + Sp(I) Where A is treated as the fixed
part and S(I) is treated as the variable part of the algorithm which depends on instance
characteristic I. Following is a simple example that tries to explain the concept

Algorithm

SUM(P, Q)

Step 1 - START

Step 2 - R ← P + Q + 10

Step 3 - Stop

Here we have three variables P, Q and R and one constant. Hence S(p) = 1+3. Now space is
dependent on data types of given constant types and variables and it will be multiplied
accordingly.

Time Complexity

Time Complexity of an algorithm is the representation of the amount of time required by the
algorithm to execute to completion. Time requirements can be denoted or defined as a
numerical function t(N), where t(N) can be measured as the number of steps, provided each
step takes constant time.
For example, in case of addition of two n-bit integers, N steps are taken. Consequently, the
total computational time is t(N) = c*n, where c is the time consumed for addition of two bits.
Here, we observe that t(N) grows linearly as input size increases.