Data structures are the fundamental building blocks of computer

programming. They define how data is organized, stored, and manipulated

within a program. Understanding data structures is very important for
developing efficient and effective algorithms. A data structure is not only used
for organizing the data. It is also used for processing, retrieving, and storing
data. There are different basic and advanced types of data structures that are
used in almost every program or software system that has been developed.
Basic Terminologies related to Data Structures

The following are some fundamental terminologies used whenever the

data structures are involved:

1. Data: We can define data as an elementary value or a collection of

values. For example, the Employee's name and ID are the data
related to the Employee.
2. Data Items: A Single unit of value is known as Data Item.
3. Group Items: Data Items that have subordinate data items are
known as Group Items. For example, an employee's name can have
a first, middle, and last name.
4. Elementary Items: Data Items that are unable to divide into sub-
items are known as Elementary Items. For example, the ID of an
Employee.
5. Entity and Attribute: A class of certain objects is represented by
an Entity. It consists of different Attributes. Each Attribute
symbolizes the specific property of that Entity. For example,

Attributes ID Name Gender Job Title

Values 1234 Stacey M. Hill Female Software Developer

Entities with similar attributes form an Entity Set. Each attribute of an

entity set has a range of values, the set of all possible values that could
be assigned to the specific attribute.

The term "information" is sometimes utilized for data with given attributes
of meaningful or processed data.

1. Field: A single elementary unit of information symbolizing the

Attribute of an Entity is known as Field.
 2. Record: A collection of different data items are known as a Record.
For example, if we talk about the employee entity, then its name, id,
address, and job title can be grouped to form the record for the
employee.
3. File: A collection of different Records of one entity type is known as
a File. For example, if there are 100 employees, there will be 25
records in the related file containing data about each employee.

Classification of data structures

Primitive Data Structures

1. Primitive Data Structures are the data structures consisting of the
numbers and the characters that come in-built into programs.
2. These data structures can be manipulated or operated directly by
machine-level instructions.
3. Basic data types like Integer, Float, Character, and Boolean come under
the Primitive Data Structures.
4. These data types are also called Simple data types, as they contain
characters that can't be divided further
Non-Primitive Data Structures
1. Non-Primitive Data Structures are those data structures derived from
Primitive Data Structures.
2. These data structures can't be manipulated or operated directly by
machine-level instructions.
3. The focus of these data structures is on forming a set of data elements that
is either homogeneous (same data type) or heterogeneous (different data types).
4. Based on the structure and arrangement of data, we can divide these data
structures into two sub-categories -
 Linear Data Structures
 Non-Linear Data Structure

Linear Data Structure: Data structure in which data elements are arranged
sequentially or linearly, where each element is attached to its previous and next
adjacent elements, is called a linear data structure. Example: Array, Stack,
Queue, Linked List, etc.
Static Data Structure: Static data structure has a fixed memory size. It is easier
to access the elements in a static data structure. Example: array.
Dynamic Data Structure: In dynamic data structure, the size is not fixed. It
can be randomly updated during the runtime which may be considered efficient
concerning the memory (space) complexity of the code. Example: Queue,
Stack, etc.
Non-Linear Data Structure: Data structures where data elements are not
placed sequentially or linearly are called non-linear data structures. In a non-
linear data structure, we can’t traverse all the elements in a single run only.
Examples: Trees and Graphs.
1. Array
The array is a type of data structure that stores elements of the same type. These
are the most basic and fundamental data structures. Data stored in each position
of an array is given a positive value called the index of the element. The index
helps in identifying the location of the elements in an array.
2. Stack
The data structure follows the rule of LIFO (Last In-First Out) where the data
last added element is removed first. Push operation is used for adding an
element of data on a stack and the pop operation is used for deleting the data
from the stack.
3. Queue
This structure is almost similar to the stack as the data is stored sequentially.
The difference is that the queue data structure follows FIFO which is the rule of
First In-First Out where the first added element is to exit the queue first. Front
and rear are the two terms to be used in a queue. Enqueue is the insertion
operation and dequeue is the deletion operation.
4. Linked List
Linked lists are the types where the data is stored in the form of nodes which
consist of an element of data and a pointer. The use of the pointer is that it
points or directs to the node which is next to the element in the sequence.
5. Trees
A tree data structure consists of various nodes linked together. The structure of
a tree is hierarchical that forms a relationship like that of the parent and a child.
The structure of the tree is formed in a way that there is one connection for
every parent-child node relationship. Only one path should exist between the
root to a node in the tree. Various types of trees are present based on their
structures like AVL tree, binary tree, binary search tree, etc.
6. Graph
Graphs are those types of non-linear data structures which consist of a definite
quantity of vertices and edges. The vertices or the nodes are involved in storing
data and the edges show the vertices relationship. The difference between a
graph to a tree is that in a graph there are no specific rules for the connection of
nodes. Real-life problems like social networks, telephone networks, etc. can be
represented through the graphs.

