Introduction to Data Structure

Introduction to Data Structure

 Computer is an electronic machine which is used for data processing and manipulation.
 When programmer collects such type of data for processing, he would require to store all of them in
computer’s main memory.
 In order to make computer work we need to know
o Representation of data in computer.
o Accessing of data.
o How to solve problem step by step.
 For doing this task we use data structure.

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
o Organization of Data
o Accessing methods
o Degree of associativity
o Processing alternatives for information
 Algorithm + Data Structure = Program
 Data structure study covers the following points
o Amount of memory require to store.
o Amount of time require to process.
o Representation of data in memory.
o Operations performed on that data.

Prof. Pradyumansinh Jadeja (9879461848) | 2130702 – Data Structure 1

 Introduction to Data Structure

Classification of Data Structure

DATA
STRUCTURE

PRIMITIVE NON
PRIMITIVE

INTEGER FLOATING CHARACTER POINTER ARRAY LIST FILE

POINT

LINEAR LIST NON

LINEAR LIST

STACK QUEUE GRAPH TREE

Data Structures are normally classified into two broad categories

1. Primitive Data Structure

2. Non-primitive data Structure

Data types
A particular kind of data item, as defined by the values it can take, the programming language used, or
the operations that can be performed on it.

Primitive Data Structure

 Primitive data structures are basic structures and are directly operated upon by machine instructions.
 Primitive data structures have different representations on different computers.
 Integers, floats, character and pointers are examples of primitive data structures.
 These data types are available in most programming languages as built in type.
o Integer: It is a data type which allows all values without fraction part. We can use it for whole numbers.
o Float: It is a data type which use for storing fractional numbers.
o Character: It is a data type which is used for character values.

Prof. Pradyumansinh Jadeja (9879461848) | 2130702 – Data Structure 2

 Introduction to Data Structure

Pointer: A variable that holds memory address of another variable are called pointer.

Non primitive Data Type

 These are more sophisticated data structures.
 These are derived from primitive data structures.
 The non-primitive data structures emphasize on structuring of a group of homogeneous or heterogeneous
data items.
 Examples of Non-primitive data type are Array, List, and File etc.
 A Non-primitive data type is further divided into Linear and Non-Linear data structure
o Array: An array is a fixed-size sequenced collection of elements of the same data type.
o List: An ordered set containing variable number of elements is called as Lists.
o File: A file is a collection of logically related information. It can be viewed as a large list of records
consisting of various fields.

Linear data structures

 A data structure is said to be Linear, if its elements are connected in linear fashion by means of logically or in
sequence memory locations.
 There are two ways to represent a linear data structure in memory,
o Static memory allocation
o Dynamic memory allocation
 The possible operations on the linear data structure are: Traversal, Insertion, Deletion, Searching, Sorting
and Merging.
 Examples of Linear Data Structure are Stack and Queue.
 Stack: Stack is a data structure in which insertion and deletion operations are performed at one end only.
o The insertion operation is referred to as ‘PUSH’ and deletion operation is referred to as ‘POP’ operation.
o Stack is also called as Last in First out (LIFO) data structure.
 Queue: The data structure which permits the insertion at one end and Deletion at another end, known as
Queue.
o End at which deletion is occurs is known as FRONT end and another end at which insertion occurs is
known as REAR end.
o Queue is also called as First in First out (FIFO) data structure.

Nonlinear data structures

 Nonlinear data structures are those data structure in which data items are not arranged in a sequence.
 Examples of Non-linear Data Structure are Tree and Graph.
 Tree: A tree can be defined as finite set of data items (nodes) in which data items are arranged in branches
and sub branches according to requirement.
o Trees represent the hierarchical relationship between various elements.
o Tree consist of nodes connected by edge, the node represented by circle and edge lives connecting to
circle.

Prof. Pradyumansinh Jadeja (9879461848) | 2130702 – Data Structure 3

 Introduction to Data Structure

 Graph: Graph is a collection of nodes (Information) and connecting edges (Logical relation) between nodes.
o A tree can be viewed as restricted graph.
o Graphs have many types:
 Un-directed Graph
 Directed Graph
 Mixed Graph
 Multi Graph
 Simple Graph
 Null Graph
 Weighted Graph

Difference between Linear and Non Linear Data Structure

