DATA STRUCTURES

PROF. KALPESH KUBAL

DEPARTMENT OF COMPUTER SCIENCE
NIRMALA MEMORIAL FOUNDATION JUNIOR COLLEGE OF COMMERCE & SCIENCE
DEFINITION

 Data structure is representation of the logical

relationship existing between individual
elements of data.
 In other words, a data structure is a way of
organizing all data items that considers not
only the elements stored but also their
relationship to each other.
INTRODUCTION
 Data structure affects the design of both structural &
functional aspects of a program.
Program= Algorithm + Data Structure
 An algorithm is a set of instruction written to carry out
certain tasks & the data structure is the way of
organizing the data with their logical relationship
retained.
 To develop a program of an algorithm, we should
select an appropriate data structure for that algorithm.
 Therefore algorithm and its associated data structures
form a program.
BASIC TERMINOLOGIES

 Data − Data are values or set of values.

 Data Item − Data item refers to single
unit of values.
 Group Items − Data items that are
divided into sub items are called as Group
Items.
 Elementary Items − Data items that
cannot be divided are called as Elementary
Items.
BASIC TERMINOLOGIES
 Entity − An entity is that which contains certain
attributes or properties, which may be assigned
values.
 Entity Set − Entities of similar attributes form an
entity set.
 Field − Field is a single elementary unit of
information representing an attribute of an entity.
 Record − Record is a collection of field values of
a given entity.
 File − File is a collection of records of the entities
in a given entity set.
CLASSIFICATION OF DATA STRUCTURE

 Data structure are normally divided into two broad

categories:
 Primitive
Data Structure
 Non-Primitive Data Structure
 CLASSIFICATION OF DATA STRUCTURE

Data structure

Primitive DS Non-Primitive DS

Integer Float Character Pointer

 CLASSIFICATION OF DATA STRUCTURE

Non-Primitive DS

Linear List Non-Linear List

Array Queue Graph Trees

Link List Stack

PRIMITIVE DATA STRUCTURE

 These are basic structures and directly

operated upon by the machine instructions.
 In general, there are different
representation on different computers.
 Integer, Floating-point number, Character
constants, string constants, pointers etc,
fall in this category.
NON-PRIMITIVE DATA STRUCTURE

 These are more sophisticated data

structures.
 These are derived from the primitive data
structures.
 The non-primitive data structures
emphasize on structuring of a group of
homogeneous (same type) or
heterogeneous (different type) data items.
 Lists, Stack, Queue, Tree, Graph are
example of non-primitive data structures.
LINEAR DATA STRUCTURE
 Data structure where data elements are
arranged sequentially or linearly where each
and every element is attached to its previous
and next adjacent is called a linear data
structure.
 In linear data structure, single level is
involved. Therefore, we can traverse all the
elements in single run only.
 Linear data structures are easy to implement
because computer memory is arranged in a
linear way.
 Its examples are array, stack, queue, linked
list, etc.
NON-LINEAR DATA STRUCTURE
 Data structures where data elements are
not arranged sequentially or linearly are
called non-linear data structures.
 In a non-linear data structure, single level
is not involved. Therefore, we can’t traverse
all the elements in single run only.
 Non-linear data structures are not easy to
implement in comparison to linear data
structure.
 It utilizes computer memory efficiently in
comparison to a linear data structure.
 Its examples are trees and graphs.
 DIFFERENCE BETWEEN LINEAR & NON-
LINEAR DATA STRUCTURE
Linear Data Non-linear Data
[Link]
Structure Structure
In a linear data structure,
data elements are arranged In a non-linear data
in a linear order where each structure, data elements are
1.
and every element is attached attached in hierarchically
to its previous and next manner.
adjacent.
Whereas in non-linear data
In linear data structure,
2. structure, multiple levels are
single level is involved.
involved.
Its implementation is easy in While its implementation is
3. comparison to non-linear data complex in comparison to
structure. linear data structure.
 DIFFERENCE BETWEEN LINEAR & NON-
LINEAR DATA STRUCTURE

