UNIT 1:
INTRODUCTION TO DATA STRUCTURES
BY
MRS. SAVITA SAWANT
INTRODUCTION TO DATA STRUCTURES
Data is nothing but collection of raw facts and figures.
It is value or group of values which is in a particular
format.
While developing different types of applications, one has to
store such data in a standard format.
Only the storage of data is not sufficient, later on we have
to perform various operations on that data like insertion,
deletion, updation, traversing etc.
So, data must be stored in a systematic format, so one can
easily perform different operations on it.
All programming languages provide a set of built-in data
types such as int, float, char etc.
DEFINITION
Data structure is a way of collecting as well as organizing data
in such a way that various operations can be performed on it
in an efficient and effective way.
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.
NEED OF DATA STRUCTURE
Stores huge data
Stores data in systematic way
Retains logical relationship
Provides various structures like stack, queue,
linked list etc.
Static and dynamic formats
Better algorithms
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
There are basic structures and directly operated upon by
the machine instructions.
Data structures that are directly operated upon the
machine level instructions are known as primitive
data structures
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
There 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.
The design of an efficient data structure must take
operations to be performed on the data structure.
NON-PRIMITIVE DATA STRUCTURE
The most commonly used operation on data structure are
broadly categorized into following types:
Creation
Insertion
Traversing
Updating
Searching
Sorting
Merging
Destroy or Deletion
DIFFERENT BETWEEN THEM
A primitive data structure is generally a basic structure
that is usually built into the language, such as an integer,
a float.
A non-primitive data structure is built out of primitive
data structures linked together in meaningful ways, such
as a or a linked-list, binary search tree, AVL Tree, graph
etc.
CLASSIFICATION OF DATA
STRUCTURE
Static
Data Structures
Dynamic Data Structures
STATIC DATA STRUCTURE
The size of the structure is fixed.
It is possible to modify the structure of the DS
but without making changes in the memory
space allocated to it
Ex: Array
int a[9] = {10, 20, 30, 40, 50, 60, 70, 80, 90}
Array length = 9
First index = 0
Last index = 8
DYNAMIC DATA STRUCTURE
They are designed to facilitate change of DS in
the runtime.
It is possible to change the assigned values of
elements, as it was with static structures.
Also, in Dynamic Data Structure, the initially
allocated memory size is not a problem.
It is possible to add new elements, remove
existing elements or do any kind of operation on
data set without considering about the memeory
space allocated initially.
Ex: Linked List
ABSTRACT DATA TYPE (ADT)
An ADT is the way we look at a DS, focusing on
what it does and ignoring how it does it’s job.
The definition of ADT only mentions what
operations are to be performed but not how these
operations to be implemented.
The process of providing only the essentials and
hiding the details is known as abstraction.
Stack and queue are perfect examples of an ADT.
We can implement both these ADT’s using an
array or a linked list.
This demonstrates the abstract nature of stack
and queue.
DESCRIPTION OF VARIOUS DATA
STRUCTURES :
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
Simply, declaration of array is as follows:
int arr[10]
Where int specifies the data type or type of elements arrays
stores.
“arr” is the name of array & the number specified inside the
square brackets is the number of elements an array can store,
this is also called sized or length of array.
ARRAYS
Following are some of the concepts to be
remembered about arrays:
The individual element of an array can be
accessed by specifying name of the array,
following by index or subscript inside square
brackets.
The first element of the array has index zero[0].
It means the first element and last element will
be specified as: arr[0] & arr[9] respectively.
ARRAYS
Problem:
Given an array int a[] = {69, 78, 63, 98, 67, 75, 66,
90, 81}. Calculate address of a[5], if base address is
1600.
Solution:
Address of a[5] is given by,
= Base address + size of each element * 5
= 1600 + 2*5
= 1600 + 10
= 1610
ARRAYS
Problem:
Given an array int a[] = {23, 78, 34, 27, 65, 28, 42,
69, 84}. Calculate address of a[7], if base address is
8500.
Solution:
Address of a[7] is given by,
= Base address + size of each element * 7
= 8500 + 2*7
= 8500 + 14
= 8514
ARRAYS
The elements of array will always be stored in
the consecutive (continues) memory location.
The number of elements that can be stored in an
array, that is the size of array or its length is
given by the following equation:
(Upperbound-lowerbound)+1
For the above array it would be
(9-0)+1=10,where 0 is the lower bound of array
and 9 is the upper bound of array.
Array can always be read or written through
loop. If we read a one-dimensional array it
require one loop for reading and other for
writing the array
ARRAYS
For example: Reading an array
For(i=0;i<=9;i++)
scanf(“%d”,&arr[i]);
For example: Writing an array
For(i=0;i<=9;i++)
printf(“%d”,arr[i]);
ARRAYS
Some common operation performed on
array are:
Creation of an array
Traversing an array
Insertion of new element
Deletion of required element
Modification of an element
Merging of arrays
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.
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:
[Linear Liked List]
Head
AAA BBB CCC
Information field Pointer field
LISTS
Types of linked lists:
Singly linked list
Doubly linked list
Circular linked list
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:
PUSH POP
[STACK]
STACK
The stack can be implemented into two ways:
Using arrays (Static implementation)
Using pointer (Dynamic implementation)
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
QUEUE
The queue can be implemented into two ways:
Using arrays (Static implementation)
Using pointer (Dynamic
implementation)
TREES
A tree can be defined as finite set of data items (nodes).
Tree is non-linear type of data structure in which data
items are arranged or stored in a sorted sequence.
Tree represent the hierarchical relationship between
various elements.
TREES
In 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.
TREES
The tree structure organizes the data into branches,
which related the information.
A root
B C
D E F G
GRAPH
Graph is a mathematical non-linear data structure
capable of representing many kind of physical structures.
It has found application in Geography, Chemistry and
Engineering sciences.
Definition: A graph G(V,E) is a set of vertices V and a set
of edges E.
An edge connects a pair of vertices and many have
weight such as length, cost and another measuring
instrument for according the graph.
Vertices on the graph are shown as point or circles and
edges are drawn as arcs or line segment.
GRAPH
Example of graph:
6
v2 v5
v1 v3
10
v1 8 11
15
9 v2
v3 v4 v4
[a] Directed & [b] Undirected Graph
Weighted Graph
GRAPH
Types of Graphs:
Directedgraph
Undirected graph
Simple graph
Weighted graph
Connected graph
Non-connected graph
