UNIT 1

Data structures are the fundamental building blocks of computer programming.

They define how data is organized, stored, and manipulated within a program.
What is Data Structure?
The choice of a good data structure makes it possible to perform a variety of critical
operations effectively. An efficient data structure also uses minimum memory space
and execution time to process the structure. A data structure is not only used for
organising 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. So we must have good
knowledge of data structures.
Need Of Data Structure:
The structure of the data and the synthesis of the algorithm are relative to each other.
Data presentation must be easy to understand so the developer, as well as the user,
can make an efficient implementation of the operation.
Data structures provide an easy way of organising, retrieving, managing, and storing
data.
Here is a list of the needs for data.
 Data structure modification is easy.
 It requires less time.
 Save storage memory space.
 Data representation is easy.
 Easy access to the large database
Classification/Types of Data Structures:
1. Linear Data Structure
1. Non-Linear Data Structure.
Linear Data Structure:
 Elements are arranged in one dimension ,also known as linear dimension.
 Example: lists, stack, queue, etc.
Non-Linear Data Structure
 Elements are arranged in one-many, many-one and many-many dimensions.
 Example: tree, graph, table, etc.

1. Array:
An array is a collection of data items stored at contiguous memory locations. The
idea is to store multiple items of the same type together. This makes it easier to
calculate the position of each element by simply adding an offset to a base value,
i.e., the memory location of the first element of the array (generally denoted by the
name of the array).

2. Linked Lists:
Like arrays, Linked List is a linear data structure. Unlike arrays, linked list elements
are not stored at a contiguous location; the elements are linked using pointers.

Stack:
Stack is a linear data structure which follows a particular order in which the
operations are performed. The order may be LIFO(Last In First Out) or FILO(First
In Last Out). In stack, all insertion and deletion are permitted at only one end of the
list.

Stack Operations:
 push(): When this operation is performed, an element is inserted into the stack.
 pop(): When this operation is performed, an element is removed from the top of
the stack and is returned.
 top(): This operation will return the last inserted element that is at the top
without removing it.
 size(): This operation will return the size of the stack i.e. the total number of
elements present in the stack.
 isEmpty(): This operation indicates whether the stack is empty or not.
4. Queue:
Like Stack, Queue is a linear structure which follows a particular order in which the
operations are performed. The order is First In First Out (FIFO). In the queue, items
are inserted at one end and deleted from the other end. A good example of the queue
is any queue of consumers for a resource where the consumer that came first is
served first. The difference between stacks and queues is in removing. In a stack we
remove the item the most recently added; in a queue, we remove the item the least
recently added.

Queue Data Structure

Queue Operations:
 Enqueue(): Adds (or stores) an element to the end of the queue..
 Dequeue(): Removal of elements from the queue.
 Peek() or front(): Acquires the data element available at the front node of the
queue without deleting it.
 rear(): This operation returns the element at the rear end without removing it.
 isFull(): Validates if the queue is full.
 isNull(): Checks if the queue is empty.
5. Binary Tree:
Unlike Arrays, Linked Lists, Stack and queues, which are linear data structures, trees
are hierarchical data structures. A binary tree is a tree data structure in which each
node has at most two children, which are referred to as the left child and the right
child. It is implemented mainly using Links.
A Binary Tree is represented by a pointer to the topmost node in the tree. If the tree
is empty, then the value of root is NULL. A Binary Tree node contains the following
parts.
1. Data
2. Pointer to left child
3. Pointer to the right child

Binary Tree Data Structure

6. Binary Search Tree:
A Binary Search Tree is a Binary Tree following the additional properties:
 The left part of the root node contains keys less than the root node key.
 The right part of the root node contains keys greater than the root node key.
 There is no duplicate key present in the binary tree.
A Binary tree having the following properties is known as Binary search tree (BST).
11. Graph:
Graph is a data structure that consists of a collection of nodes (vertices) connected
by edges. Graphs are used to represent relationships between objects and are widely
used in computer science, mathematics, and other fields. Graphs can be used to
model a wide variety of real-world systems, such as social networks, transportation
networks, and computer networks.