Linear Data Structure Non-Linear Data Structure
Every item is related to its previous and next time. Every item is attached with many other items.
Data is arranged in linear sequence. Data is not arranged in sequence.
Data items can be traversed in a single run. Data cannot be traversed in a single run.
Eg. Array, Stacks, linked list, queue. Eg. tree, graph.
Implementation is easy. Implementation is difficult.

Operation on Data Structures

Design of efficient data structure must take operations to be performed on the data structures into account. The
most commonly used operations on data structure are broadly categorized into following types

1. Create
The create operation results in reserving memory for program elements. This can be done by declaration
statement. Creation of data structure may take place either during compile-time or run-time. malloc()
function of C language is used for creation.

2. Destroy
Destroy operation destroys memory space allocated for specified data structure. free() function of C
language is used to destroy data structure.

3. Selection
Selection operation deals with accessing a particular data within a data structure.

Prof. Pradyumansinh Jadeja (9879461848) | 2130702 – Data Structure 4

 Introduction to Data Structure

4. Updation
It updates or modifies the data in the data structure.

5. Searching
It finds the presence of desired data item in the list of data items, it may also find the locations of all
elements that satisfy certain conditions.

6. Sorting
Sorting is a process of arranging all data items in a data structure in a particular order, say for example,
either in ascending order or in descending order.

7. Merging
Merging is a process of combining the data items of two different sorted list into a single sorted list.

8. Splitting
Splitting is a process of partitioning single list to multiple list.

9. Traversal
Traversal is a process of visiting each and every node of a list in systematic manner.

Time and space analysis of algorithms

Algorithm

 An essential aspect to data structures is algorithms.

 Data structures are implemented using algorithms.

 An algorithm is a procedure that you can write as a C function or program, or any other language.

 An algorithm states explicitly how the data will be manipulated.

Algorithm Efficiency

 Some algorithms are more efficient than others. We would prefer to choose an efficient algorithm, so it
would be nice to have metrics for comparing algorithm efficiency.

 The complexity of an algorithm is a function describing the efficiency of the algorithm in terms of the
amount of data the algorithm must process.

 Usually there are natural units for the domain and range of this function. There are two main complexity
measures of the efficiency of an algorithm

 Time complexity

 Time Complexity is a function describing the amount of time an algorithm takes in terms of the
amount of input to the algorithm.

Prof. Pradyumansinh Jadeja (9879461848) | 2130702 – Data Structure 5

 Introduction to Data Structure

 "Time" can mean the number of memory accesses performed, the number of comparisons between
integers, the number of times some inner loop is executed, or some other natural unit related to the
amount of real time the algorithm will take.

 Space complexity

 Space complexity is a function describing the amount of memory (space) an algorithm takes in terms
of the amount of input to the algorithm.

 We often speak of "extra" memory needed, not counting the memory needed to store the input itself.
Again, we use natural (but fixed-length) units to measure this.

 We can use bytes, but it's easier to use, say, number of integers used, number of fixed-sized structures,
etc. In the end, the function we come up with will be independent of the actual number of bytes
needed to represent the unit.

 Space complexity is sometimes ignored because the space used is minimal and/or obvious, but
sometimes it becomes as important an issue as time.

Worst Case Analysis

In the worst case analysis, we calculate upper bound on running time of an algorithm. We must know the case
that causes maximum number of operations to be executed. For Linear Search, the worst case happens when
the element to be searched is not present in the array. When x is not present, the search () functions compares
it with all the elements of array [] one by one. Therefore, the worst case time complexity of linear search would
be.

Average Case Analysis

In average case analysis, we take all possible inputs and calculate computing time for all of the inputs. Sum all
the calculated values and divide the sum by total number of inputs. We must know (or predict) distribution of
cases. For the linear search problem, let us assume that all cases are uniformly distributed. So we sum all the
cases and divide the sum by (n+1).

Best Case Analysis

In the best case analysis, we calculate lower bound on running time of an algorithm. We must know the case
that causes minimum number of operations to be executed. In the linear search problem, the best case occurs
when x is present at the first location. The number of operations in worst case is constant (not dependent on n).
So time complexity in the best case would be.

Prof. Pradyumansinh Jadeja (9879461848) | 2130702 – Data Structure 6

 Linear Data Structure

