A Primer on Data Structures

1. The Array

An array is simply a collection of items stored at contiguous memory locations. Because the memory is contiguous, the computer can instantly calculate where any specific element is located if it knows the starting address.

Get / Read

Accessing an element is instantaneous (O(1)). We simply ask for the value at a specific index.

let value = arr[1]; // Returns 20

Update

Because we have direct index access, updating a value is exactly as fast as reading it.

arr[1] = 99;

Add / Insert

Pushing to the end of a dynamic array is fast. However, inserting an element in the middle requires shifting all subsequent elements to the right to make room (O(n)).

// Insert '25' at index 1
for (let i = arr.length; i > 1; i--) {
  arr[i] = arr[i - 1]; // Shift right
}
arr[1] = 25;

Remove / Delete

Similarly, deleting an element from the middle requires shifting everything to the left to close the gap (O(n)).

// Remove value at index 1
for (let i = 1; i < arr.length - 1; i++) {
  arr[i] = arr[i + 1]; // Shift left
}
arr.length--;

2. The Linked List

Unlike arrays, elements in a linked list are not stored in contiguous memory. Instead, each element (called a Node) stores its data and a pointer to the next node in the sequence.

Add / Insert

Inserting a node means we just have to update a couple of pointers. No elements need to be shifted in memory!

newNode.next = prevNode.next;
prevNode.next = newNode;

Remove / Delete

To remove a node, you simply point the previous node's `next` pointer to "skip" the node you want to delete.

// Skip the node we want to remove
prevNode.next = prevNode.next.next;

Update & Get

Because memory is scattered, you cannot ask a linked list for "index 5". You must start at the Head and traverse the pointers until you reach the target. This makes both Get and Update O(n).

let current = head;
while (current !== target) {
  current = current.next;
}
current.value = newValue;

newNode.next = current.next;
newNode.prev = current;
current.next.prev = newNode;
current.next = newNode;

tail.next = newNode;
newNode.next = head;

3. The Stack

A Stack operates on a Last-In, First-Out (LIFO) principle. Think of it like a stack of plates; you can only ever add or remove plates from the very top.

Add (Push)

Adding an item to a stack is always called a Push.

stack.push(newValue);
top++;

Remove (Pop)

Removing an item takes it off the top. You cannot pull from the bottom.

let topValue = stack.pop();
top--;

Get (Peek) & Update

Standard stacks do not allow random access. You cannot update the middle element. You can only Peek at the top element without removing it.

let currentTop = stack[top];

4. The Queue

A Queue operates on a First-In, First-Out (FIFO) principle. It works exactly like a line at a supermarket.

Add (Enqueue)

Elements always enter at the Rear (the back of the line).

queue[rear] = newValue;
rear++;

Remove (Dequeue)

Elements always leave from the Front.

let first = queue[front];
front++;
return first;

Get (Peek) & Update

Like a stack, random updates are strictly forbidden in pure queues. You can only peek at who is at the front of the line.

5. The Tree (Binary Search Tree)

Trees are hierarchical structures. In a Binary Search Tree (BST), the left child is smaller than the parent, and the right child is larger. This allows for incredibly fast operations.

Add / Insert

We traverse down the tree. If the value is smaller, go left. If larger, go right. Insert when an empty spot is found.

if (val < current.val) {
  if (!current.left) current.left = new Node(val);
  else insert(current.left, val);
}

Remove / Delete

Tree deletion is tricky. If the node has no children, we just sever the link. If it has one child, the child replaces it. If it has two, things get complicated (requiring the in-order successor).

if (!node.left && !node.right) {
  return null; // node deleted
}

Get / Search

Thanks to the BST rule, searching is extremely fast (O(log n) average case), exactly how we insert.

while (current !== null) {
  if (val === current.val) return current;
  current = val < current.val ? current.left : current.right;
}

6. The Graph

Graphs represent networks. They consist of Vertices (Nodes) and Edges (Lines connecting them). Social networks and maps are graphs.

[
  [0, 1, 0],
  [1, 0, 1],
  [0, 1, 0]
]

{
  0: [1],
  1: [0, 2],
  2: [1]
}

function DFS(v, visited) {
  visited[v] = true;
  for (let n of adj[v]) {
    if (!visited[n]) DFS(n, visited);
  }
}

while (q.length > 0) {
  let v = q.shift();
  for (let n of adj[v]) {
    if (!visited[n]) {
      visited[n] = true;
      q.push(n);
    }
  }
}

7. Sparse Matrix

A matrix is called Sparse if most of its elements are zero. Storing all these zeros in a 2D array is a waste of memory. Instead, we store only the non-zero elements along with their positions.

[
  [0, 0, 5, 0],
  [0, 8, 0, 0],
  [0, 0, 0, 0],
  [2, 0, 0, 0]
]

// Simplified logic:
if (a.row == b.row && a.col == b.col) {
  result.push(a.row, a.col, a.val + b.val);
}

// Only multiply if A.col == B.row
if (a[i].col == b[j].row) {
  sum += a[i].val * b[j].val;
}

// Swap row and col
newRow = oldCol;
newCol = oldRow;

8. The Heap (Max Heap)

A Heap is a specialized Tree-based data structure. In a Max Heap, the root is the maximum element, and every parent is greater than its children.

Heaps are almost always implemented using an Array because they are "Complete Binary Trees".

Add (Insert)

Insert at the end of the array, then "Bubble Up" until the heap property is restored.

heap.push(val);
bubbleUp(heap.length - 1);

Remove (Extract Max)

Swap root with the last element, pop the last, and "Bubble Down" from the root.

heap[0] = heap.pop();
bubbleDown(0);

9. Tower of Hanoi

The Tower of Hanoi is a classic mathematical puzzle that illustrates the power of Recursion. It consists of three rods and a number of disks of different sizes.

The objective is to move the entire stack to another rod, obeying three simple rules:

• Only one disk can be moved at a time.
• Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack.
• No disk may be placed on top of a smaller disk.

Recursive Logic

To move n disks from Source to Target using an Auxiliary rod:

1. Move n-1 disks from Source to Auxiliary.
2. Move the nth (largest) disk from Source to Target.
3. Move the n-1 disks from Auxiliary to Target.