DATA STRUCTURE
1.1 Introduction to Data
Data is simply a set of Values.
1.2.1 Data Structures
The logical or mathematical model of a particular
organization of data is called data structures.
the choice of data model depends on two considerations,
1. Rich enough in structure to mirror the actual relationship.
[Link] should be simple, can effectively process the data
whenever necessary.
Few examples of Data structures are array, lists,
binary,tree, etc.
1.2.2 Data Structures Operations
[Link]:- For processing certain items in records,each
record is accessed exactly once.
2. Searching:- Finding location of a record with given key
value or finding locations of all records,which satisfy one or
more conditions.
3. Inserting:- Adding a new record to the structure.
4. Deleting :- Removing a record from a structure.
5. Sorting:- Arranging the records in some order.
[Link]:- Combining the records in two different
sorted files into single sorted files.
1.3.1 Algorithmic Notations
An algorithm is a finite step by step list of well-defined
instructions for solving a particular problem.
The form for formal representation of an algorithm consists
of 2 parts:-
i) Tells about Purpose, identification, variables(which occurs in
algorithm) of the algorithm.
ii)Contains a list of steps that are to be executed.
There are certain conventions that have to be followed in
algorithms.
1. Step, Control, Exit ==>
There are 'n' numbers of steps in an algorithm that are
executed one after other beginning with step 1.
Sometimes Control may transfer the step directly to step 'n'
by using the statement 'goto step n'.
The algorithm is completed with the statement 'Exit'.
2. Comments ==>
It is given in brackets either at beginning or at the end
of the step.
It indicates the main purpose of the step.
3. Variables ==>
They are given in capital letters.
Used as Counters or Subscripts.
4. Input/Output
For input, read statement is used. ( read: variable
name)
For Output, Write/Print Statement is Used. (print:
variable names)
General structure of Algorithm:-
Here, write the purpose for writing the algorithm.
Step 1: Start.
Step 2: Declare three variables
.....
......
Step n: End.
1.3.2 Control Structure
Generally there are three types of logic used in algorithms
1. Sequence Logic => Modules(steps) are executed in some sequence.
The sequence is represented by means of numbered steps.
2. Selection Logic => Some Logic Employs a number of .
According which condition is satisfied that module is executed.
There are 3 types:-
Single alternatives=> This structure has the form 'IF' condition.
Double alternatives=>This Structures has the form 'IF' condition
then 'ELSE' condition.
Multiple alternatives=>This Structures has the form 'IF' condition
then 'ELSE IF' condition then 'ELSE' condition.
3. Iteration Logic=> These types of structures are called loops.
Here there are two types
1. Repeat for
[Link] while
1.4 Arrays
A linear Array is a list of finite numbers of same
(homogeneous) elements.
The elements of the array are stored respectively in
successive memory locations.
The Number n of elements is called length or size of the
array.
1.4.1 Traversing Linear Arrays.
Linear traversal is the process of visiting each element of an
array sequentially, starting from the first element and moving
to the last element. During this traversal, each element is
processed (printed, modified, or checked) one after the
other, in the order they are stored in the array.
1.4.2 Inserting Element in an Array
It means other elements to the linear array.
Inserting an element at the end in an linear array can be easily
done provided the memory space allocated for the array is
enough to accommodate additional elements.
But if we want to insert a element in the middle of the array,
then half of the arrays must be removed downward to new
locations.
1.4.3 Deleting of an Array
IT refers to the operation of removing one of the elements
from a linear array.
Deleting at an end of an array is simple but deleting
somewhere in the middle of the array would require that each
subsequent element be moved.
1.5 Bubble Sorting
Sorting means rearranging the elements in increasing or
decreasing order.
Step 1:- It involves n-1 comparisons.
During this step, the largest element is coming like a
bubble to the nth position.
When Step 1 is completed A[n] will contain the
largest Element { A is a linear array, and A[n] refers to nth
position of array A}
Step 2:- Repeat 1st Step with one less comparison i.e. n-2
comparison.
thus, when step 2nd completed we get the second largest.
Step N-1:- After n-1 step the list will be sorted in
increasing order.
Pass:- The process of sequentially traversing through all
parts is called as a pass.
Searching:- Searching refers to the operation of finding
the location of a given element in the list.
Commonly, linear search and binary search are used.
2.6 Linear Search
In linear search, the given element is compared with each
element of the list one by one.
The Method is also called as Sequential Search
2.7 Binary Search
While using this searching method, the array should be sorted
in increasing numerical order.
Applications:
1. This algorithm is used to search an ordered array.
2. To find out the target element whether it is present or not.
Limitations:
1. The Given list should be sorted in increasing numerical
order.
[Link] search relies on random access to elements, which is
readily available in arrays.
2.8 Pointer Arrays
An array whose each element is a pointer is called a pointer
array.
2.9 Record
A record isa collection of related data items.
Each data item is termed as a file.
File is a collection of similar records.
How to access data in records ?
==> Data can be accessed using dot operator as follows:
Suppose we want to know the last name of student then,
[Link]
Generally for separating subitems from group items dot is
used.
Representation of Records in memory:-
Records contain non-homogeneous data that can't be stored .
Some higher level languages have a in built record structure.
If these types of structures are not available then records
have to be stored in individual variables.
1.10 Linked Lists
Also known as One-Way list
It is a linear collection of data elements called nodes.
each node is divided into 2 parts:-
1. contains the information of the element.
2. contains the address of the next node in the list ( it is
known as link field).
Start is the pointer variable, which contains the address of
the first node.
The left part represents the information part of the node
while the right part represents the next pointer field of node.
The pointer of last node contains a special value called NULL,
Which is a invalid Address.
Representation of Linked List in Memory:-
1. LIST requires 2 arrays; we will call them here INFO and
LINK such that INFO[K] and LINK[K].
[Link] also requires a variable name such as START, which
contains the location of beginning of list and next pointer
sentinel, denoted by NULL, which indicates the end of list.
Advantages of Linked List:-
Lists are stored in the form of arrays.
But in arrays insertion and deletion is not easy.
also array size cant be easily increased.