Data Structures and Algorithms
Introduction - Basic Data Structures
What is Data?
• Data is information optimized for processing and movement, facts and
figures stored on computers.
Need for Data Structure
• Imagine a library without a filing system. Finding a specific book
would be a nightmare.
• Data structures are like the filing system for computer programs,
organizing information for efficient storage, retrieval, and
manipulation.
Unorganized Data Organized Data
Data Structure:
A data structure is a specialized format for organizing, processing,
retrieving and storing data.
• It is a way of arranging data on a computer so that it can be accessed
and updated efficiently.
• The idea is to reduce the space and time complexities of different tasks.
A data structure should be seen as a logical concept that must address
two fundamental concerns.
1. First, how the data will be stored
2. Second, what operations will be performed on it
Importance of Data Structure:
Data structures are the foundation of efficient programs. They
play a crucial role in:
• Efficient storage and retrieval of
data
• Improved performance
• Better problem solving
• Abstraction
• Reusability
Classification of Data Structure:
LIFO (Last In First Out
FIFO (First In First Out
Linear Data Structure:
• Linear Data Structures are a type of data structure in computer science
where data elements are arranged sequentially or linearly.
• Each element has a previous and next adjacent, except for the first and
last elements.
• Example: Array, List, Stack, Queue, etc.
Characteristics of Linear DS:
1. Sequential Organization
2. Order Preservation
3. Fixed or Dynamic Size
4. Efficient Access
Non-linear Data Structure:
• A non-linear data structure is a type of data structure where elements
are not arranged sequentially or in a linear order.
• They are organized in a hierarchical or interconnected manner,
forming complex relationships between elements.
• Example: Tree, Graph, etc.
Characteristics of Non-Linear DS:
1. Hierarchical Structure
2. Dynamic Relationships
3. Efficient Data Retrieval
4. Non-contiguous Memory Allocation
Applications of Data Structure:
Data structures are used in various
fields such as:
• Operating system
• Graphics
• Computer Design
• Blockchain
• Genetics
• Image Processing
Data Structure Types:
Data Structure is used to reduce complexity of the code.
It can be of two types :
1. Static Data Structure
2. Dynamic Data Structure
Dynamic Arrays
• Dynamic arrays are arrays that can automatically resize themselves when
elements are added or removed.
• They provide flexibility for handling a varying number of elements efficiently.
Static Arrays Dynamic Arrays
Fixed size Flexible size
Memory allocated at compile- Memory allocated at runtime
time
Example: Example:
int arr[10]; int* arr = new int[initialSize];
Dynamic Array
malloc
ptr = (cast_type *) malloc(size_in_bytes);
calloc
ptr = (cast-type*)calloc(n, element-size);
realloc
ptr = realloc(ptr, newSize);
Dynamic Array - Example
Static Data Structure vs Dynamic Data Structure
Aspect Static DS Dynamic DS
Size is fixed and cannot be Size can be modified during
Size
modified runtime
Access time is faster as it is Access time may be slower due to
Access
fixed indexing and pointer usage
Memory is allocated at
Memory allocation Memory is allocated at run-time
compile-time
Array Lists, Trees (with variable size),
Examples
Hash tables
Abstract Data Type:
Abstract data types (ADTs) are a way of encapsulating data and operations on
that data into a single unit
• The user does not need to know the
implementation of the data structure only
essentials are provided.
• ADT gives us a better conceptualization of the
real world.
• The program is robust and has the ability to
catch errors.
