Data Structure Reference
Compare data structures side by side with time complexity, space complexity, and use cases.
37.0Kuses
8.9/10(74)
| Structure | Access | Search | Insert | Delete | Space |
|---|---|---|---|---|---|
| Array | O(1) | O(n) | O(n) | O(n) | O(n) |
| Dynamic Array | O(1) | O(n) | O(1)* | O(n) | O(n) |
| Linked List | O(n) | O(n) | O(1) | O(1) | O(n) |
| Doubly Linked List | O(n) | O(n) | O(1) | O(1) | O(n) |
| Stack | O(n) | O(n) | O(1) | O(1) | O(n) |
| Queue | O(n) | O(n) | O(1) | O(1) | O(n) |
| Hash Table | N/A | O(1)* | O(1)* | O(1)* | O(n) |
| BST | O(log n)* | O(log n)* | O(log n)* | O(log n)* | O(n) |
| AVL Tree | O(log n) | O(log n) | O(log n) | O(log n) | O(n) |
| Heap | O(n) | O(n) | O(log n) | O(log n) | O(n) |
| Trie | O(m) | O(m) | O(m) | O(m) | O(n*m) |
| Graph (Adj. List) | O(V+E) | O(V+E) | O(1) | O(E) | O(V+E) |
* = amortized average case. m = key length (for Trie). V = vertices, E = edges (for Graph).
Use Cases
Array
Random access, iteration, cache-friendly
Dynamic Array
Resizable arrays, lists, stacks
Linked List
Frequent insertions/deletions, queues
Doubly Linked List
Two-way traversal, LRU cache
Stack
LIFO, undo, recursion, parsing
Queue
FIFO, BFS, task scheduling
Hash Table
Fast lookup, caching, counting
BST
Sorted data, range queries
AVL Tree
Balanced BST, databases
Heap
Priority queues, scheduling
Trie
Autocomplete, spell check, IP routing
Graph (Adj. List)
Networks, social graphs, maps
About
A comprehensive comparison chart of common data structures with average-case time complexities for key operations. Asterisk (*) indicates amortized or average-case values.
⚡ Pro OptionsSponsored
Some links on this page are affiliate links. If you click and make a purchase, we may earn a commission at no extra cost to you.
Recommended Products
Ad⌨️Mechanical KeyboardsShop →🖥️Developer MonitorsShop →🪑Standing DesksShop →🎧Noise Cancelling HeadphonesShop →📷WebcamsShop →💻Laptop StandsShop →🖱️Wireless MouseShop →🔌USB-C HubShop →👓Blue Light GlassesShop →🖥️Desk PadShop →
Affiliate Disclosure: As an Amazon Associate, ToolBird earns from qualifying purchases. Links above are affiliate links — if you buy through them, we may earn a small commission at no extra cost to you.
Disclaimer: This tool is provided as-is for informational and educational purposes only.