Basic Operations of Data Structures

In the following section, we will discuss the different types of operations that
we can perform to manipulate data in every data structure:

1. Traversal: Traversing a data structure means accessing each data

element exactly once so it can be administered. For example, traversing is
required while printing the names of all the employees in a department.
2. Search: Search is another data structure operation which means to find
the location of one or more data elements that meet certain constraints.
Such a data element may or may not be present in the given set of data
 elements. For example, we can use the search operation to find the names
of all the employees who have the experience of more than 5 years.
3. Insertion: Insertion means inserting or adding new data elements to the
collection. For example, we can use the insertion operation to add the
details of a new employee the company has recently hired.
4. Deletion: Deletion means to remove or delete a specific data element
from the given list of data elements. For example, we can use the deleting
operation to delete the name of an employee who has left the job.
5. Sorting: Sorting means to arrange the data elements in either Ascending
or Descending order depending on the type of application. For example,
we can use the sorting operation to arrange the names of employees in a
department in alphabetical order or estimate the top three performers of
the month by arranging the performance of the employees in descending
order and extracting the details of the top three.
6. Merge: Merge means to combine data elements of two sorted lists in
order to form a single list of sorted data elements.

ALGORITHMS

An algorithm is a properly defined sequence of steps or commands designed to

clear up a selected problem or perform a selected task. It is a scientific method
to problem-fixing that outlines the important movements or operations to be
accomplished in a clean and unambiguous manner. Algorithms can be
expressed in various bureaucracy, along with natural language, pseudocode,
flowcharts, or programming languages.

Characteristics of algorithms:

1. Well-described steps: Algorithms are composed of a specific and

unambiguous set of instructions or steps that can be observed to perform
a selected task or solve a problem. Each step ought to be well-defined,
leaving no room for ambiguity or confusion.
2. Input and output: Algorithms take inputs, which might be the
preliminary records or facts furnished to the algorithm, and produce
outputs, which are the results or solutions generated by using the set of
rules after processing the inputs. The relation among the inputs and
outputs is decided by means of the algorithm's good judgment.
 3. Finiteness: Algorithms must have a well-defined termination condition.
This method means that they finally attain an endpoint or change after a
finite quantity of steps. If a set of rules runs indefinitely without
termination, it's far taken into consideration wrong or incomplete.
4. Determinism: Algorithms are deterministic, that means that given the
same inputs and achieved below the same conditions, they may
continually produce the identical outputs. The conduct of a set of rules
ought to be predictable and regular.
5. Efficiency: Algorithms attempt to be efficient in phrases of time and
sources. They goal to clear up issues or perform obligations in an
inexpensive quantity of time and with ultimate use of computational
sources like memory, processing power, or garage.
6. Generality: A set of rules must be designed to resolve a particular
problem or carry out a selected assignment, but it must also be relevant to
a broader elegance of times or scenarios. It ought to have a certain level
of flexibleness and flexibility.
7. Correctness: Algorithms must be designed to produce correct results for
all legitimate inputs inside their domain. They must accurately solve the
problem they may be designed for, and their outputs must match the
anticipated consequences.
8. Modularity and reusability: Algorithms may be modular, meaning they
may be divided into smaller subproblems or features that may be reused
in unique parts of the algorithm or in other algorithms. This promotes
code agency, maintainability, and code reuse.
9. Understandability: Algorithms need to be designed with clarity and ease
in mind, making them easy to apprehend and implement. Well-
documented and readable code can enhance the understandability of an
algorithm.

Example 1:

Algorithm: FindMaximum

Input: An array of integers A

Output: The maximum element in A

1. Set max to the first element of A

2. For each element num in A starting from the second element:
a. If num is greater than max, update max to num.
3. Return max as the maximum element in A
Difference between data t ype and data structure:
Data Types Data Structures

Data Type is the kind or form of a Data Structure is the collection of

variable which is being used throughout different kinds of data. That entire data
the program. It defines that the particular can be represented using an object and
variable will assign the values of the can be used throughout the entire
given data type only program.

Implementation through Data Types is a Implementation through Data Structures

form of abstract implementation is called concrete implementation

Can hold values and not data, so it is Can hold different kind and types of data
data less within one single object

