Data Structures – Quick Exam Notes (10 Topics)
1. Introduction to Data Structures
• Data Structure: A way of organizing and storing data so it can be accessed and modified efficiently.
• Importance: efficient storage, faster searching, faster insertion/deletion, better memory use.
• Types: Linear (Array, Stack, Queue, Linked List) and Non■Linear (Tree, Graph).
• Primitive data types: int, float, char, pointer.
• Non■Primitive: Array, Stack, Queue, Linked List, Tree, Graph.
2. Array
• Array: Linear data structure storing same type elements in contiguous memory locations.
• Index starts at 0.
• Operations: Traversal (visit elements), Insertion (add element at position), Deletion (remove element),
Searching (find element).
• Types: One■Dimensional array, Two■Dimensional array (matrix).
• Advantages: fast access using index, simple implementation.
• Disadvantages: fixed size, insertion/deletion slow, possible memory wastage.
3. Stack
• Stack: Linear data structure following LIFO (Last In First Out).
• Operations: Push (insert), Pop (remove top), Peek (view top element), IsEmpty.
• Overflow: pushing into full stack.
• Underflow: popping from empty stack.
• Applications: expression evaluation, parenthesis checking, recursion, infix to postfix conversion.
4. Queue
• Queue: Linear data structure following FIFO (First In First Out).
• Operations: Enqueue (insert at rear), Dequeue (remove from front), IsEmpty, IsFull.
• Types: Simple Queue, Circular Queue, Priority Queue, Deque (double ended queue).
• Applications: CPU scheduling, printer queue, process scheduling, BFS traversal.
5. Linked List
• Linked List: Linear structure where elements are stored in nodes connected by pointers.
• Node structure: Data + Next pointer.
• Operations: Insertion, Deletion, Traversal.
• Types: Singly Linked List, Doubly Linked List, Circular Linked List.
• Advantages: dynamic size, easy insertion/deletion.
• Disadvantages: extra memory for pointers, slower access.
6. Tree
• Tree: Non■linear data structure representing hierarchical relationships.
• Important terms: Root, Parent, Child, Leaf, Edge.
• Binary Tree: each node has at most two children.
• Binary Search Tree (BST): Left subtree < Root < Right subtree.
• Tree Traversals: Inorder (Left■Root■Right), Preorder (Root■Left■Right), Postorder
(Left■Right■Root).
7. Graph
• Graph: Non■linear data structure consisting of vertices (nodes) and edges (connections).
• Types: Directed Graph, Undirected Graph.
• Traversal methods: DFS (Depth First Search – uses stack) and BFS (Breadth First Search – uses
queue).
• Applications: social networks, maps navigation, network routing.
8. Sorting
• Sorting: arranging data in ascending or descending order.
• Bubble Sort: repeatedly swaps adjacent elements if in wrong order.
• Selection Sort: repeatedly selects smallest element and places it at correct position.
• Insertion Sort: inserts each element into correct position like arranging playing cards.
9. Searching
• Searching: finding the location of an element in a data structure.
• Linear Search: checks each element one by one.
• Binary Search: divides sorted array into halves repeatedly to find element.
• Binary search requires sorted array and is faster than linear search.
10. Hashing
• Hashing: technique to store and retrieve data quickly using hash functions.
• Hash Function: converts key into index of array.
• Hash Table: structure storing data using hash values as index.
• Collision: when two keys map to same index.
• Collision resolution methods: Chaining, Open Addressing.