Skip to main contentSkip to user menuSkip to navigation
System Designer
Back to Reference

Data Structures for Systems

Not Started
Loading...

Data Structures Reference

Essential data structures for system design and algorithm implementation

10
Data Structures
Linear

Array

Fixed-size sequential collection of elements of the same type

Time Complexity

access
O(1)
search
O(n)
insertion
O(n)
deletion
O(n)

Space Complexity

O(n)

Best Use Case:

When you need fast random access to elements by index

Advantages:

  • +Constant time access by index
  • +Memory efficient
  • +Cache-friendly due to locality

Disadvantages:

  • -Fixed size in most languages
  • -Expensive insertion/deletion
  • -Memory waste if not fully utilized

System Design Applications:

Caching frequently accessed dataStoring configuration valuesBatch processing operations

Common Examples:

User IDs in a batch processing systemPixel data in image processingTime series data points
Linear

Linked List

Dynamic data structure where elements are stored in nodes with pointers

Time Complexity

access
O(n)
search
O(n)
insertion
O(1)
deletion
O(1)

Space Complexity

O(n)

Best Use Case:

When you need frequent insertions/deletions and don't need random access

Advantages:

  • +Dynamic size
  • +Efficient insertion/deletion
  • +Memory efficient for sparse data

Disadvantages:

  • -No random access
  • -Extra memory for pointers
  • -Not cache-friendly

System Design Applications:

LRU cache implementationTask queuesEvent processing pipelines

Common Examples:

Undo functionality in applicationsMusic playlist implementationBrowser history
Linear

Stack

LIFO (Last In, First Out) data structure

Time Complexity

access
O(n)
search
O(n)
insertion
O(1)
deletion
O(1)

Space Complexity

O(n)

Best Use Case:

When you need LIFO behavior for temporary storage

Advantages:

  • +Simple implementation
  • +Constant time push/pop
  • +Memory efficient

Disadvantages:

  • -Limited access pattern
  • -No random access
  • -Can overflow if not managed

System Design Applications:

Request processing in web serversParsing and compilationBacktracking algorithms

Common Examples:

Function call stackExpression evaluationUndo operations
Linear

Queue

FIFO (First In, First Out) data structure

Time Complexity

access
O(n)
search
O(n)
insertion
O(1)
deletion
O(1)

Space Complexity

O(n)

Best Use Case:

When you need FIFO behavior for processing elements in order

Advantages:

  • +Fair processing order
  • +Constant time enqueue/dequeue
  • +Natural for producer-consumer

Disadvantages:

  • -No random access
  • -Limited access pattern
  • -Memory overhead for pointers

System Design Applications:

Message queues (RabbitMQ, Kafka)Load balancingRate limiting

Common Examples:

Task schedulingPrint job queuesBreadth-first search
Tree

Binary Tree

Hierarchical structure where each node has at most two children

Time Complexity

access
O(log n)
search
O(log n)
insertion
O(log n)
deletion
O(log n)

Space Complexity

O(n)

Best Use Case:

When you need hierarchical data organization with efficient search

Advantages:

  • +Logarithmic time operations
  • +Natural hierarchical representation
  • +Efficient for sorted data

Disadvantages:

  • -Can become unbalanced
  • -Complex implementation
  • -Overhead for balancing

System Design Applications:

Database indexingSearch enginesAuto-completion systems

Common Examples:

File system directoriesDecision treesExpression parsing
Tree

Heap

Complete binary tree with heap property (min-heap or max-heap)

Time Complexity

access
O(1)
search
O(n)
insertion
O(log n)
deletion
O(log n)

Space Complexity

O(n)

Best Use Case:

When you need efficient access to minimum/maximum element

Advantages:

  • +Constant time access to min/max
  • +Efficient insertion/deletion
  • +Space efficient (array-based)

Disadvantages:

  • -No efficient search for arbitrary elements
  • -Not suitable for sorted iteration
  • -Complex deletion of arbitrary elements

System Design Applications:

Task scheduling with prioritiesMemory managementTop-K problems

Common Examples:

Priority queuesHeap sort algorithmDijkstra's algorithm
Tree

Trie (Prefix Tree)

Tree structure for storing strings with common prefixes

Time Complexity

access
O(m)
search
O(m)
insertion
O(m)
deletion
O(m)

Space Complexity

O(ALPHABET_SIZE * N * M)

Best Use Case:

When you need efficient prefix-based string operations

Advantages:

  • +Fast prefix matching
  • +Space efficient for common prefixes
  • +Supports autocomplete

Disadvantages:

  • -High memory usage
  • -Complex implementation
  • -Not suitable for general data

System Design Applications:

Search suggestionsURL routingDictionary implementations

Common Examples:

Autocomplete systemsSpell checkersIP routing tables
Hash-based

Hash Table

Data structure that maps keys to values using hash functions

Time Complexity

access
O(1)
search
O(1)
insertion
O(1)
deletion
O(1)

Space Complexity

O(n)

Best Use Case:

When you need fast key-value lookups and don't need ordering

Advantages:

  • +Constant time operations (average)
  • +Flexible key types
  • +Memory efficient

Disadvantages:

  • -No ordering of elements
  • -Hash collisions
  • -Worst-case O(n) performance

System Design Applications:

Distributed caching (Redis)Session storageRate limiting counters

Common Examples:

Database indexesCaching systemsSymbol tables
Graph

Graph

Collection of vertices connected by edges

Time Complexity

access
O(V + E)
search
O(V + E)
insertion
O(1)
deletion
O(V + E)

Space Complexity

O(V + E)

Best Use Case:

When you need to represent relationships between entities

Advantages:

  • +Flexible relationship modeling
  • +Supports complex algorithms
  • +Natural for network problems

Disadvantages:

  • -Complex implementation
  • -High space complexity
  • -Difficult to optimize

System Design Applications:

Social media connectionsRecommendation systemsNetwork routing

Common Examples:

Social networksTransportation networksDependency graphs
Probabilistic

Bloom Filter

Space-efficient probabilistic data structure for membership testing

Time Complexity

access
N/A
search
O(k)
insertion
O(k)
deletion
N/A

Space Complexity

O(m)

Best Use Case:

When you need memory-efficient approximate membership testing

Advantages:

  • +Very space efficient
  • +Constant time operations
  • +No false negatives

Disadvantages:

  • -False positives possible
  • -No deletion support
  • -No element retrieval

System Design Applications:

CDN cache checkingDatabase query optimizationSpam filtering

Common Examples:

Web crawling duplicate detectionDatabase query optimizationDistributed caching

Time Complexity Guide

O(1)
Excellent
O(log n)
Good
O(n)
Fair
O(n log n)
Bad
O(n²)
Terrible

Selection Guide: Choose data structures based on your most frequent operations. Prioritize O(1) and O(log n) complexities for critical paths. Consider space-time tradeoffs and real-world constraints like cache performance and implementation complexity.

Related Resources

Design Principles

Core principles for choosing the right data structure

Performance Optimization

Optimize data structure usage for better performance

Database Selector

Interactive tool to choose the right database