The data is assigned to the data structure

Values can directly be assigned to the
object using some set of algorithms and
data type variables
operations like push, pop and so on.

Time complexity comes into play when

No problem of time complexity
working with data structures

Examples: int, float, double Examples: stacks, queues, tree

Complexity analysis

Complexity analysis is defined as a technique to characterise the time taken

by an algorithm with respect to input size (independent from the machine,
language and compiler). It is used for evaluating the variations of execution
time on different algorithms.

What is the need for Complexity Analysis?

 Complexity Analysis determines the amount of time and space resources
required to execute it.
 It is used for comparing different algorithms on different input sizes.
 Complexity helps to determine the difficulty of a problem.
 Often measured by how much time and space (memory) it takes to solve a
particular problem

[Link] Complexity

The time complexity of an algorithm is defined as the amount of time taken

by an algorithm to run as a function of the length of the input. Note that the
time to run is a function of the length of the input and not the actual
execution time of the machine on which the algorithm is running on. To
estimate the time complexity, we need to consider the cost of each
fundamental instruction and the number of times the instruction is executed.
2. Space Complexity :

The amount of memory required by the algorithm to solve a given problem is

called the space complexity of the algorithm. Problem-solving using a
computer requires memory to hold temporary data or final result while the
program is in execution. The space Complexity of an algorithm is the total
space taken by the algorithm with respect to the input size. Space complexity
includes both Auxiliary space and space used by input. (The temporary space
needed for the use of an algorithm is referred to as auxiliary space. Like
temporary arrays, pointers,etc. It is preferable to make use of Auxiliary Space
when comparing things like sorting algorithms. )

To optimize a program,

1. We can reduce the time taken to run the program and increase the
space occupied;

2. we can reduce the memory usage of the program and increase its total
run time, or

3. we can reduce both time and space complexity by deploying relevant

algorithms

Different types of Complexity exist in the program:

1. Constant Complexity
If the function or method of the program takes negligible execution time. Then
that will be considered as constant complexity.

2. Logarithmic Complexity:

It imposes a complexity of O(log(N)). It undergoes the execution of the order

of log(N) steps. To perform operations on N elements, it often takes the
logarithmic base as 2.

3. Linear Complexity:

It imposes a complexity of O(N). It encompasses the same number of steps as

that of the total number of elements to implement an operation on N elements.

[Link] Complexity:

It imposes a complexity of O(n^2). For N input data size, it undergoes the

order of N2 count of operations on N number of elements for solving a given
problem.
There are Exponnetial complexity,factotial complexity and so on.

Analysis of algorithms is the determination of the amount of time and space

resources required to execute it.

Why Analysis of Algorithms is important?

 To predict the behavior of an algorithm without implementing it on a

specific computer.
 The analysis is only an approximation; it is not perfect.
 More importantly, by analyzing different algorithms, we can compare them
to determine the best one for our purpose.

Types of Algorithm Analysis:

1. Best case

2. Worst case
3. Average case

 Best case: Define the input for which algorithm takes less time or
minimum time. In the best case calculate the lower bound of an
algorithm. Example: In the linear search when search data is present at
the first location of large data then the best case occurs.

 Worst Case: Define the input for which algorithm takes a long time or
maximum time. In the worst calculate the upper bound of an algorithm.
Example: In the linear search when search data is not present at all then
the worst case occurs.

 Average case: In the average case take all random inputs and calculate
the computation time for all inputs.
And then we divide it by the total number of inputs.