Graph Data Structure

Applications of Data Structures:
Data structures are used in various fields such as:
 Operating system
 Graphics
 Computer Design
 Blockchain
 Genetics
 Image Processing
 Simulation,

What are Primitive Data Structures?

Primitive data structures are the most basic and fundamental types of data
provided by a programming language. They represent simple data types that are not
composed of other data types and serve as the basic building blocks for data
manipulation within the language.
Key Characteristics of Primitive Data Structures
1. Fundamental Types: Primitive data structures are built into the language and do
not need to be derived from other data structures. They are typically supported at the
lowest level of the language.
2. Simple Values: They represent single, simple values like an integer number, a
floating-point number, a character, or a boolean value.
3. Memory Efficiency: Because of their simplicity, they are highly efficient in terms
of memory usage.
4. Fixed Size: They have a fixed size, meaning the amount of memory they take up is
predefined and does not change at runtime.
5. Examples
 Integer: Represents whole numbers, such as int in Java or C++.
 Float/Double: Represents numbers with fractional parts. Float is for single
precision, and Double is for double precision.
 Character: Represents individual characters like 'A', 'b', '3', etc. It's usually denoted
as char in languages like C, C++, and Java.
 Boolean: Represents truth values, typically true or false.
 Byte: Represents a byte of data and is often used for raw binary data processing.
6. Direct Operation: Primitive data structures support direct operations like
arithmetic for numbers, logical operations for booleans, etc.
7. Value Types: In many languages, primitive types are value types, which
means variables of these types store the data directly rather than referring to the data
stored elsewhere.

What are Non-Primitive Data Structures?

Non-primitive data structures, also known as composite or reference data structures
are more complex than primitive data structures and are not built into the
programming language but rather are constructed using primitive data types and other
composite types. These structures are used to store and organize data in a more
sophisticated way, allowing for the management of large and complex sets of data.
Key Characteristics of Non-Primitive Data Structures
1. Complexity: Non-primitive data structures can hold multiple and diverse data
types. They are designed to store a collection of items and typically involve more
complex management of data.
2. Examples
 Arrays: A collection of elements, typically of the same data type, arranged in a
sequential order.
 Linked Lists: Consists of nodes where each node contains data and a reference (or
link) to the next node in the sequence.
 Stacks: Follows the Last In First Out (LIFO) principle. Operations are performed at
one end, called the top of the stack.
 Queues: Operate on the First In First Out (FIFO) principle. Elements are added at
the rear and removed from the front.
 Trees: A hierarchical structure with a root value and subtrees of children,
represented as a set of linked nodes.
 Graphs: Consist of nodes (vertices) that are connected by edges. Useful for
representing networks.
 Hash Tables: Store data in an associative manner. Data is accessed via a unique
key.
 Sets: A collection of distinct elements with no particular order.