Explain Array in detail

One Dimensional Array
 Simplest data structure that makes use of computed address to locate its elements is the one-
dimensional array or vector; number of memory locations is sequentially allocated to the vector.
 A vector size is fixed and therefore requires a fixed number of memory locations.
 Vector A with subscript lower bound of “one” is represented as below….

L0  L0 is the address of the first word allocated to the first element of

vector A.
 C words are allocated for each element or node
 The address of Ai is given equation Loc (Ai) = L0 + C (i-1)
L0 + (i-1)C
A [i]  Let’s consider the more general case of representing a vector A
whose lower bound for it’s subscript is given by some variable b.
The location of Ai is then given by Loc (Ai) = L0 + C (i-b)

Two Dimensional Array
 Two dimensional arrays are also called table or matrix, two dimensional arrays have two subscripts
 Two dimensional array in which elements are stored column by column is called as column major matrix
 Two dimensional array in which elements are stored row by row is called as row major matrix
 First subscript denotes number of rows and second subscript denotes the number of columns
 Two dimensional array consisting of two rows and four columns as above Fig is stored sequentially by
columns : A [ 1, 1 ], A [ 2 , 1 ], A [ 1 , 2 ], A [ 2 , 2 ], A [ 1 , 3 ], A [ 2 , 3 ], A [ 1, 4 ], A [ 2, 4 ]
 The address of element A [ i , j ] can be obtained by expression Loc (A [ i , j ]) = L0 + (j-1)*2 + i-1
 In general for two dimensional array consisting of n rows and m columns the address element A [ i , j ] is
given by Loc (A [ i , j ]) = L0 + (j-1)*n + (i – 1)
 In row major matrix, array can be generalized to arbitrary lower and upper bound in its subscripts,
assume that b1 ≤ I ≤ u1 and b2 ≤ j ≤u2

b1, b2 b1, u2
[1,1][1,2] [1,3] [ 1 ,m ] col 1 col 2 col 3 col 4

[2,1][2,2] [2,3] [2m] row 1 [ 1 , 1 ] [1,2] [1,3] [1,4]

row 2 [ 2 , 1 ] [2,2] [2,3] [2,4]
[n,1][n,2] [n,3] [n,m]
u1, b2

Row major matrix Column major matrix

No of Columns = m = u2 – b2 + 1

 For row major matrix : Loc (A [ i , j ]) = L0 + ( i – b1 ) *(u2-b2+1) + (j-b2)

Prof. Pradyumansinh Jadeja (9879461848) | 2130702 – Data Structure 1

 Linear Data Structure

Applications of Array
1. Symbol Manipulation (matrix representation of polynomial equation)
2. Sparse Matrix

Symbol Manipulation using Array

 We can use array for different kind of operations in polynomial equation such as addition, subtraction,
division, differentiation etc…
 We are interested in finding suitable representation for polynomial so that different operations like
addition, subtraction etc… can be performed in efficient manner
 Array can be used to represent Polynomial equation

 Matrix Representation of Polynomial equation

Y Y2 Y3 Y4
X XY X Y2 X Y3 X Y4
2 2 2 2 2 3
X X Y X Y X Y X2 Y4
X3 X3 Y X3 Y2 X3 Y3 X3 Y4
4
X X4 Y X4 Y2 X4 Y3 X4 Y4

e.g. 2x2+5xy+Y2 e.g. x2+3xy+Y2+Y-X

is represented in matrix form as below is represented in matrix form as below
Y Y2 Y3 Y4 Y Y2 Y3 Y4
0 0 1 0 0 0 0 1 0 0
X 0 5 0 0 0 X -1 3 0 0 0
2 2
X 2 0 0 0 0 X 1 0 0 0 0
X3 0 0 0 0 0 X3 0 0 0 0 0
4 4
X 0 0 0 0 0 X 0 0 0 0 0

 Once we have algorithm for converting the polynomial equation to an array representation and another
algorithm for converting array to polynomial equation, then different operations in array (matrix) will be
corresponding operations of polynomial equation

What is sparse matrix? Explain

 An mXn matrix is said to be sparse if “many” of its elements are zero.
 A matrix that is not sparse is called a dense matrix.
 We can device a simple representation scheme whose space requirement equals the size of the non-