Average case = all random case time / total no of case

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.

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-Oh(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.

Eg: the time (or the number of steps) it takes to complete a problem of size
might be found to be

T(n) = 4n2− 2n+ 2. As n grows large, then n2 term will come to dominate, so
that all other terms can be neglected. ie,we say T(n) is the “Big O” of n 2

T(n)=O(n2)

( when n= 500, the term 4n2 is 1000 times as large as the 2n term. Ignoring
the latter would have negligible effect on the expression's value for most
purposes.)

The execution time serves as an upper bound on the algorithm’s time

complexity.
Balancing time and space complexity

One approach may take more space but takes less time to complete its
execution while the other approach may take less space but takes more
time to complete its execution.
We may have to sacrifice one at the cost of the other.
If space is our constraint, then we have to choose a program that requires
less space at the cost of more execution time.
On the other hand if time is our constraint then we have to choose a
program that takes less time to complete its execution at the cost of more space.

Strings
In data structures, a string is a sequence of characters used to represent
text. Strings are commonly used for storing and manipulating textual data in
computer programs. String Operations: Strings support a wide range of
operations, including concatenation, substring extraction, length calculation,
and more. These operations allow developers to manipulate and process string
data efficiently. So the terms string processing ,string manipulation etc are used
instead of word processing.
Below are fundamental operations commonly performed on strings in
programming.
Concatenation: Combining two strings to create a new string.
Length: Determining the number of characters in a string.
Substring: Extracting a portion of a string.
Comparison: Comparing two strings to check for equality or order.
Search: Finding the position of a specific substring within a string.
Replace: Changing or replacing characters within a string.

Terminology
1) Character set: includes alphabets(A-Z),digits(0-9),special characters(+,-,/,*,
(),.,$,=etc)
2) String is defined as a finite sequence S of zero or more characters.
3) Length: The number of characters in a string is called its length.
Length(string) function returns the length of a string.
Strings are denoted by enclosing their characters in single quotation marks.
Eg:’To Begin’ ,length=8(blank space also counted).
4) Empty string(null string):The string with zero characters.
5)Concatenation:
Let S1 and S2 be two strings, then the string consisting of characters of S1
followed by the characters of S2 is called concatenation of S1 and S2(denoted
by S1//S2)

Eg:’To’//’begin’=‘Tobegin’
‘To’//’ ‘//’begin’=‘To begin’
The length of S1//S2=sum of lengths of S1 and S2
6)Substring:
• A string Y is called a substring of a string S if there exist X and Z such
that S=X//Y//Z
Initial substring: if X is an empty string then Y is an Initial substring
Terminal substring: if Z is an empty string then Y is an terminal substring
• Accessing a substring from a given string requires
1. The string itself
2. Position of first character of the substring in the given string
3. The length of the substring
Substring(string,initial,length)
Substring(S,K,L)
Substring(‘computer’,1,3) returns ‘com’
7) Indexing(pattern matching)
•To find the position where a string pattern P first appears in a given string text
T
•Index(text, pattern)
•If pattern P does not appear in the text T, then index returns a value 0
8) White Space Removal
•The STRCOMPRESS and STRTRIM functions can be used to eliminate
unwanted white space (blanks or tabs) from their string arguments.
STRCOMPRESS(‘TO BE OR NOT TO BE’) returns TOBEORNOTTOBE

The following operations are usually done in word processing

[Link]:Replacing one string in the text by another
[Link]:Inserting a string in the middle of the text
[Link]:Deleting a string from the text

These operations are executed using the string operations as follows:

Insertion
Given text T ,to insert a string S such that S begins in position K
INSERT(text,position,string)
Eg:INSERT(‘ABCDEFG’,3,’XYZ’)=‘ABXYZCDEFG’
INSERT(‘ABCDEFG’,6,’XYZ’)=‘ABCDEXYZFG’

The INSERT function can be implemented by using the String operations as

follos:
SUBSTRING(T,1,K-1)
•Here T=‘ABCDEFG’
•S=‘XYZ’
•The string is to be inserted to K ,so access or retrieve the substring from
position 1 to (K-1).
 Here If K=3 then K-1=[Link] string retrieved is ‘AB’
•Then ‘XYZ’ is concatenated from K=3 (third position).
 •The result(‘ABXYZ’) is concatenated with the remaining part of T which
begins in the position K.
•Now T has length Length(T)- (K-1)=Length(T-K+1).

So can be written as:

INSERT(T,K,S)=SUBSTRING(T,1,K1)//S//SUBSTRING(T,K,LENGTH(T)-K+1)

Deletion
Given text T ,to delete a substring that begins in position K and has length L
DELETE(text,position,length)
Eg: DELETE(‘ABCDEFG’,4,2)=‘ABCFG’
DELETE(‘ABCDEFG’,2,4)=‘AFG’
Algorithm 1: Deletion
A text T and a pattern P are in memory. This algorithm deletes every
occurrence of P in T.
1.[Find index of P.]Set K:=INDEX(T,P)
[Link] while K ≠0:
a) [Delete P from T]
Set T:=DELETE(T,INDEX(T,P),LENGTH(P))
b) [Update index.]Set K:=INDEX(T,P).
[End of loop.]
3. Write T.
4. Exit.

Replacement

Given text T , to replace the first occurrence of a pattern P1 by a pattern P2 .

REPLACE(text,pattern1,pattern2)
Eg: REPLACE(‘XABYABZ’,’AB’,’C’)=‘XCYABZ’
REPLACE(‘XABYABZ’,’BA’,’C’)=‘XABYABZ’
The pattern BA does not occur, hence no change.
The replace function is expressed as deletion followed by an insertion and can
be executed using three steps.
K:=INDEX(T,P1)
T:=DELETE(T,K,LENGTH(P1))
INSERT(T,K,P2)

