api: YAML JSON TOON Database
version: 1.0.0
format: yaml
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:
    - You need a quick comparison of operation costs across data structures.
    - You are choosing a structure for a given access pattern.
  caveats:
    - 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:
    - sorting-algorithms-comparison
    - tree-data-structures
    - hash-tables
    - search-algorithms
  entry_count: 15
  fields:
    - section: structures
      field: name
      type: string
      example: Array
    - section: structures
      field: access
      type: string
      example: O(1)
    - section: structures
      field: search
      type: string
      example: O(n)
    - section: structures
      field: insertion
      type: string
      example: O(n)
    - section: structures
      field: deletion
      type: string
      example: O(n)
    - section: structures
      field: space
      type: string
      example: O(n)
  category: Data Structures
  category_slug: data-structures
  tags: algorithms,complexity,big-o,data structures
  view_count: 47
  created_at: 1777673262
  updated_at: 1777673262
data:
  structures:
    - name: Array
      access: O(1)
      search: O(n)
      insertion: O(n)
      deletion: O(n)
      space: O(n)
    - name: Linked List
      access: O(n)
      search: O(n)
      insertion: O(1)
      deletion: O(1)
      space: O(n)
    - name: Binary Search Tree
      access: O(log n)
      search: O(log n)
      insertion: O(log n)
      deletion: O(log n)
      space: O(n)
    - name: Hash Table
      access: N/A
      search: O(1)
      insertion: O(1)
      deletion: O(1)
      space: O(n)
    - name: Heap
      access: O(1) max
      search: O(n)
      insertion: O(log n)
      deletion: O(log n)
      space: O(n)
    - name: Graph (Adjacency List)
      access: O(1)
      search: O(V+E)
      insertion: O(1)
      deletion: O(V+E)
      space: O(V+E)
    - name: Stack
      access: O(n)
      search: O(n)
      insertion: O(1)
      deletion: O(1)
      space: O(n)
    - name: Queue
      access: O(n)
      search: O(n)
      insertion: O(1)
      deletion: O(1)
      space: O(n)
    - name: Dynamic Array
      access: O(1)
      search: O(n)
      insertion: O(n) (amortized O(1) at the end)
      deletion: O(n)
      space: O(n)
    - name: Doubly Linked List
      access: O(n)
      search: O(n)
      insertion: O(1)
      deletion: O(1)
      space: O(n)
    - name: AVL Tree
      access: O(log n)
      search: O(log n)
      insertion: O(log n)
      deletion: O(log n)
      space: O(n)
    - name: Red-Black Tree
      access: O(log n)
      search: O(log n)
      insertion: O(log n)
      deletion: O(log n)
      space: O(n)
    - name: B-Tree
      access: O(log n)
      search: O(log n)
      insertion: O(log n)
      deletion: O(log n)
      space: O(n)
    - name: Trie
      access: N/A
      search: O(m)
      insertion: O(m)
      deletion: O(m)
      space: O(total key length)
    - name: Skip List
      access: O(log n) expected
      search: O(log n) expected
      insertion: O(log n) expected
      deletion: O(log n) expected
      space: O(n)