School of Engineering and Technology

Programme Name BCA

Course Title DATA STRUCTURE
Course Code 24BCA023C01
Semester IIIrd sem
LTPC L:3 T:0 P:0 C:3

UNIT-I

Introduction to Data Structure:

The name "Data Structure" is a combination of two words: "Data" and "Structure". Let's go over each word
individually:

 Data: Data is information that must be processed and stored in a computer. Data can be anything from
numbers to characters to dates to photos to videos.
 Structure: Structure refers to how data is structured. It specifies the relationship between various data
elements and how they are kept in memory. The structure has an impact on the efficiency of data operations.

A data structure is a storage that is used to store and organize data. It is a way of arranging data on a computer so that
it can be accessed and updated efficiently.

A data structure organizes, processes, retrieves, and stores data, making it essential for nearly every program or
software system. To help you master them, we've compiled a comprehensive guide covering types, classifications, and
applications of data structures.
Page | 1
www.ctuniversity.in
Every application, piece of software, or programs foundation consists of two components: algorithms and data. Data is
information, and algorithms are rules and instructions that turn the data into something useful to programming.

Related data + Permissible operations on the data = Data Structures

Data structures + Algorithms = Programs

Basic Terminology of Data Structures

Understanding key terminology is essential for working with data structures:

 Data: Values that are collected and organized

 Data item: A single piece of information
 Group item: A collection of related data items
 Elementary item: A data item that cannot be further divided
 Entity: A real-world object or concept represented in a database
 Entity set: A collection of similar entities
 Field: A single characteristic of an entity
 Record: A complete set of data about an entity
 File: A collection of related records

Why Are Data Structures Important?

Data structures provide numerous benefits to IT-related processes, particularly as applications become more complex
and the amount of data available grows.

Key Benefits:

⚡ Efficiency: If the choice of a data structure for implementing a particular ADT is proper, it makes the program very
efficient in terms of time and space

🔄 Reusability: The data structure provides reusability means that multiple client programs can use the data structure

🎭 Abstraction: The data structure specified by an ADT also provides the level of abstraction. The client cannot see the
internal working of the data structure

🔍 Organization: Makes accessing, modifying, and storing data much easier

🔗 Relationships: Helps discover and recognize connections between data pieces

📦 Versatility: Can store diverse information - numbers, text, images, and complex entities

Page | 2
www.ctuniversity.in
How are data structures used?

Data structures are crucial tools in software development and data management, providing efficient ways to work
with abstract data types. They play a vital role in the creation of well-designed software, effective algorithms, and
seamless data exchange between various applications.

 Storing data: Data structures are instrumental in storing information within database management systems.
This involves defining attributes and associated structures to house records efficiently.
 Managing resources and services: They are used for managing core operating system resources and services,
encompassing memory allocation, file directory administration, and process scheduling.
 Ordering and sorting: Data structures come into play when organizing and arranging data, whether it's
character strings or Objects with specific priorities.
 Indexing: Data structures facilitate indexing data, making it easier to locate specific items within a database.
 Searching: Creating indexes with data structures accelerates the process of finding particular items within a
dataset.
 Scalability: Big data applications utilize data structures to allocate and manage data storage across distributed
sites, ensuring optimal performance and scalability.

What is the need of Data Structure?

We need data structures because they provide efficient solutions to organizing and manipulating data. They help to
store and retrieve data in an organized manner, making it easier to manage and analyze the information. Some
specific reasons why data structures are important include:

1. Improved Time Complexity: Using appropriate data structures can lead to better time complexity, making it
possible to solve problems more quickly. For example, searching for an element in a sorted array is faster than
searching for it in an unsorted array.

2. Better Space Complexity: Data structures can help to reduce the amount of memory needed to store data.
For example, using a linked list instead of an array can reduce the amount of memory needed to store the
same data.

3. Efficient Data Retrieval: Data structures make it easier to retrieve specific data efficiently. For example, a hash
table can retrieve data in constant time, while searching through an unsorted array takes linear time.

4. Better Data Management: Data structures make it easier to manage and manipulate data. For example, a
stack can be used to implement an undo functionality in an application.

5. Solving Complex Problems: Data structures can provide the foundation for efficient algorithms, making it
possible to solve complex problems in a reasonable amount of time. For example, graph algorithms can be
used to find the shortest path between two points or to find the minimum spanning tree of a graph.

Page | 3
www.ctuniversity.in
In summary, data structures play a crucial role in solving problems related to data management and analysis by
providing efficient solutions for organizing, retrieving, and manipulating data.

