Data Structures

Fundamental ways to organize and store data for efficient access and modification.

What is a Data Structure?

A data structure is a way of organizing data so that it can be used efficiently. Different data structures are suited for different tasksโ€”choosing the right one can dramatically improve your program's performance.

๐ŸŽฏ Key Categories

Linear Structures

Arrays, Linked Lists, Stacks, Queues

Non-Linear Structures

Trees, Graphs, Heaps

๐Ÿ“ฆ Arrays

An array stores elements in contiguous memory locations. Access any element instantly by its index.

10
[0]
20
[1]
30
[2]
40
[3]
50
[4]

โœ… Strengths

  • โ€ข O(1) random access by index
  • โ€ข Cache-friendly (memory locality)
  • โ€ข Simple and fast

โŒ Weaknesses

  • โ€ข Fixed size (in many languages)
  • โ€ข O(n) insertion/deletion
  • โ€ข Expensive to resize
// Array operations
const arr = [1, 2, 3, 4, 5];
arr[0];           // Access: O(1)
arr.push(6);      // Append: O(1) amortized
arr.splice(2, 1); // Delete at index: O(n)

๐Ÿ”— Linked List

A linked list stores elements in nodes, where each node points to the next. Great for frequent insertions/deletions.

A
โ†’
B
โ†’
C
โ†’
D
null

โœ… Strengths

  • โ€ข O(1) insertion/deletion at known position
  • โ€ข Dynamic size
  • โ€ข No wasted memory

โŒ Weaknesses

  • โ€ข O(n) access (must traverse)
  • โ€ข Extra memory for pointers
  • โ€ข Poor cache performance

๐Ÿ“š Stack (LIFO)

Last In, First Out โ€” like a stack of plates. You can only add or remove from the top.

A
B
C
โ† pop() / push()
(bottom)

Use cases: Function call stack, undo operations, expression parsing, browser history (back button)

// Stack operations - all O(1)
const stack = [];
stack.push(1);    // Add to top
stack.push(2);
stack.pop();      // Remove from top โ†’ 2
stack[stack.length - 1]; // Peek top โ†’ 1

๐ŸŽซ Queue (FIFO)

First In, First Out โ€” like a line at a store. Add to the back, remove from the front.

dequeue โ†
A
B
C
D
โ† enqueue

Use cases: Task scheduling, BFS traversal, print queue, message queues

๐Ÿ“– Hash Table

Maps keys to values using a hash function. Provides near-instant O(1) lookup!

"name" โ†’ "Alice"
"age" โ†’ 25
"city" โ†’ "NYC"
"job" โ†’ "Engineer"
// Hash table operations - all O(1) average
const map = new Map();
map.set("name", "Alice");  // Insert
map.get("name");           // Lookup โ†’ "Alice"
map.has("name");           // Check โ†’ true
map.delete("name");        // Remove

๐ŸŒณ Tree

A hierarchical structure with a root node and child nodes. Each node can have multiple children but only one parent.

A
B
D
E
C
F

Common types: Binary Tree, Binary Search Tree (BST), AVL Tree, Red-Black Tree, Trie, Heap

๐ŸŒ Graph

A collection of nodes (vertices) connected by edges. Can represent networks, relationships, maps, and more.

Directed Graph

Edges have direction (A โ†’ B)

Example: Twitter follows

Undirected Graph

Edges go both ways (A โ€” B)

Example: Facebook friends

Quick Comparison

StructureAccessSearchInsertDelete
ArrayO(1)O(n)O(n)O(n)
Linked ListO(n)O(n)O(1)*O(1)*
Hash TableO(1)O(1)O(1)O(1)
BST (balanced)O(log n)O(log n)O(log n)O(log n)

* O(1) when position is known; O(n) to find position

Content adapted from Hello ็ฎ—ๆณ• - Data Structures by Krahets, licensed under CC BY-NC-SA 4.0.