DATA STRUCTURES – UNIT I & II NOTES
Study Material Style Notes
Prepared for: B.Tech Artificial Intelligence & Data Science
Course Code: 231CS32
Academic Year: 2025-2026
UNIT I – INTRODUCTION TO DATA STRUCTURES
1. Introduction
• Data structures are systematic ways of organizing, managing, and storing data to enable efficient
access and modification.
• They form the foundation of software development, algorithms, and real-world problem-solving.
2. Types of Data Structures
• Primitive: Integer, Float, Character, Boolean.
• Non-Primitive: Arrays, Lists, Stacks, Queues, Trees, Graphs.
• Linear: Data arranged sequentially (Array, List, Stack, Queue).
• Non-Linear: Data connected hierarchically or as networks (Trees, Graphs).
• Static vs Dynamic: Fixed size (Arrays) vs Flexible size (Linked Lists).
3. Need for Data Structures
• Efficient data storage, retrieval, and modification.
• Essential for algorithm optimization and performance.
• Required in databases, compilers, operating systems, and AI applications.
4. Applications of Data Structures
• Operating System: Process scheduling uses queues.
• Compiler Design: Parsing uses stacks.
• Artificial Intelligence: Graphs used in pathfinding (A* search).
• Databases: Trees for indexing (B-Trees, B+ Trees).
• Networking: Graphs for routing algorithms (Dijkstra’s, Bellman-Ford).
5. Basic Terminologies
• Data: Raw facts and figures.
• Record: Collection of related fields.
• File: Collection of records.
• Key: Attribute used for searching and identification.
6. Elementary Data Organizations
• Arrays: Contiguous memory, fixed size.
• Linked Lists: Dynamic memory allocation.
• Stacks: LIFO (Last In First Out).
• Queues: FIFO (First In First Out).
• Trees: Hierarchical structures.
• Graphs: Network representation.
7. Data Structure Operations
• Traversal: Visiting all elements.
• Insertion: Adding elements.
• Deletion: Removing elements.
• Searching: Finding elements.
• Sorting: Arranging elements.
• Merging: Combining structures.
UNIT II – LINEAR DATA STRUCTURES
1. Abstract Data Types (ADT)
• Definition: A mathematical model for data types where data and operations are defined
independently of implementation.
• Examples: Stack, Queue, List.
• Advantages: Abstraction, Modularity, Reusability.
2. List ADT
• A collection of ordered elements with operations like insertion, deletion, and traversal.
• Supports both array-based and linked implementations.
3. Array-based vs Linked List Implementations
• Array: Fast access, fixed size, memory contiguous.
• Linked List: Dynamic size, sequential access, extra memory for pointers.
4. Singly, Doubly & Circular Linked Lists
• Singly: Each node points to the next node.
• Doubly: Each node points to both next and previous nodes.
• Circular: Last node connects back to first node.
5. Stack ADT
• LIFO (Last In, First Out).
• Operations: PUSH (insert), POP (remove), PEEK (view top).
• Applications: Function calls, undo/redo, expression evaluation.
6. Queue ADT
• FIFO (First In, First Out).
• Operations: ENQUEUE (insert), DEQUEUE (remove).
• Applications: Process scheduling, printer queue.
7. Variants of Queue
• Circular Queue: End connects to front, efficient memory usage.
• Double-Ended Queue (Deque): Insert/Delete at both ends.
• Priority Queue: Elements served based on priority.
8. Applications of Queues
• Job scheduling in operating systems.
• Traffic management.
• Resource allocation in networks.
