Data Structure Complexity Analysis
Time and space complexity analysis of common data structures: Array, Linked List, Binary Search Tree, Hash Table, Heap, and Graph with Big-O notation.
Time and space complexity of basic operations (access, search, insertion, deletion) for the core data structures: arrays, linked lists, binary search trees, hash tables, heaps and graphs, extended with stacks, queues, dynamic arrays, balanced trees, tries and skip lists.
Use it when
- You need a quick comparison of operation costs across data structures.
- You are choosing a structure for a given access pattern.
Watch out for
- Values are typical average-case figures; worst cases can be worse (a hash table with many collisions, an unbalanced tree).
- For linked-list insertion and deletion, O(1) assumes you already hold a reference to the node.
The data
Structures
15 rows
| Name | Access | Search | Insertion | Deletion | Space |
|---|---|---|---|---|---|
| Array | O(1) | O(n) | O(n) | O(n) | O(n) |
| Linked List | O(n) | O(n) | O(1) | O(1) | O(n) |
| Binary Search Tree | O(log n) | O(log n) | O(log n) | O(log n) | O(n) |
| Hash Table | N/A | O(1) | O(1) | O(1) | O(n) |
| Heap | O(1) max | O(n) | O(log n) | O(log n) | O(n) |
| Graph (Adjacency List) | O(1) | O(V+E) | O(1) | O(V+E) | O(V+E) |
| Stack | O(n) | O(n) | O(1) | O(1) | O(n) |
| Queue | O(n) | O(n) | O(1) | O(1) | O(n) |
| Dynamic Array | O(1) | O(n) | O(n) (amortized O(1) at the end) | O(n) | O(n) |
| Doubly Linked List | O(n) | O(n) | O(1) | O(1) | O(n) |
| AVL Tree | O(log n) | O(log n) | O(log n) | O(log n) | O(n) |
| Red-Black Tree | O(log n) | O(log n) | O(log n) | O(log n) | O(n) |
| B-Tree | O(log n) | O(log n) | O(log n) | O(log n) | O(n) |
| Trie | N/A | O(m) | O(m) | O(m) | O(total key length) |
| Skip List | O(log n) expected | O(log n) expected | O(log n) expected | O(log n) expected | O(n) |
Fields
The shape of this dataset, read from the data itself: every column, its type and a real value. Agents can use this to plan a query without fetching the whole document.
| Section | Field | Type | Example |
|---|---|---|---|
| structures | name | string | Array |
| structures | access | string | O(1) |
| structures | search | string | O(n) |
| structures | insertion | string | O(n) |
| structures | deletion | string | O(n) |
| structures | space | string | O(n) |
Fetch the same bytes
The static files contain the same reference rows as the API, with no API rate limit. Live metadata, such as view counts, may differ. Use the API for content negotiation; use the static files for a cacheable snapshot.
curl "https://yjtoon.com/api/dataset/complexity-analysis?format=toon"
const res = await fetch( "https://yjtoon.com/static-data/dataset/complexity-analysis.toon" ); const toon = await res.text();
Rate limit: 120 requests per minute per IP, no key and no signup. API reference →