Comparison Mode
Side-by-side: use case, requirements, complexity, strengths, weaknesses, example problems, and a clear “choose this when…”.
BFS vs DFSDijkstra vs Bellman-FordKruskal vs PrimMerge Sort vs Quick SortHeap vs Priority QueueHash Map vs Tree MapBFS vs DijkstraSliding Window vs Two PointersPrefix Sum vs Segment TreeGreedy vs Dynamic ProgrammingMemoization vs TabulationTarjan vs KosarajuSegment Tree vs Fenwick TreeArray vs Linked ListStack vs QueueQuick Sort vs Heap SortKMP vs Rabin-KarpUnion-Find vs DFSTrie vs Hash MapAVL Tree vs Red-Black Tree
ArrayFundamentals | Linked ListFundamentals | |
|---|---|---|
| Use case | Indexed data, sequential scans, binary search, anything cache-sensitive. | Frequent insert/delete at known positions, queues and LRU caches, unknown final size. |
| Requirements | Contiguous memory; resizing by copying (dynamic array). | Node objects with next (and prev) pointers. |
| Time complexity | Access O(1); insert/delete in the middle O(n); append amortized O(1). | Access O(n); insert/delete at a known node O(1); append O(1) with a tail pointer. |
| Space complexity | O(n), no per-element overhead. | O(n) plus one or two pointers per node. |
| Strengths | Random access; cache locality; compact. | O(1) splice at a known node; no resizing; stable node addresses for hash-map + list designs. |
| Weaknesses | Shifting on insert/delete; growth requires copying; fixed capacity in static form. | No random access; poor cache behaviour; pointer bugs. |
| Example problems | Two sum, binary search, prefix sums, sliding window. | Reverse linked list, merge k sorted lists, LRU cache, linked list cycle. |
| Choose this when | Choose an array by default; index access and cache locality beat linked lists for almost every workload. | Choose a linked list when you hold references to nodes and need O(1) insertion or removal at those nodes, as in an LRU cache. |