Introduction
Data structures are the building blocks of software engineering. Every program you write, every algorithm you implement, and every system you design relies on choosing the right data structure for the job. The difference between an O(1) lookup and an O(n) lookup can mean the difference between a system that handles millions of requests per second and one that collapses under load.
Yet many developers learn data structures in a computer science course and never revisit them. They reach for arrays and objects by default, missing opportunities to use more efficient structures like hash maps, tries, or balanced binary trees. Understanding when and why to use each data structure is a skill that separates competent developers from exceptional ones.
This guide covers the essential data structures every developer should know, with practical TypeScript implementations, real-world use cases, and performance analysis. Rather than academic definitions, we focus on when to use each structure and the trade-offs involved.
Understanding Data Structures: The Fundamentals
A data structure is a way of organizing and storing data so that it can be accessed and modified efficiently. Different data structures are optimized for different operations—some excel at lookups, others at insertions, and others at maintaining order. The key insight is that there's no single "best" data structure; the right choice depends on your access patterns.
Data structures fall into two broad categories: linear (arrays, linked lists, stacks, queues) and non-linear (trees, graphs, hash tables). Linear structures store elements in a sequence, while non-linear structures store elements with relationships between them. Understanding these categories helps you reason about which structure fits your problem.
The performance of a data structure is measured by its time complexity (how long operations take) and space complexity (how much memory it uses). We use Big O notation to describe how performance scales with the number of elements. O(1) means constant time regardless of size, O(log n) means logarithmic growth, and O(n) means linear growth.
Arrays and Dynamic Arrays
Arrays are the most fundamental data structure—a contiguous block of memory storing elements of the same type. Arrays provide O(1) random access by index but O(n) insertion and deletion in the middle. Dynamic arrays (like JavaScript's Array or Python's list) automatically resize when they run out of capacity, amortizing the cost of resizing to O(1) per insertion.
// Dynamic array implementation
class DynamicArray<T> {
private data: T[]
private _size: number
private _capacity: number
constructor(initialCapacity: number = 4) {
this.data = new Array(initialCapacity)
this._size = 0
this._capacity = initialCapacity
}
get size(): number { return this._size }
get capacity(): number { return this._capacity }
get(index: number): T {
if (index < 0 || index >= this._size) {
throw new Error('Index out of bounds')
}
return this.data[index]
}
push(value: T): void {
if (this._size === this._capacity) {
this.resize(this._capacity * 2)
}
this.data[this._size++] = value
}
private resize(newCapacity: number): void {
const newData = new Array(newCapacity)
for (let i = 0; i < this._size; i++) {
newData[i] = this.data[i]
}
this.data = newData
this._capacity = newCapacity
}
}When to use arrays: Sequential access, iteration, when you need index-based lookup, and when the size is known or changes infrequently. Arrays are cache-friendly because elements are stored contiguously in memory.
When NOT to use arrays: When you need frequent insertions/deletions in the middle, when the order matters and changes frequently, or when you need to search by value rather than index.
Hash Tables (Hash Maps)
Hash tables provide O(1) average-case lookup, insertion, and deletion. They work by computing a hash function that maps keys to array indices. When two keys hash to the same index (a collision), the hash table uses chaining (linked lists) or open addressing (probing) to resolve the conflict.
Hash tables are the workhorse of modern programming. JavaScript objects, Python dictionaries, and Java HashMaps are all hash table implementations. They're used for caching, counting, deduplication, and anywhere you need fast key-based lookups.
// Hash table with chaining for collision resolution
class HashTable<K, V> {
private buckets: Array<Array<[K, V]>>
private _size: number
private readonly LOAD_FACTOR_THRESHOLD = 0.75
constructor(initialCapacity: number = 16) {
this.buckets = new Array(initialCapacity).fill(null).map(() => [])
this._size = 0
}
private hash(key: K): number {
const str = String(key)
let hash = 5381
for (let i = 0; i < str.length; i++) {
hash = ((hash << 5) + hash + str.charCodeAt(i)) >>> 0
}
return hash % this.buckets.length
}
set(key: K, value: V): void {
const index = this.hash(key)
const bucket = this.buckets[index]
for (let i = 0; i < bucket.length; i++) {
if (bucket[i][0] === key) {
bucket[i][1] = value
return
}
}
bucket.push([key, value])
this._size++
if (this._size / this.buckets.length > this.LOAD_FACTOR_THRESHOLD) {
this.resize(this.buckets.length * 2)
}
}
get(key: K): V | undefined {
const index = this.hash(key)
const bucket = this.buckets[index]
for (const [k, v] of bucket) {
if (k === key) return v
}
return undefined
}
private resize(newCapacity: number): void {
const oldBuckets = this.buckets
this.buckets = new Array(newCapacity).fill(null).map(() => [])
this._size = 0
for (const bucket of oldBuckets) {
for (const [key, value] of bucket) {
this.set(key, value)
}
}
}
}When to use hash tables: Caching, frequency counting, deduplication, implementing sets, memoization, and any time you need O(1) key-based lookups.
When NOT to use hash tables: When you need ordered data, when you need range queries, or when memory is extremely constrained (hash tables have overhead for the array and pointers).
Linked Lists
Linked lists store elements in nodes, where each node contains a value and a pointer to the next node. Unlike arrays, linked lists don't require contiguous memory and provide O(1) insertion and deletion at the head. However, they have O(n) access by index and poor cache locality.
class ListNode<T> {
constructor(
public value: T,
public next: ListNode<T> | null = null
) {}
}
class LinkedList<T> {
private head: ListNode<T> | null = null
private tail: ListNode<T> | null = null
private _size: number = 0
get size(): number { return this._size }
prepend(value: T): void {
const node = new ListNode(value, this.head)
this.head = node
if (!this.tail) this.tail = node
this._size++
}
append(value: T): void {
const node = new ListNode(value)
if (!this.tail) {
this.head = this.tail = node
} else {
this.tail.next = node
this.tail = node
}
this._size++
}
delete(value: T): boolean {
if (!this.head) return false
if (this.head.value === value) {
this.head = this.head.next
if (!this.head) this.tail = null
this._size--
return true
}
let current = this.head
while (current.next) {
if (current.next.value === value) {
current.next = current.next.next
if (!current.next) this.tail = current
this._size--
return true
}
current = current.next
}
return false
}
toArray(): T[] {
const result: T[] = []
let current = this.head
while (current) {
result.push(current.value)
current = current.next
}
return result
}
}When to use linked lists: When you need frequent insertions/deletions at the head, when implementing stacks and queues, and when you don't need random access.
When NOT to use linked lists: When you need index-based access, when cache performance matters, or when memory overhead is a concern (each node stores a pointer).
Stacks and Queues
Stacks (LIFO—Last In, First Out) and queues (FIFO—First In, First Out) are abstract data types that restrict how elements are accessed. Stacks are used for undo mechanisms, expression evaluation, and call stacks. Queues are used for task scheduling, breadth-first search, and message processing.
// Stack implementation using a linked list
class Stack<T> {
private top: ListNode<T> | null = null
private _size: number = 0
push(value: T): void {
this.top = new ListNode(value, this.top)
this._size++
}
pop(): T | undefined {
if (!this.top) return undefined
const value = this.top.value
this.top = this.top.next
this._size--
return value
}
peek(): T | undefined {
return this.top?.value
}
get size(): number { return this._size }
get isEmpty(): boolean { return this._size === 0 }
}
// Queue implementation using a circular buffer
class Queue<T> {
private data: T[]
private head: number = 0
private tail: number = 0
private _size: number = 0
constructor(capacity: number = 16) {
this.data = new Array(capacity)
}
enqueue(value: T): void {
this.data[this.tail] = value
this.tail = (this.tail + 1) % this.data.length
this._size++
}
dequeue(): T | undefined {
if (this._size === 0) return undefined
const value = this.data[this.head]
this.head = (this.head + 1) % this.data.length
this._size--
return value
}
get size(): number { return this._size }
}Trees
Trees are hierarchical data structures with a root node and child nodes. Binary trees have at most two children per node. Binary Search Trees (BSTs) maintain the ordering property: left children are smaller, right children are larger. Balanced BSTs (AVL, Red-Black) guarantee O(log n) operations by maintaining balance.
class TreeNode<T> {
constructor(
public value: T,
public left: TreeNode<T> | null = null,
public right: TreeNode<T> | null = null
) {}
}
class BinarySearchTree<T> {
private root: TreeNode<T> | null = null
insert(value: T): void {
this.root = this.insertNode(this.root, value)
}
private insertNode(node: TreeNode<T> | null, value: T): TreeNode<T> {
if (!node) return new TreeNode(value)
if (value < node.value) {
node.left = this.insertNode(node.left, value)
} else if (value > node.value) {
node.right = this.insertNode(node.right, value)
}
return node
}
search(value: T): boolean {
return this.searchNode(this.root, value)
}
private searchNode(node: TreeNode<T> | null, value: T): boolean {
if (!node) return false
if (value === node.value) return true
return value < node.value
? this.searchNode(node.left, value)
: this.searchNode(node.right, value)
}
// In-order traversal returns sorted values
inOrder(): T[] {
const result: T[] = []
this.inOrderTraversal(this.root, result)
return result
}
private inOrderTraversal(node: TreeNode<T> | null, result: T[]): void {
if (!node) return
this.inOrderTraversal(node.left, result)
result.push(node.value)
this.inOrderTraversal(node.right, result)
}
}
Graphs
Graphs consist of vertices (nodes) and edges (connections). They model relationships—social networks, road maps, dependency trees, and network topologies. Graphs can be directed or undirected, weighted or unweighted, and cyclic or acyclic.
// Adjacency list representation
class Graph<T> {
private adjacencyList: Map<T, Set<T>> = new Map()
addVertex(vertex: T): void {
if (!this.adjacencyList.has(vertex)) {
this.adjacencyList.set(vertex, new Set())
}
}
addEdge(from: T, to: T): void {
this.addVertex(from)
this.addVertex(to)
this.adjacencyList.get(from)!.add(to)
this.adjacencyList.get(to)!.add(from) // For undirected graph
}
// Breadth-First Search
bfs(start: T): T[] {
const visited = new Set<T>()
const queue: T[] = [start]
const result: T[] = []
visited.add(start)
while (queue.length > 0) {
const vertex = queue.shift()!
result.push(vertex)
for (const neighbor of this.adjacencyList.get(vertex) || []) {
if (!visited.has(neighbor)) {
visited.add(neighbor)
queue.push(neighbor)
}
}
}
return result
}
// Depth-First Search
dfs(start: T): T[] {
const visited = new Set<T>()
const result: T[] = []
const dfsHelper = (vertex: T) => {
visited.add(vertex)
result.push(vertex)
for (const neighbor of this.adjacencyList.get(vertex) || []) {
if (!visited.has(neighbor)) {
dfsHelper(neighbor)
}
}
}
dfsHelper(start)
return result
}
// Shortest path (unweighted)
shortestPath(start: T, end: T): T[] | null {
const visited = new Set<T>()
const queue: T[][] = [[start]]
visited.add(start)
while (queue.length > 0) {
const path = queue.shift()!
const vertex = path[path.length - 1]
if (vertex === end) return path
for (const neighbor of this.adjacencyList.get(vertex) || []) {
if (!visited.has(neighbor)) {
visited.add(neighbor)
queue.push([...path, neighbor])
}
}
}
return null
}
}Heaps (Priority Queues)
A heap is a complete binary tree that satisfies the heap property: in a min-heap, every parent is smaller than its children; in a max-heap, every parent is larger. Heaps are used to implement priority queues, heap sort, and algorithms like Dijkstra's shortest path.
class MinHeap<T> {
private data: T[] = []
get size(): number { return this.data.length }
get isEmpty(): boolean { return this.data.length === 0 }
peek(): T | undefined { return this.data[0] }
insert(value: T): void {
this.data.push(value)
this.bubbleUp(this.data.length - 1)
}
extractMin(): T | undefined {
if (this.data.length === 0) return undefined
if (this.data.length === 1) return this.data.pop()
const min = this.data[0]
this.data[0] = this.data.pop()!
this.sinkDown(0)
return min
}
private bubbleUp(index: number): void {
while (index > 0) {
const parent = Math.floor((index - 1) / 2)
if (this.data[parent] <= this.data[index]) break
;[this.data[parent], this.data[index]] = [this.data[index], this.data[parent]]
index = parent
}
}
private sinkDown(index: number): void {
const length = this.data.length
while (true) {
let smallest = index
const left = 2 * index + 1
const right = 2 * index + 2
if (left < length && this.data[left] < this.data[smallest]) smallest = left
if (right < length && this.data[right] < this.data[smallest]) smallest = right
if (smallest === index) break
;[this.data[index], this.data[smallest]] = [this.data[smallest], this.data[index]]
index = smallest
}
}
}Tries
A trie (prefix tree) is a tree-like data structure for storing strings. Each node represents a character, and paths from root to leaf represent words. Tries are used for autocomplete, spell checking, and IP routing.
class TrieNode {
children: Map<string, TrieNode> = new Map()
isEndOfWord: boolean = false
}
class Trie {
private root = new TrieNode()
insert(word: string): void {
let node = this.root
for (const char of word) {
if (!node.children.has(char)) {
node.children.set(char, new TrieNode())
}
node = node.children.get(char)!
}
node.isEndOfWord = true
}
search(word: string): boolean {
let node = this.root
for (const char of word) {
if (!node.children.has(char)) return false
node = node.children.get(char)!
}
return node.isEndOfWord
}
startsWith(prefix: string): string[] {
let node = this.root
for (const char of prefix) {
if (!node.children.has(char)) return []
node = node.children.get(char)!
}
const results: string[] = []
this.collectWords(node, prefix, results)
return results
}
private collectWords(node: TrieNode, prefix: string, results: string[]): void {
if (node.isEndOfWord) results.push(prefix)
for (const [char, child] of node.children) {
this.collectWords(child, prefix + char, results)
}
}
}Performance Comparison
| Structure | Access | Search | Insert | Delete | Space | Best For |
|---|---|---|---|---|---|---|
| Array | O(1) | O(n) | O(1)* | O(n) | O(n) | Index-based access |
| Linked List | O(n) | O(n) | O(1) | O(1) | O(n) | Frequent head insertions |
| Hash Table | N/A | O(1)* | O(1)* | O(1)* | O(n) | Key-based lookups |
| BST (balanced) | O(log n) | O(log n) | O(log n) | O(log n) | O(n) | Ordered data |
| Heap | O(1)** | O(n) | O(log n) | O(log n) | O(n) | Priority queues |
| Trie | N/A | O(m)*** | O(m) | O(m) | O(n*m) | Prefix search |
*Amortized / **Peek only / ***m = word length
Real-World Applications
Caching with LRU Cache
An LRU (Least Recently Used) cache combines a hash map and a doubly linked list to provide O(1) get and put operations:
class LRUCache<K, V> {
private cache = new Map<K, V>()
private readonly maxSize: number
constructor(maxSize: number) {
this.maxSize = maxSize
}
get(key: K): V | undefined {
if (!this.cache.has(key)) return undefined
const value = this.cache.get(key)!
// Move to end (most recently used)
this.cache.delete(key)
this.cache.set(key, value)
return value
}
put(key: K, value: V): void {
if (this.cache.has(key)) {
this.cache.delete(key)
} else if (this.cache.size >= this.maxSize) {
// Remove least recently used (first entry)
const firstKey = this.cache.keys().next().value
this.cache.delete(firstKey)
}
this.cache.set(key, value)
}
}Graph Algorithms for Social Networks
Social networks use graph algorithms for friend recommendations, community detection, and influence analysis. BFS finds shortest connection paths, while PageRank identifies influential nodes.
Conclusion
Data structures are not just academic exercises—they're practical tools that directly impact your application's performance and scalability. Choosing the right data structure for your access pattern is one of the most impactful decisions you can make.
Key takeaways:
- Hash tables are your default for key-based lookups—O(1) average performance makes them the right choice for most mapping and caching scenarios.
- Arrays excel at sequential access and index-based operations—use them when you need fast iteration and random access.
- Trees provide ordered data with O(log n) operations—use BSTs, heaps, and tries when ordering or hierarchical relationships matter.
- Graphs model relationships—use them for social networks, dependency analysis, and pathfinding.
Practice implementing these structures from scratch to build intuition. Refer to VisuAlgo for interactive visualizations and Big-O Cheat Sheet for quick performance reference.