api: YAML JSON TOON Database
version: 1.0.0
format: toon
dataset:
  id: 2753
  slug: complexity-analysis
  title: Data Structure Complexity Analysis
  description: "Time and space complexity analysis of common data structures: Array, Linked List, Binary Search Tree, Hash Table, Heap, and Graph with Big-O notation."
  summary: "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_when[2]: You need a quick comparison of operation costs across data structures.,You are choosing a structure for a given access pattern.
  caveats[2]: "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."
  related[4]: sorting-algorithms-comparison,tree-data-structures,hash-tables,search-algorithms
  entry_count: 15
  fields[6]{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)
  category: Data Structures
  category_slug: data-structures
  tags: "algorithms,complexity,big-o,data structures"
  view_count: 48
  created_at: 1777673262
  updated_at: 1777673262
data:
  structures[15]{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)