Unit 1.
Introduction to Data Structure
Data structure
Data Structure is a particular way of storing and organizing information in a
computer so that it can be retrieved and used most productively.
Different kinds of data structures are meant for different kinds of applications, and
some are highly specialized to specific tasks.
Data structures are important for the following reasons:
1. Data structures are used in almost every program or software system.
2. Specific data structures are essential ingredients of many efficient algorithms,
and make possible the management of huge amounts of data, such as large
integrated collection of databases.
3. Some programming languages emphasize data structures, rather than algorithms,
as the key organizing factor in software design.
What is Data Structure?
Data structure is a representation of the logical relationship existing between
individual elements of data.
• Data Structure is a way of organizing all data items that considers not only
the elements stored but also
• their relationship to each other.
• We can also define data structure as a mathematical or logical model of a
particular organization of
• data items.
• The representation of particular data structure in the main memory of a
computer is called as storage
• structure.
• The storage structure representation in auxiliary memory is called as file
structure.
• It is defined as the way of storing and manipulating data in organized form
so that it can be used
• efficiently.
• Data Structure mainly specifies the following four things
• Organization of Data
• Accessing methods
• Degree of associativity
• Processing alternatives for information
• Algorithm + Data Structure = Program
Need of Data Structures
As applications are getting complexed and amount of data is increasing day by
day, there may arrise the following problems:
Processor speed: To handle very large amout of data, high speed processing is
required, but as the data is growing day by day to the billions of files per entity,
processor may fail to deal with that much amount of data.
Data Search: Consider an inventory size of 106 items in a store, If our application
needs to search for a particular item, it needs to traverse 106 items every time,
results in slowing down the search process.
Multiple requests: If thousands of users are searching the data simultaneously on
a web server, then there are the chances that a very large server can be failed
during that process
in order to solve the above problems, data structures are used. Data is organized to
form a data structure in such a way that all items are not required to be searched
and required data can be searched instantly.
Advantages of Data Structures
Efficiency: Efficiency of a program depends upon the choice of data structures.
For example: suppose, we have some data and we need to perform the search for a
perticular record. In that case, if we organize our data in an array, we will have to
search sequentially element by element. hence, using array may not be very
efficient here. There are better data structures which can make the search process
efficient like ordered array, binary search tree or hash tables.
Reusability: Data structures are reusable, i.e. once we have implemented a
particular data structure, we can use it at any other place. Implementation of data
structures can be compiled into libraries which can be used by different clients.
Abstraction: Data structure is specified by the ADT which provides a level of
abstraction. The client program uses the data structure through interface only,
without getting into the implementation details.
Data Structure Classification
Operations on data structure
1) Traversing: Every data structure contains the set of data elements. Traversing
the data structure means visiting each element of the data structure in order to
perform some specific operation like searching or sorting.
Example: If we need to calculate the average of the marks obtained by a student in
6 different subject, we need to traverse the complete array of marks and calculate
the total sum, then we will divide that sum by the number of subjects i.e. 6, in
order to find the average.
2) Insertion: Insertion can be defined as the process of adding the elements to the
data structure at any location.
If the size of data structure is n then we can only insert n-1 data elements into it.
3) Deletion: The process of removing an element from the data structure is called
Deletion. We can delete an element from the data structure at any random location.
If we try to delete an element from an empty data structure then underflow occurs.
4) Searching: The process of finding the location of an element within the data
structure is called Searching. There are two algorithms to perform searching,
Linear Search and Binary Search. We will discuss each one of them later in this
tutorial.
5) Sorting: The process of arranging the data structure in a specific order is known
as Sorting. There are many algorithms that can be used to perform sorting, for
example, insertion sort, selection sort, bubble sort, etc.
6) Merging: When two lists List A and List B of size M and N respectively, of
similar type of elements, clubbed or joined to produce the third list, List C of size
(M+N), then this process is called merging
o Time complexity: It is a way of representing the amount of time needed by
a program to run to the completion.
o Space complexity: It is the amount of memory space required by an
algorithm, during a course of its execution. Space complexity is required in
situations when limited memory is available and for the multi user system.
Abstract Data Types (ADT)
1. The Abstract data type is special kind of data type, whose behavior is
defined by a set of values and set of operations.
2. The keyword “Abstract” is used as we can use these data types, we can
perform different operations. But how those operations are working that is
totally hidden from the user. The ADT is made of with primitive data types,
but operation logics are hidden.
3. The definition of ADT only mentions what operations are to be performed
but not how these operations will be implemented.
4. It does not specify how data will be organized in memory and what
algorithms will be used for implementing the operations.
5. It is called “abstract” because it gives an implementation-independent view.
The process of providing only the essentials and hiding the details is known
as abstraction.
Difference Between Primitive and Non-Primitive Data Structure
Primitive data structure Non Primitive Data structure
Non-Primitive data structure is a data structure
Primitive data structure is the data structure that allows
that allows you to store multiple data type
you to store only single data type values.
values.
integer, boolean, character, float, etc. are some Array, Linked List, Stack, etc. are some examples
examples of primitive data structures. of non-primitive data structures.
Primitive data structure always contains some value i.e.
You can store a NULL value in the non-primitive
these data structures do not allow you to store NULL
data structures.
values.
The size of the primitive data structures is dependent on The size of the non-primitive data structure is
the type of the primitive data structure. not fixed.
Difference Between Linear Data structure and Non-Linear Data
Structure
Sr. Key Linear Data Structures Non-linear Data Structures
No.
Sr. Key Linear Data Structures Non-linear Data Structures
No.
Data Element In linear data structure, data In non-linear data structure,
Arrangement elements are sequentially data elements are
1 connected and each element hierarchically connected and
is traversable through a single are present at various levels.
run.
Levels In linear data structure, all In non-linear data structure,
2 data elements are present at a data elements are present at
single level. multiple levels.
Implementation Linear data structures are Non-linear data structures
complexity easier to implement. are difficult to understand
3
and implement as compared
to linear data structures.
Traversal Linear data structures can be Non-linear data structures
traversed completely in a are not easy to traverse and
4
single run. needs multiple runs to be
traversed completely.
Memory Linear data structures are not Non-linear data structures
utilization very memory friendly and are uses memory very efficiently.
5
not utilizing memory
efficiently.
Time Time complexity of linear data Time complexity of non-
6 Complexity structure often increases with linear data structure often
increase in size. remain with increase in size.
7 Examples Array, List, Queue, Stack. Graph, Map, Tree.
Complexity
Complexity in data structures refers to the analysis of how efficiently
operations on a data structure perform, particularly concerning the resources
consumed as the size of the input data grows. The two primary types of
complexity are:
• Time Complexity:
This measures the amount of time an algorithm takes to complete its operations (e.g.,
insertion, deletion, searching, sorting) as a function of the input size, typically denoted
by 'n'. It is usually expressed using Big O notation, which provides an upper bound on
the growth rate of the running time. Common time complexities include O(1)
(constant), O(log n) (logarithmic), O(n) (linear), O(n log n) (log-linear), O(n^2)
(quadratic), and O(2^n) (exponential).
• Space Complexity:
This measures the amount of memory or storage space an algorithm or data structure
requires to operate as a function of the input size 'n'. It includes both the memory
needed to store the data structure itself and any auxiliary space used by the algorithm
during its execution.
Importance of Complexity Analysis:
• Algorithm Comparison:
Complexity analysis allows for comparing the efficiency of different algorithms
designed to solve the same problem, helping in selecting the most optimal solution.
• Scalability Assessment:
It provides insight into how an algorithm or data structure will perform when dealing
with large datasets, indicating its scalability.
• Resource Management:
Understanding complexity helps in predicting resource requirements (time and
memory) for a given task, aiding in system design and optimization.
Factors Influencing Complexity:
• Input Size:
The most significant factor, as complexity is generally expressed in terms of 'n', the
size of the input.
• Specific Operations:
Different operations on a data structure (e.g., searching in a linked list versus a hash
table) can have vastly different complexities.
• Worst-Case, Average-Case, and Best-Case Scenarios:
Complexity can vary depending on the specific arrangement of input data, leading to
different analyses for these scenarios. The worst-case is often the most critical for
performance guarantees.
Recursion
Recursion in data structures is a programming technique where a function
calls itself, either directly or indirectly, to solve a problem. It is a powerful
method for breaking down complex problems into smaller, more manageable
subproblems that are identical in nature to the original problem.
Key Components of Recursion:
• Base Case:
This is the terminating condition that stops the recursion and prevents an infinite
loop. When the base case is met, the function returns a value without making further
recursive calls.
• Recursive Step:
In this part, the function calls itself with a modified input that moves closer to the base
case. The problem is broken down into a smaller instance, and the recursive call is
made to solve this smaller instance.
How Recursion Works (with respect to Data Structures):
Recursion is particularly well-suited for problems involving data structures that
have a self-similar or hierarchical nature. Examples include:
• Tree Traversal:
Algorithms like Inorder, Preorder, and Postorder traversals of binary trees naturally
lend themselves to recursion. A recursive function can visit a node and then
recursively call itself on its left and right children.
• Linked Lists:
Operations like traversing, searching, or reversing a linked list can be implemented
recursively by processing the current node and then recursively calling the function on
the next node.
• Graphs:
Depth-First Search (DFS) in graphs is a classic example of a recursive algorithm,
where the function explores a path as far as possible before backtracking.
Examples. Factorial of no
int fact(int n) {
// BASE CONDITION
if (n == 0)
return 1;
return n * fact(n - 1);
int main() {
printf("Factorial of 5 : %d\n", fact(5));
return 0;
Recursion Example Tower Of Hanoi:-
The Tower of Hanoi uses recursion by breaking the complex problem of
moving n disks into three simpler, repeating steps: recursively move the
top n-1 disks to the auxiliary peg, move the largest disk from the source to the
destination peg, and recursively move the n-1 disks from the auxiliary peg to
the destination peg. This process continues until the base case is reached,
where a single disk is moved directly from the source to the destination
Recursive Steps for Moving Disks
1. 1. Base Case:
If there is only one disk (n=1), move it directly from the source peg to the destination
peg.
2. 2. Recursive Step (n > 1):
• Move n-1 disks: Recursively move the top n-1 disks from the source peg to the
auxiliary peg, using the destination peg as a temporary holder.
• Move the largest disk: Move the nth (largest) disk from the source peg to the
destination peg.
• Move n-1 disks again: Recursively move the n-1 disks from the auxiliary peg to the
destination peg, using the source peg as a temporary holder.
Example: Moving 3 Disks (A to C using B)
1. Move disks 1 and 2 from A to B: (using C as auxiliary):
o Move disk 1 from A to C: (base case for this smaller problem).
o Move disk 2 from A to B .
o Move disk 1 from C to B .
2. Move disk 3 from A to C: (largest disk).
3. Move disks 1 and 2 from B to C: (using A as auxiliary):
o Move disk 1 from C to A .
o Move disk 2 from B to C .
o Move disk 1 from A to C
Static Data Structure vs Dynamic Data Structure
What is a Static Data structure?
In Static data structure the size of the structure is fixed. The content of the
data structure can be modified but without changing the memory space
allocated to it.
Example of Static Data Structures: Array
What is Dynamic Data Structure?
In Dynamic data structure the size of the structure is not fixed and can be
modified during the operations performed on it. Dynamic data structures are
designed to facilitate change of data structures in the run time.
Example of Dynamic Data Structures: Linked List
Difference Between Static Data Structure and Dynamic Data Structure
Aspect Static Data Structure Dynamic Data Structure
Memory Memory is allocated at
Memory is allocated at run-time
allocation compile-time
Size is fixed and cannot be Size can be modified during
Size
modified runtime
Memory Memory utilization may be Memory utilization is efficient as
utilization inefficient memory can be reused
Access time is faster as it Access time may be slower due to
Access
is fixed indexing and pointer usage
Arrays, Stacks, Queues, Lists, Trees (with variable size),
Examples
Trees (with fixed size) Hash tables
