Course Code: AI203

Course Name: Data Structures &

Algorithms

Prof. Pragati P. Patil

 Unit – I : Introduction to Data
Structures
• Primitive and non-primitive data structures,
• Operations on data structures, Algorithms,
• Abstract Data Types,
• Complexity Analysis
 Type of Data Structures
• A data structure is the portion of memory allotted for a
model, in which the required data can be arranged in a
proper fashion.
• The data structures are of two types or it can be broadly
classified into two types of data structures:
(i) Primitive data structure
(ii) Non-primitive data structure.
Type of Data Structures
 Primitive Data Structures
• Primitive Data Structures are the data structures consisting of the numbers and
the characters that come in-built into programs.
• These data structures can be manipulated or operated directly by machine-level
instructions.
• Primitive Data Structures are basic data structures provided by programming
languages to represent single values.
• Such as Integers, floating-point numbers, Real numbers, Characters, booleans and
pointers, and their corresponding storage representation.
• Programmers can use these data types when creating variables in their programs.
• For example, a programmer may create a variable say “z” and define it as a integer
data type. The variable will then store data as a number or integer.
 Classification of Data Structure
Data structure

Primitive DS Non-Primitive DS

Integer Float Character String

 Basic data types or primitive data
types
• Integer: It is a positive or negative number that does not contain any fractional part.
• Real: A number that contains the decimal part
• Boolean: It is a data type that can store one of only two values, usually these values
are TRUE or FALSE
• Character: It is any letter, number, punctuation mark or space, which takes up a
single unit of storage, usually a byte
• String: It is sometimes just referred to as ‘text’. Any type of alphabetic or numeric
data can be stored as a string: “Delhi City”, “30/05/2013” and “459.78” are all
examples of the strings. Each character within a string will be stored in one byte
using its ASCII code. The maximum length of a string is limited only by the
available memory.
 Non primitive data structure
• Non – primitive data structures are not defined by the
programming language, but are instead created by the
programmer.
• They are also called as the reference variables, since they
reference a memory location, which stores the data.
• These data structures are derived from the primitive data
structures. Examples: Array, Stack, Queues, Linked list,
Tree, Graphs and hash table.
Classification of Data Structure
 Linear Data Structures
• In linear data structure the elements are stored in
sequential order.
• Hence, they are in the form of a list, which shows the
relationship of adjacency between elements and is said to
be linear data structure.
• The most, simplest linear data structure is a 1-D array, but
because of its deficiency, list is frequently used for
different kinds of data
 Linear Data Structures - Array
• Array: The Array is a collection of data of same data type stored in
consecutive memory location and is referred by common name.
• Array can contain one type of data only, either all integer, all float-
point number or all character.
• Simply, declaration of array : 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.
Linear Data Structures - 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).
 Linear Data Structures - Stack
• Stack: A stack is a Last-In-First-Out or First-In-Last-Out linear data structure in
which insertion and deletion takes place at only from one end called the top of the
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).
• Example : 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.
 Linear Data Structures - Stack
• Insertion of element into
stack is called PUSH and
deletion of element from
stack is called POP.
• The figure how the operations
take place on a stack:
 Linear Data Structures - Queue
• Queue: A Queue is a First-In-First-Out or Last-In-Last-Out data
structure in which insertion takes place from one end called the
rear and the deletions takes place at one end called the Front.
• 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.
 Linear Data Structures - 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 figure how the operations take place on a queue.
• Enqueue(): Adds (or stores) an element to the end of the queue..
• Dequeue(): Removal of elements from the queue.

front rear
 Linear Data Structures - List
• 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.
• Technically each such element is referred
to as a node, therefore a list can be defined
as a collection of nodes as show below:
 Linear Data Structures - List
• Linked List: Linked list is a collection of data of same type but the data items need not be
stored in consecutive memory locations. It is linear but non-contiguous type data structure.
A linked list may be a single list or double list.
• The element contains a data item and a link or reference to the subsequent item on the same
list. This is why they are most preferred when one has to handle dynamic data elements.
• Types of linked lists:
• Single linked list - A single list is used to traverse among the nodes in one direction.
• Doubly linked list - A double linked list is used to traverse among the nodes in both the
directions.
• Single circular linked list - Each node has a pointer to the next node, and the last node
points back to the first node. This forms a circle, and the list can only be traversed in one
direction.
• Doubly circular linked list - Each node has pointers to both the next and previous nodes. The
last node points to the first node, and the first node points to the last node.
 Non-linear data structure
• In non linear data structure the elements are stored based
on the hierarchical relationship among the data.
• A list, which doesn’t show the relationship of adjacency
between elements, is said to be non-linear data structure.
 Non-linear data structure - Tree
• Tree: This data structure is used to represent data that has some
hierarchical relationship among the data elements. Thus, it maintains
hierarchical relationship between various elements.
• A tree uses a node-like structure to make a hierarchical form and each
node here represents a value.
• The root node is the uppermost node of the tree and the leaf node is the
node at the bottom of the tree.
• This data structure imposes a rule that nodes of a tree do not create
loops in the data structure. A tree is used for indexing databases,
scanning, parsing, and generating code in compiler design, in routers in
computer networks, social networking sites, etc.
 Non-linear data structure - Tree
• Tree: tree is a hierarchical data structure
that consists of nodes connected by edges.
It is a non-linear data structure that
represents a parent-child relationship
between nodes.
• A tree has a root node, which is the topmost
node and has no parent. Each node in the
tree can have zero or more child nodes.
• A node with no children is called a leaf
node. The depth of a node is the number of
edges from the root node to that node. The
height of the tree is the maximum depth of
any node in the tree.
 Non-linear data structure –
Graph
• Graph data structure is used to represent data that has relationship between pair of
elements not necessarily hierarchical in nature.
• It maintains random relationship or point-to-point relationship between various elements.
• 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.
• It consists of a set of vertices (also known as nodes) and a set of edges, which connect
pairs of vertices. The vertices represent the objects, and the edges represent the
relationships between the objects.
• Graphs can be used to model a wide variety of real-world systems, such as social
networks, transportation networks, and computer networks. Eg. electrical and
communication networks, airline routes, flow chart and graphs for planning projects.
 Non-linear data structure – Graph
• Graphs can be either directed or undirected, depending on whether the
relationships represented by the edges have a direction. In a directed
graph, the edges have a direction and are called arcs, while in an
undirected graph, the edges have no direction and are simply called
edges.

Undirected
Graph
Directed
Graph