Data Structure and Algorithm – Definitions of All Topics
1. Searching Techniques
Linear Search: Linear search checks each element of the list sequentially until the required element is
found or the list ends. (O(n))
Binary Search: Efficient search on a sorted list by repeatedly dividing the search interval into halves.
(O(log n))
2. Sorting Techniques
Selection Sort: Selects the smallest or largest element and places it in the correct position. (O(n²))
Bubble Sort: Repeatedly compares adjacent elements and swaps if in wrong order. (O(n²))
Merge Sort: Divides list into halves, sorts each half, and merges them. (O(n log n))
Quick Sort: Uses a pivot to partition and sort recursively. (O(n log n))
Shell Sort: Generalized insertion sort that compares far-apart elements. (O(n log² n))
Heap Sort: Uses heap structure to sort by repeatedly extracting the max/min. (O(n log n))
Radix Sort: Non-comparison sorting using digit-by-digit counting. (O(nk))
3. Hashing
Hash Table: Stores key–value pairs for fast access using hash functions. (O(1) average)
Hash Function: Converts a key into an index.
Collision: Occurs when two keys produce same hash index.
Collision Resolution: Techniques like chaining, linear probing, double hashing.
Hash Table Implementation: Practical creation of a hash table using array and hash function.
4. Huffman Algorithm and Huffman Tree
Huffman Algorithm: A greedy algorithm used for lossless data compression assigning shorter codes to
frequent symbols.
Huffman Tree: A binary tree built based on symbol frequencies, where each leaf node represents a
symbol.
5. Concept of Data Structure
Data Structure: A way to organize and store data efficiently.
Types: Primitive (int, char), Non-Primitive (array, list, tree, graph), Linear (array, queue, stack),
Non-linear (tree, graph).
Operations: Insertion, deletion, traversal, searching, sorting, merging, updating.
6. Algorithm Analysis and Complexity
Algorithm: Step-by-step procedure to solve a problem.
Algorithm Analysis: Determines time and space required by algorithm.
Complexity: Time and space used by an algorithm.
Time-Space Trade-off: Speed can be improved by using more memory and vice versa.
Asymptotic Notations: O (worst), Ω (best), Θ (average).
7. Arrays
Array: Collection of elements of same type stored in contiguous memory.
One-Dimensional Array: Linear list of elements accessed by one index.
Address Calculation: LOC(A[i]) = Base(A) + (i × size).
Array Operations: Traversal, insertion, deletion, searching, sorting.
Multidimensional Arrays: Arrays with more than one index.
Sparse Matrix: Matrix with mostly zero elements stored efficiently.
8. Pointers
Pointer: Variable storing memory address of another variable.
Pointer Variables: Declared using '*'.
Pointers and Structures: Allow dynamic access to structure members.
Dynamic Memory Allocation: Allocating memory during runtime (malloc, calloc, realloc, free).
9. Linked Lists
Linked List: Linear data structure where elements (nodes) are linked using pointers.
Types: Singly, Doubly, Circular, and Header Linked Lists.
Operations: Insertion, deletion, traversal, searching, updating.
10. Stack (Linked Representation)
Stack: Linear structure following LIFO (Last In, First Out) principle.
Operations: Push (insert), Pop (remove), Peek (top element).
Linked Representation: Implemented using linked list nodes.
11. Queue (Linked Representation)
Queue: Linear structure following FIFO (First In, First Out) principle.
Operations: Enqueue (insert), Dequeue (remove).
Linked Representation: Implemented using linked list with front and rear pointers.