| 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 |