[Link]
Linear Data Non-linear Data
Structure Structure
In linear data structure, While in non-linear data
data elements can be structure, data elements can’t
4.
traversed in a single run be traversed in a single run
only. only.
While in a non-linear data
In a linear data structure,
structure, memory is utilized in
5. memory is not utilized in an
an efficient way.
efficient way.

Its examples are: array,

While its examples are: trees
6. stack, queue, linked list,
and graphs.
etc.
 DIFFERENCE BETWEEN LINEAR & NON-LINEAR DATA
STRUCTURE
Non-linear Data
[Link] Linear Data Structure
Structure
Applications of linear data
Applications of non-linear data
structures are mainly in
7. structures are in Artificial
application software
Intelligence and image processing.
development.
Non-linear data structures are
useful for representing complex
Linear data structures are
relationships and data
8. useful for simple data storage
hierarchies, such as in social
and manipulation.
networks, file systems, or
computer networks.
Performance is usually good
for simple operations like Performance can vary depending
adding or removing at the on the structure and the
9.
ends, but slower for operations operation, but can be optimized for
like searching or removing specific operations.
elements in the middle.
OPERATIONS ON DATA STRUCTURE
The most commonly used operation on data
structure are broadly categorized into
following types:
 Traversing
 Searching
 Insertion
 Deletion
 Sorting
 Merging
BASIC PROGRAMMING BLOCKS
ARRAYS

 An array is defined as a set of finite number of

homogeneous elements or same data items.
 It means an array can contain one type of data only,
either all integer, all float-point number or all character.
 ARRAYS

Creating an array in C and C++ programming languages −

 data_type array_name[array_size] = {elements separated

using commas}
or
 data_type array_name[array_size];
 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.
 Algorithm

 Step 1: Start

 Step 2: [Initialize variable ] Set i = size - 1

 Step 3: Repeat Step 4 and 5 While i >= pos-1

 Step 4: [Move ith element forward. ] set arr[i+1]

= arr[i]
 Step 5: [Decrease counter. ] Set i = i - 1

 Step 6: [End of step 3 loop. ]

 Step 7: [Insert element. ] Set arr[pos-1] = item

 Step 8: 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.
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
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 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.
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
LINKED LISTS

A lists (Linear linked list) can be defined as a

collection of variable number of data items.
 Lists are the most commonly used non-primitive
data structures.
 An element of list must contain at least two fields,
one for storing data or information and other for
storing address of next element.
 As you know for storing address we have a special
data structure of list the address must be pointer
type.
LINKED LISTS
 Technically each such element is referred to as a
node, therefore a list can be defined as a
collection of nodes as show bellow:

Head

AAA BBB CCC

Information field Pointer field

TYPES OF LINKED LIST
 Single linked list

 Doubly linked list

 Single circular linked list

 Doubly circular linked list
MEMORY REPRESENTATION OF LINKED LIST
Head
1005

I 1007 N 1009
D 1001 I 1003 A
1005 1007 1009 1001 1003
LINKED LIST INSERTION
LINKED LIST DELETION
STACK

A stack is also an ordered collection of

elements like arrays, but it has a special
feature that deletion and insertion of
elements can be done only from one end
called the top of the stack (TOP)
 Due to this property it is also called as last
in first out type of data structure (LIFO).
STACK

 It could be through of just like a stack of

plates placed on table in a party, a guest
always takes off a fresh plate from the top and
the new plates are placed on to the stack at
the top.
 It is a non-primitive data structure.
 When an element is inserted into a stack or
removed from the stack, its base remains
fixed where the top of stack changes.
STACK
 Insertion of element into stack is called PUSH
and deletion of element from stack is called
POP.
 The bellow show figure how the operations
take place on a stack:
INSERTION: PUSH()
 push() is an operation that inserts elements into
the stack.

 Algorithm
1 − Checks if the stack is full.
2 − If the stack is full, produces an error and exit.
3 − If the stack is not full, increments top to point
next empty space.
4 − Adds data element to the stack location, where
top is pointing.
5 − Returns success.
DELETION: POP()
 pop() is a data manipulation operation which
removes elements from the stack. The following
pseudo code describes the pop() operation in a
simpler way.

 Algorithm
