Data Structures Full Notes - Mumbai University (NEP 2020)
1. STACK
Definition:
A stack is a linear data structure which follows the LIFO (Last In First Out) principle.
Operations:
- push(x): Adds element x to the top of the stack.
- pop(): Removes the top element.
- peek()/top(): Returns the top element without removing it.
- isEmpty(): Checks if the stack is empty.
Implementation:
- Array-based: Uses a fixed-size array and a top pointer.
- Linked List-based: Uses nodes where insertions and deletions are done at the head.
Applications:
- Recursion and function call management
- Expression evaluation (infix to postfix, postfix evaluation)
- Undo mechanisms in software
- Backtracking (e.g., maze solving)
2. QUEUE
Definition:
A queue is a linear data structure that follows FIFO (First In First Out).
Operations:
- enqueue(x): Adds element x at the rear of the queue.
- dequeue(): Removes the front element.
- front(): Returns the front element.
Data Structures Full Notes - Mumbai University (NEP 2020)
- isEmpty(): Checks if the queue is empty.
Types of Queue:
- Simple Queue: Normal FIFO queue
- Circular Queue: Rear connects back to front to utilize empty space
- Deque: Double-ended queue, insertion and deletion from both ends
- Priority Queue: Each element has a priority; higher priority dequeued first
Applications:
- Job scheduling in OS
- Network packet management
- Printer queues
3. LINKED LIST
Definition:
A linked list is a linear data structure where each element is a node containing data and a reference to the
next node.
Types:
- Singly Linked List: Points to next node
- Doubly Linked List: Points to both next and previous nodes
- Circular Linked List: Last node points back to first
Operations:
- Insertion (beginning, middle, end)
- Deletion (by value or position)
- Traversal
Advantages:
- Dynamic size allocation
Data Structures Full Notes - Mumbai University (NEP 2020)
- Easier insertion/deletion compared to arrays
Disadvantages:
- No random access (O(n) to search)
- Extra memory for pointers
4. TREE
Definition:
A tree is a non-linear hierarchical data structure.
Binary Tree:
- Each node has at most 2 children
Binary Search Tree (BST):
- Left subtree has smaller values, right has greater
Tree Traversal:
- Inorder: Left, Root, Right (gives sorted order for BST)
- Preorder: Root, Left, Right
- Postorder: Left, Right, Root
Applications:
- Hierarchical data (file systems)
- Searching and sorting (BST)
- Expression trees
5. SEARCHING TECHNIQUES
Linear Search:
Data Structures Full Notes - Mumbai University (NEP 2020)
- Sequentially checks each element
- Time Complexity: O(n)
- No need for sorted data
Binary Search:
- Works on sorted data
- Repeatedly divides array in half
- Time Complexity: O(log n)
Comparison:
- Linear is simple but slow for large data
- Binary is fast but requires sorted input
Applications:
- Used in small or unsorted datasets (linear)
- Used in sorted large datasets (binary)