Characteristics of Data Structure

The following are some of the main characteristics of data structures:

1. Representation of Data: Data structures define a way of representing data in a computer's memory, making it
possible to store, manipulate, and access data efficiently.

2. Access Techniques: Different data structures provide different techniques for accessing data stored within
them, such as random access or sequential access.

3. Storage Organization: Data structures define the organization of data in memory, such as linear or
hierarchical organization.

4. Insertion and Deletion Operations: Different data structures support different methods for adding and
removing elements, such as insertion at the end or deletion from the front.

5. Time and Space Complexity: Data structures can have different time and space complexities, depending on
the operations they support and the way they organize data.

6. Adaptability: Some data structures are more adaptable to certain types of data and operations than others.
For example, a stack is more suitable for problems that require Last-In-First-Out (LIFO) behavior, while a
queue is better suited for problems that require First-In-First-Out (FIFO) behavior.

7. Flexibility: Different data structures have different degrees of flexibility, such as the ability to dynamically
grow or shrink in size, or the ability to efficiently insert or delete elements in the middle.

Advantages of Data Structure

The following are some of the main advantages of using data structures:

1. Better Data Organization: Data structures provide a way of organizing data in a meaningful and efficient
manner, making it easier to access and manipulate data.

2. Increased Data Retrieval Efficiency: Data structures can provide fast and efficient retrieval of data, which is
essential in many real-world applications.

3. Efficient Data Manipulation: Data structures can provide efficient methods for adding, deleting, and
modifying data, which is important in dynamic applications.

4. Improved Code Reusability: Reusable data structures can be used in many different applications, reducing the
time and effort required to write and maintain code.

5. Better Problem-Solving Capability: Data structures provide a way of modelling real-world problems and
solving them in a more efficient and elegant manner.

Page | 4
www.ctuniversity.in
 6. Reduced Memory Requirements: Data structures can be designed to use memory more efficiently, reducing
the overall memory requirements of an application.

7. Increased Data Security: Data structures can be designed to provide additional security features, such as data
encryption and protection against unauthorized access.

Data Structure Operations:

Data structure operations refer to the various actions that can be performed on a data structure. A data structure is a
way of organizing and storing data in a computer so that it can be accessed and manipulated efficiently. Different data
structures have different capabilities and efficiencies for different operations.

Data structure operations can be broadly categorized into two types:

 Basic Operations: These are the fundamental operations that can be performed on a data structure. Examples
include insertion, deletion, search, and access.
 Advanced Operations: These are more complex operations that are built on top of basic operations. Examples
include sorting, merging, splitting, and traversal.

Here is a list of common data structure operations with examples:

 Insertion: Adding an element to the data structure. For example, inserting an element into an array or a linked
list.
 Deletion: Removing an element from the data structure. For example, removing an element from a array or a
linked list.
 Search: Finding an element in the data structure. For example, searching for a specific key or value in array or
a linked list.
 Access: Retrieving an element from the data structure. For example, accessing the first element of a queue.
 Traversal: Visiting every element in the data structure. For example, printing all elements of an array or a
linked list.
 Sorting: Arranging elements in the data structure in a particular order. For example, sorting an array of
integers in ascending or descending order.
 Merging: Combining two data structures into one. For example, merging two sorted linked lists into a single
sorted linked list.
 Splitting: Breaking a data structure into smaller parts. For example, splitting a linked list into two equal halves.

Page | 5
www.ctuniversity.in
  Reversal: Reversing the order of elements in the data structure. For example, reversing the elements of a
stack.
 Indexing: Accessing an element of the data structure using an index or a key. For example, accessing the
element at index i in an array.

Real World Applications of Data Structures

Data structures are a fundamental concept in computer science and have different applications in various fields. Some
of the most common applications of data structures .

Here is a list of some common applications of Data structures, along with examples:

 Database Management Systems - Data structures are used to store and organize large amounts of data in a
structured manner. For example, a relational database uses tables and indices to store data, and a NoSQL
database uses document-oriented or key-value data structures.
 Operating Systems - Data structures are used to manage resources, such as memory allocation and process
scheduling. For example, a priority queue data structure can be used to manage the scheduling of processes in
an operating system.
 Graphical User Interfaces - Data structures are used to store and display hierarchical data, such as the file
system in a computer's file explorer. For example, a tree data structure can be used to represent the file
hierarchy in a file explorer.
 Computer Networks - Data structures are used to store information about network topology and to