1 − Checks if the stack is empty.
2 − If the stack is empty, produces an error and
exit.
3 − If the stack is not empty, accesses the data
element at which top is pointing.
4 − Decreases the value of top by 1.
5 − Returns success.
MEMORY REPRESENTATION OF STACK
STACK REPRESENTATION
 The stack can be represented into two ways:
QUEUE

 Queue are first in first out type of data

structure (i.e. FIFO)
 In a queue new elements are added to the
queue from one end called REAR end and the
element are always removed from other end
called the FRONT end.
 The people standing in a railway reservation
row are an example of queue.
 QUEUE

 Each new person comes and stands at the

end of the row and person getting their
reservation confirmed get out of the row
from the front end.
 The bellow show figure how the
operations take place on a stack:

10 20 30 40 50

front rear
REPRESENTATION OF QUEUE
QUEUE OPERATIONS

Original Queue
QUEUE
 The queue can be implemented into two ways:
 Using arrays (Static implementation)
 Using pointer (Dynamic
implementation)
LINEAR SAERCH

 Linear search is a very simple search algorithm.

 In this type of search, a sequential search is
made over all items one by one.
 Every item is checked and if a match is found
then that particular item is returned, otherwise
the search continues till the end of the data
collection.
LINEAR SEARCH ALGORITHM

 Linear Search ( Array A, Value x)

 Step 1: Set i to 1

 Step 2: if i > n then go to step 7

 Step 3: if A[i] = x then go to step 6

 Step 4: Set i to i + 1

 Step 5: Go to Step 2

 Step 6: Print Element x Found at index i and go

to step 8
 Step 7: Print element not found

 Step 8: Exit
BINARY SEARCH
 Binary Search is defined as a searching
algorithm used in a sorted array by repeatedly
dividing the search interval in half. The idea
of binary search is to use the information that the
array is sorted and reduce the time complexity to
O(log N).
BINARY SEARCH WORKING
BINARY SEARCH ALGORITHM

 do until the pointers low and high meet each

other.
 mid = (low + high)/2

 if (x == arr[mid])

 return mid
 else if (x > arr[mid]) // x is on the right side
 low = mid + 1
 else // x is on the left side
 high = mid - 1
BUBBLE SORT

 Bubble Sort is the simplest sorting

algorithm that works by repeatedly
swapping the adjacent elements if they are
in the wrong order.
 This algorithm is not suitable for large data
sets as its average and worst-case time
complexity is quite high.
 BUBBLE SORT WORKING
 In this algorithm, traverse from left and compare adjacent
elements and the higher one is placed at right side.
 In this way, the largest element is moved to the rightmost
end at first.
 This process is then continued to find the second largest
and place it and so on until the data is sorted.
BUBBLE SORT ALGORITHM
begin BubbleSort(list)

for all elements of list

if list[i] > list[i+1]
swap(list[i], list[i+1])
end if
end for

return list

end BubbleSort
TREES
A tree can be defined as finite set of data
items (nodes).
 Tree data structure is a collection of
data (Node) which is organized in
hierarchical structure recursively.
 Tree is non-linear type of data structure in
which data items are arranged or stored in
a sorted sequence.
TREES

 There is a special data item at the top of

hierarchy called the Root of the tree.
 The remaining data items are partitioned into
number of mutually exclusive subset, each of
which is itself, a tree which is called the sub
tree.
 The tree always grows in length towards
bottom in data structures, unlike natural trees
which grows upwards.
TREE EXAMPLE
 TREE TERMINOLOGY
1. Root
 The first node is called as Root Node.

 Every tree must have a root node.

 Root node is the origin of the tree data structure.

 In any tree, there must be only one root node.

 TREE TERMINOLOGY
2. Edge
 The connecting link between any two nodes is called
as EDGE.
 In a tree with 'N' number of nodes there will be a
maximum of 'N-1' number of edges.
 TREE TERMINOLOGY
3. Parent
 The node which is a predecessor of any node is called
as PARENT NODE.
 The node which has a branch from it to any other node is
also called a parent node.
 Parent node can also be defined as "The node which
has child / children".
 TREE TERMINOLOGY