3. Memory Allocation: Often allocated dynamically on the heap, which allows these
data structures to expand as needed during runtime.
4. Usage: Used for more complex data manipulations, such as storing large amounts
of data, performing complex algorithms, managing and indexing data efficiently, and
organizing data in hierarchical or networked structures.
5. Operations: Provide a wide range of operations like insertion, deletion, searching,
sorting, iterating over elements, etc.
Algorithms
An algorithm is basically a procedure of steps that we exactly follow to solve a particular
task or problem. We can say that it is a set of rules that we need to follow while
developing a program code during problem-solving. Furthermore, if we write an
algorithm before actually writing a code, it becomes easy to perform the coding part.
Moreover, the algorithm is in simple English language hence, others can also easily
understand it and develop the code.
Features of an algorithm
The features of an algorithm are as follows:
Clarity
The algorithm should be very clear and unambiguous in its meaning. It should be simple
so that one can understand it easily.
Well-defined inputs
A program may require to take input from the user. Therefore, the algorithm should
clearly define the inputs.
Well-defined outputs
The algorithm should clearly specify the output that the program will produce.
Finiteness
The algorithm should have a termination point. This means that the algorithm should not
be such that it runs infinite times or end up in loops.
Feasibility
The algorithm should be such that we can implement it easily. Hence, it should be
simple and practical to implement.
Language independent
It should be in simple English language. Since the code implementation should result in
the same output no matter which programming language we use while writing the code.
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 an 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(imp).
How to Design an Algorithm?
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.
1. The constraints of the problem must be considered while solving the problem.
1. The input to be taken to solve the problem.
1. The output is to be expected when the problem is solved.
1. The solution to this problem is within the given constraints.
Example
Algorithm to add 3 numbers and print their sum:
1. START
1. Declare 3 integer variables num1, num2, and num3.
1. Take the three numbers, to be added, as inputs in variables num1, num2, and
num3 respectively.
1. Declare an integer variable sum to store the resultant sum of the 3 numbers.
1. Add the 3 numbers and store the result in the variable sum.
1. Print the value of the variable sum
1. END

Row-Major and Column-Major Array Layouts

The elements of an array can be stored in column-major layout or row-major layout.
For an array stored in column-major layout, the elements of the columns are
contiguous in memory. In row-major layout, the elements of the rows are contiguous.
Array layout is also called order, format, and representation. The order in which
elements are stored can be important for integration, usability, and performance.
Certain algorithms perform better on data stored in a particular order.
Programming languages and environments typically assume a single array layout for
all data. MATLAB® and Fortran use column-major layout by default, whereas C and
C++ use row-major layout. With MATLAB Coder™, you can generate C/C++ code
that uses row-major layout or column-major layout. See Generate Code That Uses
Row-Major Array Layout.
Array Storage in Computer Memory
Computer memory stores data in terms of one-dimensional arrays. For example, when
you declare a 3-by-3 matrix, the software stores this matrix as a one-dimensional array
with nine elements. By default, MATLAB stores these elements with a column-major
array layout. The elements of each column are contiguous in memory.
Consider the matrix A:
A=
1 2 3
4 5 6
7 8 9
The matrix A is represented in memory by default with this arrangement:
1 4 7 2 5 8 3 6 9
In row-major array layout, the programming language stores row elements
contiguously in memory. In row-major layout, the elements of the array are stored as:
1 2 3 4 5 6 7 8 9
N-dimensional arrays can also be stored in column-major or row-major layout. In
column-major layout, the elements from the first (leftmost) dimension or index are
contiguous in memory. In row-major, the elements from the last (rightmost)
dimension or index are contiguous.
What is an Array?
An array is a type of linear data structure that is defined as a collection of elements
with same or different data types. They exist in both single dimension and multiple
dimensions. These data structures come into picture when there is a necessity to store
multiple elements of similar nature together at one place.

Basic terminologies of Array

 Array Index: In an array, elements are identified by their indexes. Array index
starts from 0.
 Array element: Elements are items stored in an array and can be accessed by
their index.
 Array Length: The length of an array is determined by the number of elements
it can contain.
Memory representation of Array
In an array, all the elements are stored in contiguous memory locations. So, if we
initialize an array, the elements will be allocated sequentially in memory. This
allows for efficient access and manipulation of elements.
Importance of Array
Assume there is a class of five students and if we have to keep records of their marks
in examination then, we can do this by declaring five variables individual and
keeping track of records but what if the number of students becomes very large, it
would be challenging to manipulate and maintain the data.
What it means is that, we can use normal variables (v1, v2, v3, ..) when we have a
small number of objects. But if we want to store a large number of instances, it
becomes difficult to manage them with normal variables. The idea of an array is to
represent many instances in one variable.
Basic Operations in Arrays
The basic operations in the Arrays are insertion, deletion, searching, display, traverse,
and update. These operations are usually performed to either modify the data in the
array or to report the status of the array.
Following are the basic operations supported by an array.
 Traverse − print all the array elements one by one.
 Insertion − Adds an element at the given index.
 Deletion − Deletes an element at the given index.
 Search − Searches an element using the given index or by the value.
 Update − Updates an element at the given index.
 Display − Displays the contents of the array.
