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.

Mar 15, 2025 - 17:44
 0
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.