implement routing algorithms. For example, a graph data structure can be used to represent a computer
network, with nodes representing devices and edges representing connections between devices.
 Compiler Design - Data structures are used to store and process the syntax and semantics of programming
languages. For example, a parse tree data structure can be used to represent the structure of a program and
to generate intermediate code.
 Artificial Intelligence and Machine Learning - Data structures are used to store and manipulate large amounts
of data in order to train algorithms and make predictions. For example, a decision tree data structure can be
used in a machine learning algorithm to make predictions based on input data.
Page | 6
www.ctuniversity.in
  Computer Graphics - Data structures are used to store and manipulate geometric models for rendering and
animation. For example, a 3D mesh data structure can be used to represent a 3D object in computer graphics.
 Bioinformatics - Data structures are used to store and analyze large amounts of biological data, such as DNA
sequences and protein structures. For example, a suffix tree data structure can be used to efficiently store and
search for patterns in DNA sequences.
 Web Search Engines - Data structures are used to store and retrieve large amounts of web pages and to rank
them based on relevance. For example, an inverted index data structure can be used to store keywords and
their corresponding web pages, allowing for fast searching and retrieval.
 Computer Algorithms and Optimization - Data structures are used to design and analyze algorithms for solving
complex problems. For example, a priority queue data structure can be used in Dijkstra's algorithm for finding
the shortest path in a graph.

 Geographic Information Systems (GIS) - Data structures are used to store and analyse geographical data, such
as maps, satellite images, and census data. For example, a quadtree data structure can be used to efficiently
store and search for geographical features, such as cities or roads.
 Video Games - Data structures are used to store and manipulate game objects and their interactions. For
example, a spatial partitioning data structure can be used to efficiently search for and detect collisions
between game objects.
 Financial Systems - Data structures are used to store and manage financial data, such as stock prices and
transaction history. For example, a balanced binary search tree data structure can be used to efficiently store
and retrieve stock prices.
 Cryptography - Data structures are used to store and process encrypted data and to implement cryptographic
algorithms. For example, a hash table data structure can be used to store and look up values for encryption
and decryption.
 Natural Language Processing (NLP) - Data structures are used to store and process large amounts of text data,
such as for text classification, sentiment analysis, and text generation. For example, a trie data structure can
be used to efficiently store and search for words in a large text corpus.

Classification of Data Structure

Page | 7
www.ctuniversity.in
Data structure has many different uses in our daily life. There are many different data structures that are used to solve
different mathematical and logical problems. By using data structure, one can organize and process a very large
amount of data in a relatively short period. Let's look at different data structures that are used in different situations.

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.

Examples: 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 data structure.

 Dynamic data structure: In the 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.

Examples: stack and queue data structures.

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.

Examples: tree and graph data structures.

1. Arrays Data Structure

An array is a linear data structure and it is a collection of elements of same data type stored at contiguous memory
locations.
It offers mainly the following advantages.
 Random Access: i-th elements can be accessed in O(1) Time as we have the base address and every element is of
same size.
 Cache Friendliness: Since elements are stored at contiguous locations, we get the advantage of locality of
reference.

Page | 8
www.ctuniversity.in
Applications of an array are as follows:
Arrays efficiently manage and store database records.
 It helps in implementing sorting algorithm.
 It is also used to implement other data structures like Stacks, Queues, Heaps, Hash tables, etc.
 An array can be used for CPU scheduling.

2. Linked list Data Structure

A linked list is a linear data structure in which elements are not stored at contiguous memory locations. The elements
in a linked list are linked using pointers as shown in the below image.

Applications of the Linked list

 Linked lists are used to implement other data structures like stacks, queues, etc.
 It is used for the representation of sparse matrices.
 It is used in the linked allocation of files.
 Linked lists are used to display image containers. Users can visit past, current, and next images.
 They are used to perform undo operations.

3. Stack Data Structure

Stack is a linear data structure that follows LIFO(Last in first out) principle i.e., entering and retrieving data is possible
from only one end. The entering and retrieving of data is also called push and pop operation in a stack.

Applications of Stack

 The stack data structure is used in the evaluation and conversion of arithmetic expressions.
Page | 9
www.ctuniversity.in
  It is used for parenthesis checking and string reversal.

 A memory stack is also used for processing function calls.

 The stack is used in virtual machines like JVM.

4. Queue Data Structure