4. Child
 The node which is descendant of any node is called
as CHILD Node.
 The node which has a link from its parent node is also
called as child node.
 In a tree, any parent node can have any number of child
nodes.
 In a tree, all the nodes except root are child nodes.
 TREE TERMINOLOGY
5. Siblings
 Nodes which belong to same Parent are called as
SIBLINGS.
 TREE TERMINOLOGY
6. Leaf
 The node which does not have a child is called as LEAF
Node.
 The leaf nodes are also called as External Nodes.

 External node is also a node with no child.

 Leaf node is also called as 'Terminal' node.

 TREE TERMINOLOGY
7. Internal Nodes
 The node which has atleast one child is called
as INTERNAL Node.
 The nodes other than leaf nodes are called as Internal
Nodes.
 The root node is also said to be Internal Node if the
tree has more than one node.
 Internal nodes are also called as 'Non-Terminal' nodes.
 TREE TERMINOLOGY
8. Degree
 The total number of children of a node is called
as DEGREE of that Node.
 The highest degree of a node among all the nodes in a
tree is called as 'Degree of Tree‘.
 TREE TERMINOLOGY
9. Level
 The root node is said to be at Level 0 and the children of
root node are at Level 1 and the children of the nodes
which are at Level 1 will be at Level 2 and so on...
 In a tree each step from top to bottom is called as a Level
and the Level count starts with '0' and incremented by
one at each level (Step).
 TREE TERMINOLOGY
10. Height
 The total number of edges from leaf node to a particular
node in the longest path is called as HEIGHT of that
Node.
 Height of the root node is said to be height of the tree.

 Height of all leaf nodes is '0'.

 TREE TERMINOLOGY
11. Depth
 The total number of egdes from root node to a
particular node is called as DEPTH of that Node.
 The total number of edges from root node to a leaf node
in the longest path is said to be Depth of the tree.
 Depth of the root node is '0'.
 TREE TERMINOLOGY
12. Path
 The sequence of Nodes and Edges from one node to
another node is called as PATH between that two
Nodes.
 Length of a Path is total number of nodes in that
path.
 In below example the path A - B - E - J has length 4.
 TREE TERMINOLOGY
13. Sub Tree
 Each child from a node forms a subtree recursively.

 Every child node will form a subtree on its parent node.

TREE REPRESENTATIONS
 BINARY TREE DATA STRUCTURE
 A binary tree is a special type of tree data structure in
which every node can have a maximum of 2 children.
 One is known as a left child and the other is known as
right child.
 In a binary tree, every node can have either 0 children
or 1 child or 2 children but not more than 2 children.
 TYPES OF BINARY TREES

1. Strictly Binary Tree

 A binary tree in which every node has either two or zero
number of children is called Strictly Binary Tree.
 Strictly binary tree is also called as Full Binary
Tree or Proper Binary Tree or 2-Tree.
 Strictly binary tree data structure is used to represent
mathematical expressions.
 TYPES OF BINARY TREES

2. Complete Binary Tree

 A binary tree in which every internal node has exactly
two children and all leaf nodes are at same level is
called Complete Binary Tree.
 At every level of complete binary tree, there must be
2level number of nodes.
 For example, at level 2 there must be 22 = 4 nodes and
at level 3 there must be 23 = 8 nodes.
 TYPES OF BINARY TREES

3. Extended Binary Tree

 The full binary tree obtained by adding dummy nodes to
a binary tree is called as Extended Binary Tree.
BINARY TREE REPRESENTATIONS
1. Array Representation
BINARY TREE REPRESENTATIONS
2. Linked List Representation
EXPRESSION TREE

 The expression tree is a binary tree in which each

internal node corresponds to the operator and
each leaf node corresponds to the operand.
EXPRESSION TREE EXAMPLE-1

a + (b * c) + d * (e + f)
EXPRESSION TREE EXAMPLE-2

a*b+c
EXPRESSION TREE EXAMPLE-3

a+b*c+d
EXPRESSION TREE EXAMPLE-4

a+b–c*d+e*f
EXPRESSION TREE EXAMPLE-5
3 + ((5+9)*2)