zero elements.
Prof. Pradyumansinh Jadeja (9879461848) | 2130702 – Data Structure 2
 Linear Data Structure

 Example:-
o The non-zero entries of a sparse matrix may be mapped into a linear list in row-major order.
o For example the non-zero entries of 4X8 matrix of below fig.(a) in row major order are 2, 1, 6, 7,
3, 9, 8, 4, 5

0 0 0 2 0 0 1 0
0 6 0 0 7 0 0 3
0 0 0 9 0 8 0 0
0 4 5 0 0 0 0 0
Fig (a) 4 x 8 matrix

Terms 0 1 2 3 4 5 6 7 8
Row 1 1 2 2 2 3 3 4 4
Column 4 7 2 5 8 4 6 2 3
Value 2 1 6 7 3 9 8 4 5
Fig (b) Linear Representation of above matrix

 To construct matrix structure we need to record

(a) Original row and columns of each non zero entries
(b) No of rows and columns in the matrix
 So each element of the array into which the sparse matrix is mapped need to have three fields: row,
column and value
 A corresponding amount of time is saved creating the linear list representation over initialization of two
dimension array.

0 0 6 0 9 0 0
A= 2 0 0 7 8 0 4
10 0 0 0 0 0 0
0 0 12 0 0 0 0
0 0 0 0 0 0 0
0 0 0 3 0 0 5

 Here from 6X7=42 elements, only 10 are non zero. A[1,3]=6, A[1,5]=9, A[2,1]=2, A[2,4]=7, A[2,5]=8,
A[2,7]=4, A[3,1]=10, A[4,3]=12, A[6,4]=3, A[6,7]=5.
 One basic method for storing such a sparse matrix is to store non-zero elements in one dimensional
array and to identify each array elements with row and column indices fig (c).

ROW COLUMN A
1 1 3 6
2 1 5 9

Prof. Pradyumansinh Jadeja (9879461848) | 2130702 – Data Structure 3

 Linear Data Structure

3 2 1 2
4 2 4 7
5 2 5 8
6 2 7 4
7 3 1 10
8 4 3 12
9 6 4 3
10 6 7 5
Fig (c )

COLUMN A
1 3 6
ROW 2 5 9
1 1 3 1 2
2 3 4 4 7
3 7 5 5 8
4 8 6 7 4
5 0 7 1 10
6 9 8 3 12
9 4 3
10 7 5
ROW NO First Column
for row no COLUMN NO

Fig(d)

 A more efficient representation in terms of storage requirement and access time to the row of the
matrix is shown in fid (d). The row vector changed so that its ith element is the index to the first of the
column indices for the element in row I of the matrix.

Linked Representation of Sparse matrix

Typical node to represent non-zero element is

Row Column Value Pointer To

Number Number Next Node

1 3 6 1 5 9 2 1 2 2 4 7

2 5 8 2 7 4 3 1 10 4 3 12

6 4 3 6 7 5 NULL

Prof. Pradyumansinh Jadeja (9879461848) | 2130702 – Data Structure 4

 Linear Data Structure

Write algorithms for Stack Operations – PUSH, POP, PEEP

 A linear list which allows insertion and deletion of an element at one end only is called stack.
 The insertion operation is called as PUSH and deletion operation as POP.
 The most and least accessible elements in stack are known as top and bottom of the stack respectively.
 Since insertion and deletion operations are performed at one end of a stack, the elements can only be
removed in the opposite orders from that in which they were added to the stack; such a linear list is
referred to as a LIFO (last in first out) list.

 A pointer TOP keeps track of the top element in the stack. Initially, when the stack is empty, TOP has a
value of “one” and so on.
 Each time a new element is inserted in the stack, the pointer is incremented by “one” before, the
element is placed on the stack. The pointer is decremented by “one” each time a deletion is made from
the stack.

Applications of Stack
 Recursion
 Keeping track of function calls
 Evaluation of expressions
 Reversing characters
 Servicing hardware interrupts
 Solving combinatorial problems using backtracking.

Procedure : PUSH (S, TOP, X)

 This procedure inserts an element x to the top of a stack which is represented by a vector S containing N
elements with a pointer TOP denoting the top element in the stack.

Prof. Pradyumansinh Jadeja (9879461848) | 2130702 – Data Structure 5