Queue is a linear data structure that follows First In First Out(FIFO) principle i.e. the data item stored first will be
accessed first. In this, entering is done from one end and retrieving data is done from other end. An example of a
queue is any queue of consumers for a resource where the consumer that came first is served first.

Applications of Queue:
 Queue is used for handling website traffic.
 It helps to maintain the playlist in media players.
 It helps in serving requests on a single shared resource, like a printer, CPU task scheduling, etc.
 Queues are used for job scheduling in the operating system.

5. Tree Data Structure

A tree is a non-linear and hierarchical data structure where the elements are arranged in a tree-like structure. In a
tree, the topmost node is called the root node. Each node contains some data, and data can be of any type. It consists
of a central node, structural nodes, and sub-nodes which are connected via edges. Different tree data structures allow
quicker and easier access to the data as it is a non-linear data structure.

Applications of Tree:
 Heap is a tree data structure that is implemented using arrays and used to implement priority queues.
 B-Tree and B+ Tree are used to implement indexing in databases.
 Syntax Tree helps in scanning, parsing, generation of code, and evaluation of arithmetic expressions in Compiler
design.
 Spanning trees are used in routers in computer networks.
 Domain Name Server also uses a tree data structure.

Page | 10
www.ctuniversity.in
 6. Graph Data Structure
A graph is a non-linear data structure that consists of vertices (or nodes) and edges. It consists of a finite set of
vertices and set of edges that connect a pair of nodes. The graph is used to solve the most challenging and complex
programming problems. It has different terminologies which are Path, Degree, Adjacent vertices, Connected
components, etc.

Graph

Applications of Graph:
 The operating system uses Resource Allocation Graph.
 Also used in the World Wide Web where the web pages represent the nodes.
 One of the most common real-world examples of a graph is Google Maps where cities are located as vertices
and paths connecting those vertices are located as edges of the graph.
 A social network is also one real-world example of a graph where every person on the network is a node, and
all of their friendships on the network are the edges of the graph.

Algorithm Analysis
Algorithm analysis is the process of evaluating the performance of an algorithm and measuring its computational
efficiency. The goal of algorithm analysis is to determine the time and/or space complexity of an algorithm and to
compare it to other algorithms for the same problem.

There are two main aspects of algorithm analysis: Time complexity and Space complexity. Time complexity is a
measure of the amount of time an algorithm takes to run as a function of the size of the input data. Space complexity
is a measure of the amount of memory an algorithm requires to run as a function of the size of the input data.

There are several methods for analysing the performance of algorithms, including:

Page | 11
www.ctuniversity.in
  Asymptotic Analysis: Asymptotic analysis is the process of calculating an algorithm's running time in
mathematical units to determine the program's limitations. It helps to study the long-term behaviour of
algorithms and estimate their efficiency in terms of time and space complexity.

 Worst-Case Analysis: Worst-Case Analysis is a method of evaluating the performance of an algorithm by

analyzing the maximum amount of resources (such as time or memory) that the algorithm would require to
solve the largest possible input size within its scope. In other words, it's a way to determine how the algorithm
would perform in the worst possible scenario, allowing us to understand the upper bound of its performance.
This information is useful in determining the reliability and stability of the algorithm, especially in mission-
critical applications where high performance is crucial.

 Average-Case Analysis: Average-Case Analysis is a method of evaluating the performance of an algorithm by

analysing the expected amount of resources (such as time or memory) that the algorithm would require to
solve a random input of a given size. It provides an estimation of the average performance of an algorithm
over all possible inputs.

 Best-Case Analysis: Best-Case Analysis is a method of evaluating the performance of an algorithm by analyzing
the minimum amount of resources (such as time or memory) that the algorithm would require to solve the
smallest possible input size within its scope. It gives the upper bound of the algorithm's performance. IN other
words, it's a way to determine how the algorithm would perform in the best possible scenario, allowing us to
understand the lower bound of its performance. This information is useful in determining the minimum
resources required to solve a problem with the algorithm and provides an upper bound on performance
optimization

What is Algorithm Complexity?

Algorithm complexity refers to the number of steps an algorithm needs to take in order to solve a particular problem.
When given an input of size n, an algorithm's complexity is determined by how long it would take to complete a
particular problem. If an algorithm needs to scale, even for very large values of n, it should still be able to compute the
result in a finite and reasonable amount of time. Because of this, complexity is estimated asymptotically as n gets
closer to infinity. While complexity is typically measured in terms of time, it can also be measured in terms of space, or
more specifically, in terms of the amount of memory used by the algorithm.

