UNIT-1
INTRODUCTION TO DATA STRUCTURE
AND ARRAY
Data Structure :
• A data structure is a specialized format for organizing, managing, and
storing data in a way that allows efficient access and modification
• It defines how data is arranged in memory and how the operations like
insertion, deletion, retrieval, and traversal are performed on that data.
Key aspects of data structures:
• Organization: Data structures define how data is arranged and
related to each other, allowing for efficient access and manipulation.
• Storage: They provide a method for storing data in the computer's
memory.
• Efficiency: The choice of data structure impacts the performance of
algorithms and programs, especially in terms of time and space
complexity.
Types Of Data Structure :-
Data
Structure
Non-
Primitive
Primitive
Boolean Linear Non-
Integer Float character
Linear
Tree Graph
Static Dynamic
Linked
Array Stack Queue
list
Primitive Data Structure :
• Also known as built-in-data type
• It is pre defined in language
1. Integer:
• Stores whole numbers (positive, negative, or zero).
• Example: int x = 10;
2. Float:
• Used to store real numbers (with decimal points).
• Example: float f = 3.14;
3. Character:
• Holds a single character.
• Example: char c = 'A';
4. Boolean:
• Stores true or false values.
Non-Primitive Data Structure :
1. Linear Data Structures:
These data structures store data in a sequential manner,
where elements are arranged one after the other.
Types of Linear Data Structures:
a) Array:
A collection of elements of the same data type stored in contiguous
memory locations.
Example: int arr[5] = {10, 20, 30, 40, 50};
b) Linked List:
A sequence of nodes where each node contains data and a reference (or
pointer) to the next node.
Example: Node -> Node -> Node
c) Stack:
• A linear data structure that follows the LIFO (Last
In, First Out) principle.
• Elements are added and removed from the top of
the stack.
Example: Pushing and popping books on a stack.
d) Queue:
• A linear data structure that follows the FIFO (First
In, First Out) principle.
• Elements are added at the rear and removed from
the front.
Example: People standing in a queue to buy tickets.
2. Non-Linear Data Structures:
These data structures do not store elements sequentially. Instead, they
organize data in a hierarchical way.
Types of Non-Linear Data Structures:
a) Tree:
A hierarchical data structure consisting of nodes. Each node contains data
and references to its child nodes.
Example: Family tree, file system.
b) Graph:
A collection of nodes (vertices) connected by edges. It is used to
represent relationships between data points.
Example: Social network graph, road maps.
Difference between linear and non-linear data
structure
Linear data structure Non-linear data structure
• Elements are stored • Elements are stored
sequentially. hierarchically or
• Uses contiguous non-contiguous interconnected.
memory. • Non-contiguous memory
• Access elements one by one. allocation.
Array, stack, queue, linked list. • Access/traversed in multiple
paths.
• Each connected to One
• Each element can be
element(linear) ex. Array,
connected to multiple
stack ,queue.
elements. ex Tree, graph.
Algorithm :
• An algorithm is just a set of steps that you follow to solve a problem
or complete a task.
• Example: an algorithm to add two numbers.
• Step1. Start
• Step2. Input the first number as num1
• Step3. Input the second number as num2
• Step4. Add num1 and num2 and store the result in sum.
• Step5. Display the value of sum.
• Step6. End
Algorithm complexity :
• Complexity of an algorithm refers to the measure of the time that it
will need to execute and get the expected output, and the Space it
will need to store all the data (input, temporary data, and output).
• Hence these two factors define the efficiency of an algorithm.
• Therefore the complexity of an algorithm can be divided into two
types:
• Time Complexity: How long an algorithm takes to run .
• Space Complexity: How much memory an algorithm uses.
• Asymptotic Notations are used to express the complexity
(time or space) of an algorithm — especially when the input
size (n) becomes large.
• They help us analyze and compare algorithms when input size
becomes very large.
Asymptotic Notation :
• Asymptotic notation helps us understand how fast an algorithm
gets slower as the input (data) gets bigger.
• Instead of focusing on the exact time an algorithm takes, it gives a
general idea about how the time grows with larger inputs.
1. Big-O Notation (O) :
• The notation (n) is the formal way to express the upper bound of an
algorithm's running time. is the most commonly used notation.
• It measures the worst case time complexity or the longest amount
of time an algorithm can possibly take to complete.
• A function f(n) is said to be in the order of g(n), written as:
• f(n) = O(g(n))
• if there exist positive constants c and n₀ such that:
• f(n)⩽c.g(n) , for n>n0 in all case
• (c is just a number that makes g(n) big enough to cover f(n) for large
values of n.)
• Hence, function g(n) is an upper bound for function f(n), as g(n)
grows faster than f(n).
nn00
2. Omega Notation (Ω):
• Tells you the best-case scenario.
• It shows the minimum time the algorithm will take.
• If an algorithm takes Ω(n), the fastest it will run, even with the best
input, is proportional to n.
Example
• Let us consider a given function, f(n)=4.n3+10.n2+5.n+1.
• Considering g(n)=n3
• f(n)⩾4.g(n)
• for all the values of n>0.
• Hence, the complexity of f(n) can be represented as Ω(g(n)), i.e.
Ω(n3)
3. Theta Notation (Θ):
• Tells you the average-case scenario.
• It shows that the time will grow exactly at a certain rate
• We say that f(n)=Ω(g(n))
• when there exists constant c that f(n)⩾c.g(n) , for all large
value of n.
• We say that f(n)=θ(g(n))
• when there exist constants c1 and c2 that c1.g(n) ⩽f(n) ⩽c2.g(n)
• for all sufficiently large value of n. Here n is a positive integer.
Example :
• Let us consider a given function, f(n)=4.n3+10.n2+5.n+1
• Considering g(n)=n3, 4.g(n)⩽f(n)⩽5.g(n) for all the large values of n.
• Hence, the complexity of f(n) can be represented as θ(g(n)), i.e. θ(n 3)
Array(Linear Structure) :
• In data structures, an array is a collection of elements stored at
contiguous memory locations.
• Each element in the array can be accessed using an index, with the
first element being at index 0.
• Declaration & initialization of an array-
dataType arrayName[size]={1,2,3,4,5};
• Examples:
int arr[5] = {1, 2, 3, 4, 5};
If you omit the size, the compiler can count it for you:
dataType arrayName[]={1,2,3,4,5};
int arr[] = {1, 2, 3, 4, 5}; // Size is automatically 5
• int arr[5]; // Fixed size array created now input can be taken from
user
Traversing Linear Array
• Traversing a linear array means accessing each element of
the array one by one.
• It allows you to inspect or use each element in the array.
Use Of Traversing :
• Printing all elements.
• Modifying or updating each element (e.g. multiplying all
values by 2).
• Counting how many elements meet a condition (e.g. how
many numbers are even).
• Summing all elements in the array.
Algorithm Using For Loop
Step 1: Start - Begin the process.
Step 2: Initialize - Let n be the total number of elements
in the array. Initialize the array arr[] with n elements.
Step 3: Traverse using a for loop - For i = 0 to n - 1
(i.e., start from the first element and go until the last
element):
• Access the element at index i (arr[i]).
• Perform any required operation on the element (like
printing or processing).
Step 4: End the process after all elements have been
traversed.
Step 5: Stop
• PROGRAM-In Text Editor