DATA STRUCTURES

BTAT1301 (or) BTST1301

Unit Details
Unit – I : Introduction to Data Structures

Unit – II : Stacks and Queues

Unit – III : Linked Lists

Unit – IV : Searching and Sorting

Unit – V : Trees and Graphs

Unit- I
Introduction to Data Structures:
1. Definition of Data Structures
2. Abstract Data Type
3. Classification of Data Structures
❖Linear
❖Non-Linear

4. Applications
5. Data Structure Operations:
❖Insertion
❖Deletion
❖Search
❖Traversal
Introduction to Data Structures
Definition:
❖ A data structure is a Specific way to store and organize data in a computer's memory so that these
data can be used efficiently.

❖ The data structure name indicates itself that organizing the data in memory.

❖ There are many ways of organizing the data in the memory as we have already seen one of the data
structures, i.e., array in C language.

❖ Array is a collection of memory elements in which data is stored sequentially, i.e., one after another.

❖ The data structure is a set of algorithms that we can use in any programming language to structure
the data in the memory.
Introduction to Data Structures
Data Type Data Structures
It tells about the type of data a variable can accept. It is a collection of data types

Data Types can only hold a particular value that is part Data Structure can have different kinds and types of
of the data data within one single object

Values can directly be assigned to the data type The data is assigned to the data structure object using
variables since data type already represents the type of some set of algorithms and operations like push, pop,
value that can be stored and so on.

For Data Types, there is no involvement of time Time complexity comes into play when working with
complexity since only type and nature of data is data structures as it mainly deals with manipulation
concern and execution of logic over stored data.

Examples: int, float, double Examples: Stacks, Queues, Tree

Introduction to Data Structures
Abstract Data Type:
❖ Data types are used to define or classify the type of values a variable can store in it.

❖ Moreover, it also describes the possible operations allowed on those values. For example, the integer data
type can store an integer value. Possible operations on an integer include addition, subtraction,
multiplication, modulo.

❖ Abstract data type (ADT) is a concept or model of a data type. Because of ADT, a user doesn’t have to
bother about how that data type has been implemented.

❖ Moreover, ADT also takes care of the implementation of the functions on a data type. Here, the user will
have predefined functions on each data type ready to use for any operation.

❖ ADT only mentions what operations are to be performed but not how these operations will be
implemented.

❖ It does not specify how data will be organized in memory and what algorithms will be used for
implementing the operations. It is called “abstract” because it gives an implementation-independent view.
Introduction to Data Structures

❖ The user of data type does not need to know how

that data type is implemented.

❖ For example, we have been using Primitive values

like int, float, char data types only with the
knowledge that these data type can operate and
be performed on without any idea of how they are
implemented.

❖ So a user only needs to know what a data type

can do, but not how it will be implemented.

❖ Think of ADT as a black box which hides the

inner structure and design of the data type.

❖ Now we will define three ADTs

namely List ADT, Stack ADT, Queue ADT.
Classification of Data Structure
❖ By using data structure, one can organize and process a very large amount of data in a relatively short
period.
Classification of Data Structure
❖ Linear data structure: In which data elements are arranged sequentially or linearly, where
each element is attached to its previous and next adjacent elements, is called a linear data
structure.

• Static data structure: Static data structure has a fixed memory size. It is easier to access
the elements in a static data structure. An example of this data structure is an array.

• Dynamic data structure: In the dynamic data structure, the size is not fixed. It can be
randomly updated during the runtime which may be considered efficient concerning the
memory (space) complexity of the code. Examples of this data structure are queue, stack,
etc.

❖ Non-linear data structure: Data structures where data elements are not placed sequentially or
linearly are called non-linear data structures.

❖ In a non-linear data structure, we can’t traverse all the elements in a single run
only. Examples of non-linear data structures are trees and graphs.
Linear Data Structure
Characteristics of Linear Data Structure:
❖ Sequential Organization: In linear data structures, data elements are arranged
sequentially, one after the other.

❖ Order Preservation: The order in which elements are added to the data structure is
preserved. This means that the first element added will be the first one to be accessed or
removed, and the last element added will be the last one to be accessed or removed.

❖ Fixed or Dynamic Size: Linear data structures can have either fixed or dynamic sizes.
Arrays typically have a fixed size when they are created, while other structures like linked
lists, stacks, and queues can dynamically grow or shrink as elements are added or removed.

❖ Efficient Access: Accessing elements within a linear data structure is typically efficient. For
example, arrays offer constant-time access to elements using their index.
Linear Data Structure
List of Linear Data Structures

