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
1---2name: data-structures3description: Master selection and implementation of data structures. Learn when to use arrays, lists, trees, graphs, heaps, and hash tables for optimal performance.4---56# Data Structures Skill78## Skill Metadata910```yaml11skill_config:12 version: "1.0.0"13 category: implementation14 prerequisites: [cs-foundations]15 estimated_time: "6-8 weeks"16 difficulty: intermediate1718 parameter_validation:19 structure_type:20 type: string21 enum: [array, list, tree, heap, hash, graph, trie]22 required: true23 operation:24 type: string25 enum: [search, insert, delete, traverse]2627 retry_config:28 max_attempts: 329 backoff_strategy: exponential30 initial_delay_ms: 5003132 observability:33 log_level: INFO34 metrics: [structure_usage, operation_complexity]35```3637---3839## Quick Start4041Choose the right structure for every problem. Master operations and trade-offs.4243### Linear Structures4445**Arrays**46- Random access O(1)47- Fixed size48- Cache friendly49- Use: Known size, frequent access5051**Linked Lists**52- Dynamic size53- Sequential access O(n)54- Efficient insertion/deletion O(1)55- Types: Singly, doubly, circular5657**Stacks**58- LIFO principle59- Push/pop O(1)60- Use: Undo/redo, parenthesis matching, DFS6162**Queues**63- FIFO principle64- Enqueue/dequeue O(1)65- Types: Simple, circular, priority, deque66- Use: BFS, job scheduling6768### Trees6970**Binary Search Trees**71- Ordered storage72- Search/insert/delete O(log n) avg73- Traversals: inorder, preorder, postorder7475**Balanced Trees**76- AVL: height-balanced77- Red-Black: color-based balancing78- B-Trees: multi-way79- Guarantee O(log n) operations8081**Heaps**82- Min/Max heap property83- Insert/delete O(log n), Build O(n)84- Use: Priority queues, heap sort8586### Hash Structures8788**Hash Tables**89- Average O(1) operations90- Collision handling: chaining, open addressing91- Load factor matters9293---9495## Decision Matrix9697| Need | Best Structure |98|------|----------------|99| Random access | Array |100| Frequent insertions/deletions | Linked list |101| Min/max element | Heap |102| Ordered traversal | BST |103| Fast lookup | Hash table |104| Prefix matching | Trie |105| Relations | Graph |106107---108109## Complexity Comparison110111| Operation | Array | List | BST | Hash | Heap |112|-----------|-------|------|-----|------|------|113| Search | O(n) | O(n) | O(log n) | O(1) avg | O(n) |114| Insert | O(n) | O(1)* | O(log n) | O(1) avg | O(log n) |115| Delete | O(n) | O(1)* | O(log n) | O(1) avg | O(log n) |116117---118119## Troubleshooting120121| Issue | Root Cause | Resolution |122|-------|------------|------------|123| Hash collision storm | Poor hash function | Improve hash, use chaining |124| Tree degenerates | Sorted insertions | Use balanced tree (AVL/RB) |125| Memory exhaustion | No size limits | Add capacity limits |126| Iterator invalidation | Modify during iteration | Use safe iteration pattern |127128---129130## Implementation Checklist131132- [ ] Dynamic array with resizing133- [ ] Singly/doubly linked list134- [ ] Stack and queue135- [ ] Binary search tree136- [ ] AVL tree or Red-Black tree137- [ ] Hash table138- [ ] Min/max heap139- [ ] Trie140- [ ] Graph (adjacency list)141- [ ] Disjoint set union
pluginagentmarketplace