Table of Contents
What You'll Learn
- Core concepts of Stack, Queue, Linked List, Trees, and Graphs
- Python implementations with working code examples
- Real-world applications and use cases
- Time and space complexity analysis
- CBSE Class 12 exam preparation tips for data structures
- Common interview questions and answers
Introduction to Data Structures
Data Structures are specialized formats for organizing, storing, and managing data efficiently. They form the foundation of computer science and enable efficient data manipulation for various operations like searching, sorting, inserting, and deleting.
Think of data structures as containers that hold data in specific ways to make certain operations faster or more efficient. Just like you organize your bookshelf differently than your wardrobe, different types of data require different organizational structures.
Types of Data Structures:
- Linear Data Structures: Elements arranged sequentially (Arrays, Lists, Stacks, Queues, Linked Lists)
- Non-Linear Data Structures: Elements arranged hierarchically or networked (Trees, Graphs)
- Static Data Structures: Fixed size (Arrays)
- Dynamic Data Structures: Size can change (Linked Lists, Stacks, Queues)
Why Data Structures Matter
Understanding data structures is crucial for several reasons:
- Efficiency: Proper data structure choice can reduce time complexity from O(n²) to O(log n) or even O(1)
- Problem Solving: Many real-world problems have optimal solutions using specific data structures
- Interview Success: Tech interviews heavily focus on data structures and algorithms
- Better Code: Writing organized, maintainable, and scalable code
- System Design: Essential for designing databases, operating systems, compilers, and network protocols
Stack - LIFO (Last In First Out) Principle
A Stack is a linear data structure where elements are added and removed from the same end, called the "top". It follows the LIFO principle - the last element inserted is the first one to be removed.
Real-World Examples:
- Browser History: Back button uses stack - most recent page visited is shown first
- Undo Functionality: Text editors use stack to track changes
- Function Calls: Program execution uses call stack to track function calls
- Expression Evaluation: Converting and evaluating mathematical expressions
Stack Operations:
- Push: Add element to top of stack
- Pop: Remove element from top of stack
- Peek/Top: View top element without removing
- isEmpty: Check if stack is empty
- Size: Get number of elements in stack
Stack Implementation in Python:
# Stack implementation using Python list
class Stack:
def __init__(self):
self.items = []
def push(self, item):
"""Add item to top of stack"""
self.items.append(item)
print(f"Pushed: {item}")
def pop(self):
"""Remove and return top item"""
if self.is_empty():
return "Stack is empty"
return self.items.pop()
def peek(self):
"""View top item without removing"""
if self.is_empty():
return "Stack is empty"
return self.items[-1]
def is_empty(self):
"""Check if stack is empty"""
return len(self.items) == 0
def size(self):
"""Return number of items"""
return len(self.items)
def display(self):
"""Display all items"""
print("Stack (top to bottom):", self.items[::-1])
# Example usage
stack = Stack()
stack.push(10)
stack.push(20)
stack.push(30)
stack.display() # Output: [30, 20, 10]
print("Popped:", stack.pop()) # Output: 30
print("Top element:", stack.peek()) # Output: 20Practical Application - Balanced Parentheses:
def is_balanced(expression):
"""Check if parentheses are balanced using stack"""
stack = []
opening = "({["
closing = "})]"
pairs = {')': '(', '}': '{', ']': '['}
for char in expression:
if char in opening:
stack.append(char)
elif char in closing:
if not stack or stack.pop() != pairs[char]:
return False
return len(stack) == 0
# Test cases
print(is_balanced("({[]})")) # True
print(is_balanced("({[})")) # False
print(is_balanced("((()))")) # TrueQueue - FIFO (First In First Out) Principle
A Queue is a linear data structure where elements are added at one end (rear) and removed from the other end (front). It follows the FIFO principle - the first element inserted is the first one to be removed.
Real-World Examples:
- Printer Queue: Print jobs are processed in order they were received
- Customer Service: Customers served in order of arrival
- CPU Scheduling: Processes waiting for CPU time
- BFS Algorithm: Breadth-First Search uses queue for traversal
Queue Operations:
- Enqueue: Add element to rear of queue
- Dequeue: Remove element from front of queue
- Front: View front element without removing
- Rear: View last element
- isEmpty: Check if queue is empty
Queue Implementation in Python:
# Queue implementation using Python list
class Queue:
def __init__(self):
self.items = []
def enqueue(self, item):
"""Add item to rear of queue"""
self.items.append(item)
print(f"Enqueued: {item}")
def dequeue(self):
"""Remove and return front item"""
if self.is_empty():
return "Queue is empty"
return self.items.pop(0)
def front(self):
"""View front item without removing"""
if self.is_empty():
return "Queue is empty"
return self.items[0]
def rear(self):
"""View rear item"""
if self.is_empty():
return "Queue is empty"
return self.items[-1]
def is_empty(self):
"""Check if queue is empty"""
return len(self.items) == 0
def size(self):
"""Return number of items"""
return len(self.items)
def display(self):
"""Display all items"""
print("Queue (front to rear):", self.items)
# Example usage
queue = Queue()
queue.enqueue(10)
queue.enqueue(20)
queue.enqueue(30)
queue.display() # Output: [10, 20, 30]
print("Dequeued:", queue.dequeue()) # Output: 10
print("Front element:", queue.front()) # Output: 20pop(0) for dequeue is O(n) because all elements need to shift. For better performance, use collections.deque which provides O(1) operations for both ends.
Efficient Queue Using collections.deque:
from collections import deque
class EfficientQueue:
def __init__(self):
self.items = deque()
def enqueue(self, item):
self.items.append(item) # O(1)
def dequeue(self):
if self.is_empty():
return "Queue is empty"
return self.items.popleft() # O(1)
def is_empty(self):
return len(self.items) == 0Linked Lists
A Linked List is a linear data structure where elements (nodes) are stored in sequence, but not in contiguous memory locations. Each node contains data and a reference (link) to the next node.
Advantages over Arrays:
- Dynamic Size: Can easily grow or shrink
- Efficient Insertion/Deletion: O(1) if position is known (no shifting needed)
- Memory Efficient: Uses only required memory
Disadvantages:
- Random Access: O(n) - must traverse from beginning
- Extra Memory: Stores reference to next node
- Cache Inefficient: Non-contiguous memory
Singly Linked List Implementation:
# Node class
class Node:
def __init__(self, data):
self.data = data
self.next = None
# Linked List class
class LinkedList:
def __init__(self):
self.head = None
def insert_at_beginning(self, data):
"""Insert node at beginning - O(1)"""
new_node = Node(data)
new_node.next = self.head
self.head = new_node
def insert_at_end(self, data):
"""Insert node at end - O(n)"""
new_node = Node(data)
if self.head is None:
self.head = new_node
return
current = self.head
while current.next:
current = current.next
current.next = new_node
def delete_node(self, key):
"""Delete node with given data - O(n)"""
current = self.head
# If head needs to be deleted
if current and current.data == key:
self.head = current.next
current = None
return
# Search for the node
prev = None
while current and current.data != key:
prev = current
current = current.next
# If key not found
if current is None:
return
# Unlink the node
prev.next = current.next
current = None
def search(self, key):
"""Search for a node - O(n)"""
current = self.head
while current:
if current.data == key:
return True
current = current.next
return False
def display(self):
"""Display all nodes"""
current = self.head
elements = []
while current:
elements.append(current.data)
current = current.next
print(" -> ".join(map(str, elements)))
# Example usage
ll = LinkedList()
ll.insert_at_end(10)
ll.insert_at_end(20)
ll.insert_at_beginning(5)
ll.display() # Output: 5 -> 10 -> 20
ll.delete_node(10)
ll.display() # Output: 5 -> 20Binary Trees
A Binary Tree is a hierarchical data structure where each node has at most two children, referred to as left child and right child. The topmost node is called the root.
Types of Binary Trees:
- Full Binary Tree: Every node has 0 or 2 children
- Complete Binary Tree: All levels filled except possibly the last, which fills from left
- Perfect Binary Tree: All internal nodes have 2 children, all leaves at same level
- Binary Search Tree (BST): Left child < parent < right child
Binary Tree Traversals:
- Inorder (Left-Root-Right): Gives sorted order in BST
- Preorder (Root-Left-Right): Useful for copying tree
- Postorder (Left-Right-Root): Useful for deleting tree
- Level Order: Level by level traversal (uses queue)
Binary Search Tree Implementation:
# Node class for BST
class TreeNode:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
# Binary Search Tree class
class BinarySearchTree:
def __init__(self):
self.root = None
def insert(self, data):
"""Insert data into BST"""
if self.root is None:
self.root = TreeNode(data)
else:
self._insert_recursive(self.root, data)
def _insert_recursive(self, node, data):
if data < node.data:
if node.left is None:
node.left = TreeNode(data)
else:
self._insert_recursive(node.left, data)
else:
if node.right is None:
node.right = TreeNode(data)
else:
self._insert_recursive(node.right, data)
def inorder_traversal(self, node):
"""Inorder: Left-Root-Right"""
if node:
self.inorder_traversal(node.left)
print(node.data, end=" ")
self.inorder_traversal(node.right)
def preorder_traversal(self, node):
"""Preorder: Root-Left-Right"""
if node:
print(node.data, end=" ")
self.preorder_traversal(node.left)
self.preorder_traversal(node.right)
def search(self, data):
"""Search for data in BST - O(log n) average"""
return self._search_recursive(self.root, data)
def _search_recursive(self, node, data):
if node is None or node.data == data:
return node is not None
if data < node.data:
return self._search_recursive(node.left, data)
return self._search_recursive(node.right, data)
# Example usage
bst = BinarySearchTree()
values = [50, 30, 70, 20, 40, 60, 80]
for val in values:
bst.insert(val)
print("Inorder traversal:")
bst.inorder_traversal(bst.root) # Output: 20 30 40 50 60 70 80
print("\nSearch 40:", bst.search(40)) # True
print("Search 100:", bst.search(100)) # FalseGraphs Basics
A Graph is a non-linear data structure consisting of vertices (nodes) and edges connecting them. Graphs are used to represent networks, relationships, and connections.
Types of Graphs:
- Directed vs Undirected: Edges have direction or not
- Weighted vs Unweighted: Edges have weights/costs or not
- Cyclic vs Acyclic: Contains cycles or not
- Connected vs Disconnected: All vertices reachable or not
Graph Representations:
- Adjacency Matrix: 2D array, space O(V²)
- Adjacency List: Dictionary of lists, space O(V+E)
Simple Graph Implementation:
# Graph using Adjacency List
class Graph:
def __init__(self):
self.graph = {}
def add_vertex(self, vertex):
"""Add a vertex to graph"""
if vertex not in self.graph:
self.graph[vertex] = []
def add_edge(self, vertex1, vertex2):
"""Add an edge between two vertices (undirected)"""
if vertex1 in self.graph and vertex2 in self.graph:
self.graph[vertex1].append(vertex2)
self.graph[vertex2].append(vertex1)
def display(self):
"""Display graph"""
for vertex in self.graph:
print(f"{vertex} -> {', '.join(map(str, self.graph[vertex]))}")
# Example usage
g = Graph()
vertices = ['A', 'B', 'C', 'D']
for v in vertices:
g.add_vertex(v)
g.add_edge('A', 'B')
g.add_edge('A', 'C')
g.add_edge('B', 'D')
g.add_edge('C', 'D')
g.display()
# Output:
# A -> B, C
# B -> A, D
# C -> A, D
# D -> B, CTime and Space Complexity
Understanding complexity helps choose the right data structure for your use case:
| Data Structure | Access | Search | Insertion | Deletion | Space |
|---|---|---|---|---|---|
| Array | O(1) | O(n) | O(n) | O(n) | O(n) |
| Stack | O(n) | O(n) | O(1) | O(1) | O(n) |
| Queue | O(n) | O(n) | O(1) | O(1) | O(n) |
| Linked List | O(n) | O(n) | O(1)* | O(1)* | O(n) |
| Binary Search Tree | O(log n) | O(log n) | O(log n) | O(log n) | O(n) |
| Hash Table | O(1) | O(1) | O(1) | O(1) | O(n) |
* For linked lists, insertion/deletion is O(1) if position is known, otherwise O(n) to find position
Choosing the Right Data Structure
Select data structures based on your requirements:
Use Stack When:
- You need LIFO behavior (undo/redo, browser history)
- Implementing recursion or DFS algorithm
- Expression evaluation or syntax parsing
- Backtracking problems (maze solving, N-queens)
Use Queue When:
- You need FIFO behavior (task scheduling, printer queue)
- BFS algorithm implementation
- Handling asynchronous requests
- Cache implementation (LRU cache)
Use Linked List When:
- Frequent insertions/deletions in middle
- Size changes frequently and unpredictably
- Implementing other data structures (stack, queue)
- Memory fragmentation is an issue
Use Trees When:
- Hierarchical data (file systems, organization charts)
- Need fast search, insertion, deletion (BST)
- Implementing dictionaries or databases
- Priority queues (heap trees)
Use Graphs When:
- Representing networks (social, computer, road)
- Finding shortest paths (GPS navigation)
- Web crawling and link analysis
- Recommendation systems
Data Structures in CBSE Class 12 Syllabus
For CBSE Class 12 Computer Science, focus on these topics:
Covered in Syllabus:
- Stack: Implementation using list, push, pop, peek operations
- Queue: Implementation using list, enqueue, dequeue operations
- Understanding: LIFO vs FIFO principles, applications
Exam Preparation Tips:
- Write Complete Code: Practice writing full stack/queue implementation from scratch
- Understand Operations: Know what each operation does and its complexity
- Real-World Examples: Memorize 2-3 applications for each data structure
- Trace Code: Practice predicting output of given stack/queue programs
- Error Finding: Be ready to identify errors in given code
- Diagram Drawing: Draw stack/queue states after each operation
Common Exam Questions:
- Write a function to push/pop elements in stack
- Write a function to insert/delete elements in queue
- Predict output of given stack/queue program
- Find errors in given stack/queue implementation
- Explain LIFO/FIFO with examples
- Give 3 real-world applications of stack/queue
Study Strategy for Exams
- Practice writing stack/queue code at least 10 times without looking
- Create a small notebook with all operation codes for quick revision
- Solve all NCERT and sample paper questions on data structures
- Watch your indentation - Python is strict about it!
- Remember edge cases: empty stack/queue, single element scenarios
- Use meaningful variable names in exams for better readability
Frequently Asked Questions
What is the difference between Stack and Queue?
Stack follows LIFO (Last In First Out) principle - the last element added is the first to be removed, like a stack of plates. Queue follows FIFO (First In First Out) principle - the first element added is the first to be removed, like people standing in a line. Stack has one end for operations (top), while Queue has two ends (front for removal, rear for addition). Real-world examples: Stack - browser back button, undo feature; Queue - printer jobs, customer service line.
When should I use a Linked List instead of an Array?
Use Linked List when: (1) You need frequent insertions/deletions in the middle - Arrays require shifting elements making it O(n), while Linked Lists can do it in O(1) if position is known, (2) Size changes unpredictably - Arrays have fixed size or expensive resizing, Linked Lists grow dynamically, (3) You don't need random access - If you rarely access elements by index, the O(n) access time of Linked Lists won't hurt. Use Arrays when you need fast random access O(1), better cache performance, or when size is relatively stable.
What is time complexity and why does it matter?
Time complexity describes how the runtime of an algorithm grows as input size increases. It's expressed using Big O notation: O(1) constant time, O(log n) logarithmic, O(n) linear, O(n²) quadratic. It matters because the difference is dramatic at scale - for 1 million elements, O(1) takes 1 operation, O(n) takes 1 million, O(n²) takes 1 trillion! Choosing the right data structure can reduce time from hours to milliseconds. For example, searching in a sorted array with binary search is O(log n) instead of O(n) with linear search - for 1 million items, that's 20 operations vs 1 million.
How is Binary Search Tree different from a regular Binary Tree?
A Binary Tree is any tree where each node has at most 2 children, with no ordering requirement. A Binary Search Tree (BST) is a special Binary Tree with a strict ordering property: for every node, all values in the left subtree are smaller, and all values in the right subtree are larger. This ordering enables efficient operations: search, insert, and delete are O(log n) in balanced BSTs vs O(n) in regular Binary Trees. BSTs are used for implementing dictionaries, sets, and databases. Example: in BST with root 50, left child might be 30, right child 70 - this ordering must maintain throughout the tree.
Do I need to learn all data structures for CBSE Class 12 exam?
No! CBSE Class 12 Computer Science syllabus specifically covers only Stack and Queue. You need to know: (1) Implementation of Stack using Python list, (2) Implementation of Queue using Python list, (3) Operations: push/pop for stack, enqueue/dequeue for queue, (4) LIFO and FIFO principles, (5) Real-world applications, and (6) Writing code to solve problems using these structures. Linked Lists, Trees, and Graphs are NOT in CBSE syllabus, though they're helpful for competitive programming and college. Focus your exam preparation on mastering Stack and Queue thoroughly - write code 10+ times, understand each operation, and practice NCERT questions.