data-structures

Data Structures Skill

Skill Metadata

skill_config:
  version: "1.0.0"
  category: implementation
  prerequisites: [cs-foundations]
  estimated_time: "6-8 weeks"
  difficulty: intermediate

  parameter_validation:
    structure_type:
      type: string
      enum: [array, list, tree, heap, hash, graph, trie]
      required: true
    operation:
      type: string
      enum: [search, insert, delete, traverse]

  retry_config:
    max_attempts: 3
    backoff_strategy: exponential
    initial_delay_ms: 500

  observability:
    log_level: INFO
    metrics: [structure_usage, operation_complexity]

---

Quick Start

Choose the right structure for every problem. Master operations and trade-offs.

Linear Structures

Arrays

• Random access O(1)
• Fixed size
• Cache friendly
• Use: Known size, frequent access

Linked Lists

• Dynamic size
• Sequential access O(n)
• Efficient insertion/deletion O(1)
• Types: Singly, doubly, circular

Stacks

• LIFO principle
• Push/pop O(1)
• Use: Undo/redo, parenthesis matching, DFS

Queues

• FIFO principle
• Enqueue/dequeue O(1)
• Types: Simple, circular, priority, deque
• Use: BFS, job scheduling

Trees

Binary Search Trees

• Ordered storage
• Search/insert/delete O(log n) avg
• Traversals: inorder, preorder, postorder

Balanced Trees

• AVL: height-balanced
• Red-Black: color-based balancing
• B-Trees: multi-way
• Guarantee O(log n) operations

Heaps

• Min/Max heap property
• Insert/delete O(log n), Build O(n)
• Use: Priority queues, heap sort

Hash Structures

Hash Tables

• Average O(1) operations
• Collision handling: chaining, open addressing
• Load factor matters

---

Decision Matrix

Need	Best Structure
Random access	Array
Frequent insertions/deletions	Linked list
Min/max element	Heap
Ordered traversal	BST
Fast lookup	Hash table
Prefix matching	Trie
Relations	Graph

---

Complexity Comparison

Operation	Array	List	BST	Hash	Heap
Search	O(n)	O(n)	O(log n)	O(1) avg	O(n)
Insert	O(n)	O(1)*	O(log n)	O(1) avg	O(log n)
Delete	O(n)	O(1)*	O(log n)	O(1) avg	O(log n)

---

Troubleshooting

Issue	Root Cause	Resolution
Hash collision storm	Poor hash function	Improve hash, use chaining
Tree degenerates	Sorted insertions	Use balanced tree (AVL/RB)
Memory exhaustion	No size limits	Add capacity limits
Iterator invalidation	Modify during iteration	Use safe iteration pattern

---

Implementation Checklist

• Dynamic array with resizing
• Singly/doubly linked list
• Stack and queue
• Binary search tree
• AVL tree or Red-Black tree
• Hash table
• Min/max heap
• Trie
• Graph (adjacency list)
• Disjoint set union