Algorithm 2: Replace
A text T and patterns P and Q are in memory. This algorithm replaces every
occurrence of P in T by Q.
1.[Find index of P.]Set K:=INDEX(T,P)
[Link] while K ≠0:
a) [Replace P by Q]
Set T:=REPLACE(T,P,Q)
b) [Update index.]Set K:=INDEX(T,P).
[End of loop.]
3. Write T.
4. Exit

PA

TTERN MATCHING ALGORITHMS

 • Pattern matching is a problem of deciding whether or not a given string
pattern P appears in a string text T.
• The length of P does not exceed the length of T
• We compare a given pattern P with each of the substrings of T moving
from left to right until we get a match
• Wk=SUBSTRING(T,K,LENGTH(P))
Wk denotes the substring of T having the same length as P and beginning with
the K th character of T.
• We compare P character by character with the first substring W1; if all
characters are the same then P=W1..ie P appears in T and INDEX(T,P)=1
NOTE
Substring(string,initial,length):To access a substring from a given string .
INDEX(T,P): To find the position where a string pattern P first appears in a
given string text T.

First pattern matching algorithm(Naïve’s Algorithm)

• P is an r-character string and T is an s-characterstring
• The algorithm contain two loops ,one inside another.
• Outer loop runs through each successive r-character substring
Wk=T[K]T[K+1]T[K+2]….T[K+R-1] of T.
• The inner loop compares P with Wk character by character.
• If any character does not match then control transfers to steps 5 which
increases K and then leads to the next substring of T. If all the r-
characters of P do match those of some Wk, then P appears in T and K is
the INDEX of P in T.
• If outer loop is completed then P does not appear in T and so INDEX=0
• Complexity of the algorithm:O(n2)
Second Pattern matching algorithm( String Matching with
Finite Automata)
•This algorithm uses a table which is derived from a particular pattern P but is
independent of the text T
•Suppose
P=aaba,
T=T1T2T3… where Ti denotes the i-th character of T
If the first two characters match those of P, T=aa…,then T can have
any of the 3 forms:
i) T=aab..
ii) ii)T=aaa…
iii) iii) T==aax where x is any character other than a or b
•If T3=b and T4=a then P =W1(T1T2=aa)
•If T3= a then P≠W1, but then T2T3=aa. Hence read [Link] T4=b, then read [Link]
T5=a then P=W2
•If T3=x, then P≠W1, P≠W2and P≠W3since x doesnot appear in P .Hence read
[Link] T4=a then first character of W4matches the first character of P.
•Second pattern matching algorithm uses a table and an accompanying graph as
follows
Q0=λ ,Q1=a, Q2=a2, Q3=a2b,Q4=a2ba=P

•Qi denotes the initial substring of P of length i.

•Q0=λ ,Q1=a, Q2=a2, Q3=a2b,Q4=a2ba=P aaba=a2ba
•Q0 is an empty string.
•In the table the rows are named by the initial substrings Q0 ,Q1 ,Q2 ,Q3 and
the columns are labelled a,b,x where x is any character that does not appear in
P.
•A function f(Qi ,t)denotes the entry in the table in row Qi and column t(t is any
character).This entry denotes the largest Q that appears as a terminal substring
in the string Qit(concatenation of Qi and t). Here
f(Q0,a)=Q1
f(Q0,b)=Q0
f(Q0,x)=Q0
f(Q1,a)=Q2
f(Q1,b)=Q0 and so on
•In the graph there is a node corresponding to each initial substring of P
•All Q’s are called the states of the system,Q0 is the initial state.
•There is directed edge in the graph corresponding to each entry In the table .If
f(Qi,t)=Qj then there is an arrow labelled t from Qi to Qj
Eg: If f(Q2,b)=Q3 there is an arrow labelled b from Q2to Q3

Let T=T1T2T3…Tn denote an n character string in which pattern P =aaba is

searched.
•Beginning with the initial state Q0 and using the text T ,a sequence of steps are
obtained like S1,S2,S3…
•Assume S1=Q0 then from table or graph,
f(S1,T1)=S2,
f(S2,T2)=S3 and so on..
Then there are two possibilities:
(1)some state Sk= P, the desired pattern. In this case, P does appear in T and its
index is K-LENGTH(P)
(2)No state S1,S2….SN+1 is equal to P. In this case P does not appear in T.

Complexity of this algorithm is O(n).

[Link] are the applications of strings