Data Structure Operations Time Complexity Guide
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.

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.