Understanding time complexity is essential for writing efficient code. Here's a quick reference guide for common data structure operations to help you make the right choices in your projects.
Index-Based List Operations
| Operation | Time Complexity | Description |
|---|---|---|
| get(r) | O(1) | Retrieve element at index r |
| set(r, e) | O(1) | Replace element at index r with e |
| add(r, e) | O(n) | Insert element e at index r |
| remove(r) | O(n) | Remove element at index r |
Linked Lists (Position-Based) Operations
| Operation | Time Complexity | Description |
|---|---|---|
| element() | O(1) | Return element at a given position |
| first() | O(1) | Return position of first element |
| last() | O(1) | Return position of last element |
| before(p) | O(1) | Return position before p |
| after(p) | O(1) | Return position after p |
| insertAfter(p, e) | O(1) | Insert element e after position p |
| insertBefore(p, e) | O(1) | Insert element e before position p |
| remove(p) | O(1) | Remove element at position p |
Tree Operations
| Operation | Time Complexity | Description |
|---|---|---|
| createNode(element, parent) | O(1) | Create new tree node |
| root() | O(1) | Return root node of tree |
| parent(v) | O(1) | Return parent of node v |
| children(v) | O(1) | Return set of children of node v |
| isInternal(v) | O(1) | Check if node v is internal |
| isExternal(v) | O(1) | Check if node v is external (leaf) |
| isRoot(v) | O(1) | Check if node v is the root |
| size() | O(1) | Return number of nodes in tree |
| elements() | O(n) | Return set of all elements in tree |
| positions() | O(n) | Return set of all positions in tree |
| swapElements(v, w) | O(1) | Swap elements between nodes v and w |
| replaceElement(v, e) | O(1) | Replace element in node v with e |
| depth(T, v) | O(n) | Calculate depth of node v in tree T |
| height(T, v) | O(n) | Calculate height of subtree rooted at v |
Tree Traversal Algorithms
| Operation | Time Complexity | Description |
|---|---|---|
| preorder(T, v) | O(n) | Visit nodes in preorder starting from v |
| postorder(T, v) | O(n) | Visit nodes in postorder starting from v |
Why This Matters
Understanding the time complexity of these operations helps you:
- Choose the right data structure for your specific use case
- Optimize your algorithms for better performance
- Avoid unexpected performance bottlenecks in production
Keep this reference handy when designing your next algorithm or debugging performance issues!
Implementation Examples
If you're looking for pseudocode implementations of these data structures, check out my GitHub repository:
Algorithms Library on GitHub
The repository contains pseudocode implementations that complement this time complexity guide. Feel free to use them as a reference when implementing these data structures in your projects.