Examples to Understand Algorithm Complexity

 If there is a big, unsorted list and you are seeking for a certain item, you will likely compare each item. Search
time is proportional to the list size. In this case, complexity is linear.
 On the other hand, searching for a word in a dictionary will be quicker since the words are arranged in order,
you are aware of the order, and you can quickly determine whether you need to turn to earlier or later pages.
This is an illustration of logarithmic complexity.
 No matter how many words there are in the dictionary, selecting the first word from it always takes a
Constant amount of time. The complexity of joining the end of a bank queue is also constant regardless of
how lengthy the queue is.This is an illustration of constant complexity.

Page | 12
www.ctuniversity.in
  The difficulty increases quadratically if you are requested to find all duplicates in an unsorted list. It is linearly
complex to search for duplicates of a single item. If we apply this rule to every item, complexity takes
a quadratic form.

What is the time space trade off?

A space-time tradeoff is a strategy used in computer science to either solve a problem or calculation quickly by using
more storage space, or slowly and carefully by using very little space.

An algorithm or software in this situation trades off more space usage for less time. Thus, space refers to the amount
of data storage used (RAM, HDD, etc.) and time refers to the amount of time used to complete a certain activity
(computation time or response time)

Need of Time Space Tradeoff

 Less time by using more memory

 Solving a problem in very little space by spending a long time.

Asymptotic Analysis
Asymptotic notations are mathematical notations for analysing the runtime of a given algorithm for a large input. It
allows us to compare the runtimes of various algorithms without having to manually calculate their runtimes. We
must determine how long our algorithm takes to complete each step in order to evaluate how well it performs for
various inputs. This time can easily be calculated by manually. Sometimes it's not possible for humans to record such a
small runtime, so manually measuring an algorithm's runtime is not a smart idea.

Asymptotic notation is a mathematical notation that is used to analyze the time complexity and the runtime of an
algorithm for a large input.

An algorithm's asymptotic analysis involves determining the mathematical limits or framing of its run-time
performance. We may easily draw conclusions about an algorithm's best case, average case, and worst case scenarios
using asymptotic analysis.

An algorithm's time requirement often falls into one of three categories.

 Best Case − Minimum time required for program execution.

 Average Case − Average time required for program execution.
 Worst Case − Maximum time required for program execution.

Types of Asymptotic Notations

The complexity of algorithms for asymptotic analysis is represented using asymptotic notations. These symbols are
tools used in mathematics to express complexity. Three notations are usually applied.

 Big Oh (Ο) Notation

 Big-Omega (Ω) Notation
 Big-Theta(Θ) Notation

1. Big Oh (O) Notation

The formal notation for expressing the upper bound of an algorithm's execution time is O(n). It calculates the worst-
case time complexity, or the maximum time an algorithm can take to run.

Page | 13
www.ctuniversity.in
Think about the f(n) and g(n) functions, where f and g are defined on an unbounded set of positive real numbers. For
every big value of n, g(n) is always strictly positive.

The function f is said to be O(g) (read as big- oh of g), if, for a constant c>0 and a natural number n0, f (n) ≤ CG(n) for
all n >= n0. This can bw written as below

O(g(n)) = { f(n) : There exist positive constant c and n0 such that 0 ≤ f(n) ≤ c g(n), for all n ≥ n0 }

2. Big-Omega (Ω) Notation

The formal notation for expressing the lower bound of the execution time of an algorithm is Ω(n). It measures the best
case time complexity or the fastest possible time an algorithm may run.

We write f(n) = Ω(g(n)), If there are positive constants n0 and c such that, to the right of n0 the f(n) always lies on or
above c*g(n).

Ω(g(n)) = { f(n) : There exist positive constant c and n0 such that 0 ≤ c g(n) ≤ f(n), for all n ≥ n0 }

3. Big-Theta(Θ) Notation
The formal notation for expressing the lower and upper bounds of an algorithm's execution time is Θ(n). It express the
average case of an algorithm. It is displayed as follows:

Page | 14
www.ctuniversity.in
We write f(n) = Θ(g(n)), If there are positive constants n0 and c1 and c2 such that, to the right of n0 the f(n) always
lies between c1*g(n) and c2*g(n) inclusive.

Θ(g(n)) = {f(n) : There exist positive constant c1, c2 and n0 such that 0 ≤ c1 g(n) ≤ f(n) ≤ c2 g(n), for all n ≥ n0 }

Page | 15
www.ctuniversity.in