Data Structure Mechanism

Arrays A collection of elements stored in contiguous memory locations.

Linked Lists collection of nodes, each containing an element and a reference to the
next node.

Stacks A collection of elements with Last-In-First-Out (LIFO) order

Queues A collection of elements with First-In-First-Out (FIFO) order

Linear Data Structure
Array:-
❖ An array is a collection of items of same data type stored at
contiguous memory locations.

Characteristics of Array Data Structure:

❖ Homogeneous Elements
❖ Contiguous Memory Allocation
❖ Zero-Based Indexing
❖ Random Access
Types of arrays:
1. One-Dimensional Array
❖ which consists of a single row of elements,
❖ All of the same data type
2. Two-Dimensional Array Operations:
1. Insertion
❖ It referred to as a matrix or 2D array
2. Deletion
❖ It is an array of arrays. It consists of rows and columns 3. Accessing Elements
3. Multi-Dimensional Array 4. Searching
❖ Arrays can have more than two dimensions, leading to
multi-dimensional arrays.
Linear Data Structure Types of Linked List:
Linked List:-
❖ It is a linear data structure which looks like a
Singly Linked List:
chain of nodes, where each node contains
a data field and a link to the next node in the
list.

❖ Unlike Arrays, Linked List elements are not

stored at a contiguous location. Doubly Linked Lists:

Common Features:
❖ Node: Each element in a linked list is
represented by a node, which contains two
components:
❖ Data: The actual data or value associated
with the element.
Circular Linked Lists:
❖ Next Pointer(or Link): A reference or pointer
to the next node in the linked list.

❖ Head: The first node in a linked list is called the

“head.” It serves as the starting point for Operations:
traversing the list. 1. Insertion
2. Deletion
❖ Tail: The last node in a linked list is called the
3. Accessing Elements
“tail.” 4. Searching
Linear Data Structure Example:-
❖ we can think of the stack
Stacks:- data structure as the pile of
plates on top of another
❖ A Stack is a linear data structure that follows the
principle of Last In First Out (LIFO). This means
1. Put a new plate on top
the last element inserted inside the stack is
removed first.
2. Remove the top plate
Common Features: ❖ And, if you want the plate at
❖ A stack follows the LIFO principle: Last In, First the bottom, you must first
Out -- the last inserted element will be the first to remove all the plates on
get removed. top.

❖ Insertion and deletion are allowed at one end Operations:

only, i.e., the 'top' of the stack.
❖Push: Add an element to the top of a stack

❖ The 'base' of the stack points to the first inserted ❖Pop: Remove an element from the top of a stack
element in the stack and the 'top' of the stack
points to the last inserted element.
❖IsEmpty: Check if the stack is empty
❖IsFull: Check if the stack is full
❖Peek: Get the value of the top element without
removing it
Linear Data Structure Example:-
❖ People waiting in line for a rail ticket form a queue
Queues:-
❖ Queue follows the First In First Out (FIFO) rule -
the item that goes in first is the item that comes
out first.
❖ A queue can be defined as an ordered list which
enables insert operations to be performed at one
end called REAR and delete operations to be
performed at another end called FRONT.

Characteristics:

❖ Queue can handle multiple data. Operations:

❖ Enqueue: Add an element to the end of the queue

❖ We can access both ends.
❖ Dequeue: Remove an element from the front of the
❖ Data can only place at the back of queue queue

❖ IsEmpty: Check if the queue is empty

❖ Data can only remove from the front of queue
❖ IsFull: Check if the queue is full
❖ They are fast and flexible.
❖ Peek: Get the value of the front of the queue without
removing it
Non - Linear Data Structure
❖ In which data elements are arranged in Characteristics of Non-Linear Data Structure
random order without forming a linear
structure. ❖ Non-linear data structures do not follow a
sequential order.

❖ Data elements are present at the

multilevel, for example, tree.
❖ Elements are stored in a hierarchical or a
network-based structure.
❖ Multiple runs are required to traverse
through all the elements completely.
Traversing in a single run is impossible
to traverse the whole data structure.
❖ These data structures allow efficient searching,
insertion, and deletion of elements.
❖ Each element can have multiple paths to
reach another element.

❖ Non-linear data structures are used to solve

❖ It utilizes computer memory efficiently complex problems where data cannot be
arranged in a linear manner.
❖ Examples: Trees and Graphs
Non - Linear Data Structure
Tree:-
❖ The tree is a non-linear data structure that is
comprised of various nodes.
❖ The nodes in the tree data structure are arranged in
hierarchical order.

