Programming

Comparison Table Data Structure Structure Type Search Complexity Insertion Complexity Deletion Complexity Use Cases Advantages Disadvantages Array Contiguous block of memory O(1) for access; O(n) for search (unsorted) O(n) (shifting elements) O(n) (shifting elements) Static collections, lookup tables Fast random access, cache friendly Fixed size (static arrays), expensive mid-operations Linked List Node-based (non-contiguous memory) O(n) O(1) (with pointer/reference) O(1) (with pointer/reference) Dynamic lists, implementing stacks/queues Dynamic size, efficient insertions/deletions No random access, additional memory for pointers Stack LIFO (often implemented via array or linked list) O(n) if searching required O(1) (push) O(1) (pop) Function calls, recursion, backtracking Simple, constant-time push/pop Access restricted to the top element Queue FIFO (often implemented via array or linked list) O(n) if searching required O(1) (enqueue) O(1) (dequeue) Scheduling, buffering, process management Simple FIFO order, constant time operations Access restricted to front/rear only Binary Search Tree Hierarchical tree (ordered) O(log n) average; O(n) worst-case O(log n) average; O(n) worst-case O(log n) average; O(n) worst-case Maintaining sorted data, dynamic sets Efficient average-case operations, maintains order Unbalanced trees can degrade to O(n) operations Heap (Binary Heap) Complete binary tree O(n) for arbitrary search O(log n) O(log n) Priority queues, heap sort Fast access to min/max element, efficient insertion/deletion Not efficient for general searching Hash Table Key-value mapping using hashing O(1) average; O(n) worst-case O(1) average; O(n) worst-case O(1) average; O(n) worst-case Dictionaries, caches, indexing Extremely fast average-case operations Performance depends on hash function; worst-case linear; unordered Graph Collection of nodes (vertices) and edges Varies (algorithm dependent) Varies (representation dependent) Varies (representation dependent) Modeling networks, routing, social networks Models complex relationships, versatile Implementation complexity; can be memory-intensive Additional Notes Arrays are best for scenarios where the size is fixed and fast random access is required. Linked Lists shine in situations requiring frequent insertions and deletions with dynamic sizing. Stacks and Queues provide simple, ordered data access patterns suitable for specific algorithmic strategies. Binary Search Trees offer ordered storage with efficient average-case performance, though balanced versions (like AVL or Red-Black trees) are preferred in practice. Heaps are ideal for priority-based tasks. Hash Tables are invaluable for fast lookup tasks, provided a well-designed hash function minimizes collisions. Graphs are essential for representing interconnected data but require careful design regarding representation (adjacency list vs. matrix) based on the use case.

Truth Table X Y X & Y X | Y X ^ Y 0 0 0 0 0 0 1 0 1 1 1 0 0 1 1 1 1 1 1 0 Points to Remember The left-shift and right-shift operators should not be used for negative numbers Left Shift(<<) just means multiply by 2. Similarly >> results division by 2. XOR results 0 if both bits are same. So a^1=~a , a^0=a and a^a=0. Questions How to toggle or flip a particular bit in a number? To toggle any bit in a variable, Use (^) exclusive OR operator. #define togglebit(data, bit) (data* = data ^ (1<<bit)) Write MACRO to Swap the bytes in 16bit Integer Variable. #define ByteSwap16(Value) ((Value & 0x00FF) << 8) | ((Value & 0xFF00) >> 8) #define ByteSwap32(Value) ((Value & 0x000000FF) << 24) | ((Value & 0x0000FF00U) << 8) | ((Value & 0x00FF0000U) >> 8) | ((Value & 0xFF000000U) >> 24) Count the number of set bits in a number unsigned int countSetBits( unsigned int number ) { unsigned int count = 0; while( number != 0) { count++; number &= (number-1); } return count; } Swap 2 bits of given integer int swapBits(unsigned int n, unsigned int p1, unsigned int p2) { unsigned int bit1 = (n >> p1) & 1; /* Move p1'th to rightmost side */ unsigned int bit2 = (n >> p2) & 1; /* Move p2'th to rightmost side */ unsigned int x = (bit1 ^ bit2); /* XOR the two bits */ /* Put the xor bit back to their original positions */ x = (x << p1) | (x << p2); /* XOR 'x' with the original number so that the two sets are swapped */ unsigned int result = n ^ x; }