Array - Insertion Operation
In the insertion operation, we are adding one or more elements to the array. Based on
the requirement, a new element can be added at the beginning, end, or any given index
of array. This is done using input statements of the programming languages.
Algorithm
Following is an algorithm to insert elements into a Linear Array until we reach the end
of the array −
1. Start
2. Create an Array of a desired datatype and size.
3. Initialize a variable 'i' as 0.
4. Enter the element at ith index of the array.
5. Increment i by 1.
6. Repeat Steps 4 & 5 until the end of the array.
7. Stop

Array - Deletion Operation

In this array operation, we delete an element from the particular index of an array.
This deletion operation takes place as we assign the value in the consequent index to
the current index.
Algorithm
Consider LA is a linear array with N elements and K is a positive integer such that
K<=N. Following is the algorithm to delete an element available at the Kth position of
LA.
1. Start
2. Set J = K
3. Repeat steps 4 and 5 while J < N
4. Set LA[J] = LA[J + 1]
5. Set J = J+1
6. Set N = N-1
7. Stop
Array - Search Operation
Searching an element in the array using a key; The key element sequentially compares
every value in the array to check if the key is present in the array or not.
Algorithm
Consider LA is a linear array with N elements and K is a positive integer such that
K<=N. Following is the algorithm to find an element with a value of ITEM using
sequential search.
1. Start
2. Set J = 0
3. Repeat steps 4 and 5 while J < N
4. IF LA[J] is equal ITEM THEN GOTO STEP 6
5. Set J = J +1
6. PRINT J, ITEM
7. Stop
Array - Traversal Operation
This operation traverses through all the elements of an array. We use loop statements
to carry this out.
Algorithm
Following is the algorithm to traverse through all the elements present in a Linear
Array
1 Start
2. Initialize an Array of certain size and datatype.
3. Initialize another variable ‘i’ with 0.
4. Print the ith value in the array and increment i.
5. Repeat Step 4 until the end of the array is reached.
6. End

Array - Update Operation

Update operation refers to updating an existing element from the array at a given
index.
Algorithm
Consider LA is a linear array with N elements and K is a positive integer such that
K<=N. Following is the algorithm to update an element available at the Kth position
of LA.
1. Start
2. Set LA[K-1] = ITEM
3. Stop

Array - Display Operation

This operation displays all the elements in the entire array using a print statement.
Algorithm
Consider LA is a linear array with N elements. Following is the algorithm to display
an array elements.
1. Start
2. Print all the elements in the Array
3. Stop
Linear Search
Linear Search is the method of finding an element in an array by sequentially
comparing with each element until a match is found or the whole list has been
searched.
Example

Given 15 boxes kept one after the other each containing a number inside it. The boxes
are indexed from 0 to 15.
You are assured that the number 42 is also kept in one of the box. You've to find the
box containing the number 42.
The boxes with the indexes look like this. The numbers inside the boxes are not
visible and any of these boxes can have 42 inside it.
How would you find which box contains 42?
You would use linear search by opening each box one-by-one and checking whether
that box contains 42 or not.
Here,
The best case would require checking only 1 box (1st element is 42): O(1)
The average case would require checking half of the boxes: O(n)
The worst case would require checking all the boxes: O(n)
Binary Search

In the above example, what if the numbers inside the box are sorted in ascending
order. Would you still check the boxes sequentially or can you optimize it?
We can have an optimization by checking the center box first and deciding whether to
check left or right. This will significantly reduce the number of boxes that we have to
check.
This algorithm is known as binary search.
Algorithm
Compute middleIndex using startIndex and endIndex
Compare required number with the middle element and return index if true
Else if required number is lesser than middle element, recur in the left half.
Else recur in the right half.
The base case is when number is found or no more elements to check.