❖ Each node has a parent node and zero or more child

nodes. The node that is present at the top of the
hierarchy is called the root node.

Terminologies related to Trees:-

Node : A node is a data item that is stored in a tree
data structure.
Edge : Two nodes in a tree data structure are
connected with the help of an edge.
Parent : A parent in a tree is defined as a node that
has one or more child nodes.
Child : A child is a node that is connected to a
parent node. Types of Tree:- Operations on
Root : The root node is the topmost node in a tree. Tree:-
Leaf : A leaf node in a tree data structure is a 1. Binary Tree
1. Insertion
node that does not have any child nodes.
Height : The height of a tree is the maximum 2. Binary Search Tree 2. Deletion
number of edges from the root node to any
leaf node. 3. Searching
3. AVL Tree
Depth : The depth of a node is the number of edges
from the root node to that node. 4. Traversal
4. Red Block Tree
Non - Linear Data Structure
Graph:-
❖ A graph is a non linear data structure that consists of a set of Types of Graph:-
vertices and a set of edges that connect them together.

❖ In a graph, vertices represent entities, while edges represent

the relationships between them. Graphs are used to represent
complex relationships between entities and are widely used in
computer science.

Terminologies related to Graph:-

Vertex: A vertex is a data item that is stored in a graph data
structure.

Edge: An edge is a connection between two vertices in a Undirected Graph Directed Graph
graph.

Degree: The degree of a vertex in a graph data structure is

defined as the number of edges connected to it.
Operations on
Weight: The weight of an edge is a numerical value that is Tree:-
assigned to the edge to represent the cost or distance
between the vertices. 1. Insertion

Path: A path is a sequence of edges that connects two 2. Deletion

vertices in a graph. 3. Searching
Weighted Graph
Cycle: A cycle is a path in a graph that starts and ends at 4. Traversal
the same vertex.
Applications of Data Structures
Array:-
Stack:-
❖ Storing and accessing data
✓ Browser history
✓ Used to store and retrieve data in a specific order
✓ Evaluation of Arithmetic Expressions
❖ Sorting
✓ used to sort data in ascending or descending order ✓ Backtracking
❖ Searching ✓ Delimiter Checking and parenthesis
✓ To be searched for specific elements checking
❖ Matrices ✓ Reverse a Data
✓ used to represent matrices in mathematical
computations ✓ Processing Function Calls

Linked List:- Queue:-

❖ List of songs in the music player ✓ Key press sequence on the keyboard
❖ Previous and Next web page URLs in a web browser ✓ CPU task scheduling
❖ The previous and next images in image viewer ✓ Network
❖ Switching between two applications is carried out by ✓ Multi programming
using “alt+tab” in windows and “cmd+tab” in mac book
✓ Shared resources
❖ In mobile phones, the newly entered contact details will
be placed at the correct alphabetical order
Applications of Data Structures
Tree:-
❖ File Systems : The file system of a computer is often represented as a tree. Each folder or
directory is a node in the tree, and files are the leaves.
❖ XML Parsing : Trees are used to parse and process XML documents. An XML document can
be thought of as a tree, with elements as nodes and attributes as properties
of the nodes.
❖ Database Indexing : Many databases use trees to index their data. The B-tree and its variations
are commonly used for this purpose.
❖ Compiler Design : The syntax of programming languages is often defined using a tree structure
called a parse tree. This is used by compilers to understand the structure of
the code and generate machine code from it.
❖ Artificial Intelligence : Decision trees are often used in artificial intelligence to make decisions
based on a series of criteria.

Graph:-
❖ Social media analysis : Used to identify trends, sentiment, and key influencers
❖ Network monitoring : Graphs can be used to monitor network traffic in real-time
❖ IoT : Used to identify patterns, optimize performance
❖ Autonomous vehicles : allowing them to navigate safely and efficiently
❖ Web Graphs : Used to connect URLs on the internet
Operations on Data Structure
Insertion: It is the operation which we apply on all the data-structures. Insertion
means to add an element in the given data structure. The operation of insertion is
successful when the required element is added to the required data-structure.

Deletion: It is the operation which we apply on all the data-structures. Deletion

means to delete an element in the given data structure. The operation of deletion is
successful when the required element is deleted from the data structure.

Searching: Searching means to find a particular element in the given data-

structure. It is considered as successful when the required element is found.
Searching is the operation which we can performed on data-structures like array,
linked-list, tree, graph, etc.

Traversing: Traversing a Data Structure means to visit the element stored in it. It
visits data in a systematic manner. This can be done with any type of DS.