Data structures are specific ways of organizing and storing data in a computer so it can be accessed and modified efficiently. Algorithms are instructions and formulas for solving problems.
Data Structures
We structure data in different ways depending on what data we have, and what we want to do with it.
Primitive Data Structures
Basic data structures provided by programming languages to represent single values, such as integers, floating-point numbers, characters, and booleans.
Abstract Data Structures
Higher level data structures that are built using primitive data types and provide more complex and specialized operations.
1. Arrays
An array is a collection of items stored at contiguous (unbreakable) memory locations.
const a = new ArrayBuffer(6);
const a8 = new Uint8Array(a);
// ArrayBuffer { [Uint8Contents]: <00 00 00 00 00 00>, [byteLength]: 6 }
In JavaScript, arrays aren't primitives but are instead Array objects with special characteristics.
const a = []; // This isn't an actual array.
2. Linked List
A linked list is a node-based data structure where each node contains a value and a reference (pointer) to the next node. Unlike arrays, linked lists allow dynamic insertion and deletion with constant time complexity, and do not require shifting indices when modifying the list.
Linked lists use heap-allocated objects, which means nodes are stored in memory locations that are typically more expensive than stack memory. Each node is a separate object containing a value and references to other nodes.
interface LinkedList<T> {
get length(): number;
insertAt(item: T, index: number): void;
remove(item: T): T | undefined;
removeAt(index: number): T | undefined;
append(item: T): void;
prepend(item: T): void;
get(index: number): T | undefined;
}
3. Queue
A queue is a FIFO (First In, First Out) structure, where elements are inserted at the tail and removed from the head of the list, similar to waiting in a line. Both pushing and popping elements from a queue are constant time O(1) operations, as they only involve updating pointers and do not require traversing the entire list.
type Node<T> = {
value: T;
next?: Node<T>;
};
class Queue<T> {
public length: number;
private head?: Node<T>;
private tail?: Node<T>;
constructor() {
this.head = this.tail = undefined;
this.length = 0;
}
enqueue(item: T): void {
const node = { value: item } as Node<T>;
this.length++;
if (!this.tail) {
this.tail = this.head = node;
}
this.tail.next = node;
this.tail = node;
}
deque(): T | undefined {
if (!this.head) {
return undefined;
}
this.length--;
const head = this.head;
this.head = this.head.next;
// free memory
head.next = undefined;
return head.value;
}
peek(): T | undefined {
return this.head?.value;
}
}
4. Stack
A stack is a singly linked list where elements are added and removed only from the head, following a Last-In-First-Out (LIFO) principle, similar to a stack of plates where the last item added is the first one removed. To push an element in a stack, you point the new element's 'next' pointer to the current head, and then update the head to point to the new element.
Stack operations are efficient because they involve constant time pointer manipulations, which do not depend on the number of items in the list or the size of the values.
Function calls are conceptually similar to a stack, with each function call being 'pushed' onto the call stack and 'popped' off when the function completes. The memory used for these calls is literally called the 'stack'.
type Node<T> = {
value: T;
prev?: Node<T>;
};
class Stack<T> {
public length: number;
private head?: Node<T>;
constructor() {
this.head = undefined;
this.length = 0;
}
push(item: T): void {
const node = { value: item } as Node<T>;
this.length++;
if (!this.head) {
this.head = node;
return;
}
node.prev = this.head;
this.head = node;
}
pop(): T | undefined {
this.length = Math.max(0, this.length - 1);
if (this.length === 0) {
const head = this.head;
this.head = undefined;
return head?.value;
}
const head = this.head as Node<T>;
this.head = head.prev;
return head.value;
}
peek(): T | undefined {
return this.head?.value;
}
}
5. Array List
A dynamic, growable array under the hood It creates a new array with a larger capacity (often doubled), then copies existing elements to the new array, allowing for dynamic growth.
Standard operations include push (adding to the end) and pop (removing from the end), which are stack-like operations with O(1) time complexity when the array has not exceeded its capacity.
Inserting or deleting from the front or middle requires shifting all subsequent elements, resulting in an O(N) time complexity.
class ArrayList<T> {
private items: T[] = [];
public push(element: T): void {
this.items.push(element);
}
public get(index: number): T {
if (index < 0 || index >= this.items.length) {
throw new Error("Index out of bounds");
}
return this.items[index];
}
public pop(index: number): T | undefined {
return this.items.splice(index, 1)[0];
}
public size(): number {
return this.items.length;
}
public isEmpty(): boolean {
return this.items.length === 0;
}
}
6. Ring Buffer
A ring buffer is a data structure where operations like pushing, popping, shifting, and unshifting are O(1), using modulo arithmetic to wrap around an array. It maintains order by using head and tail indices that can move circularly within a fixed-size array.
When a ring buffer needs to resize, it creates a new larger buffer, starting at the head and copying elements in order. The head will be set to 0, and the tail will be set to the current length, allowing for additional capacity and continued circular operations.
A ring buffer can be used in log batching scenarios, where logs need to maintain order while being written. It allows for efficient logging by periodically flushing a batch of logs without blocking the main service, and without requiring complex mutex synchronization.
class RingBuffer<T> {
private buffer: (T | null)[];
private capacity: number;
private head: number = 0;
private tail: number = 0;
private size: number = 0;
constructor(capacity: number) {
this.capacity = capacity;
this.buffer = new Array(capacity).fill(null);
}
push(item: T): boolean {
if (this.isFull()) {
return false;
}
this.buffer[this.tail] = item;
this.tail = (this.tail + 1) % this.capacity;
this.size++;
return true;
}
pop(): T | null {
if (this.isEmpty()) {
return null;
}
const item = this.buffer[this.head];
// Clean up reference for GC
this.buffer[this.head] = null;
this.head = (this.head + 1) % this.capacity;
this.size--;
return item;
}
isEmpty(): boolean {
return this.size === 0;
}
isFull(): boolean {
return this.size === this.capacity;
}
getSize(): number {
return this.size;
}
}
Algorithms
An algorithm is a set of step-by-step instructions to solve a given problem or achieve a specific goal.
Searching Algorithms
Searching algorithms are essential tools in computer science used to locate specific items within a collection of data.
1. Linear Search
Linear search is the most straightforward way to find a specific value in a collection of data. We find our needle by walking through the array and checking for the needle with a conditional statement. Worst case time complexity would be O(n).
function linear_search(heystack: number[], needle: number): boolean {
for (let i = 0; i < heystack.length; i++) {
if (heystack[i] === needle) {
return true;
}
}
return false;
}2. Binary Search
Binary search is faster than linear search except for small arrays. However, the array must be sorted first to be able to apply binary search. Worst case time complexity would be O(log n).
function binary_search(haystack: number[], needle: number): boolean {
let lo = 0;
let hi = haystack.length;
do {
const m = Math.floor(lo + (hi - lo) / 2);
const v = haystack[m];
if (v === needle) {
return true;
} else if (v > needle) {
hi = m;
} else {
lo = m + 1;
}
} while (lo < hi);
return false;
}3. Two Crystal Balls
There are two identical crystal balls and one needs to find out which is the maximum floor in a 100 story building from where the balls can fall before they break. In the most efficient way, what will be the maximum number of drops required to find the right floor in any possible scenario.
This can be represented in a sorted array of 100 elements:
[0, 0, 0, 0, 0, ..., 0, 1, 1, 1, 1, 1, 1, 1, ..., 1]So each time we find 1, it will break, and will only have 1 ball left. So we can only find the 1 twice (break 2 balls). We can’t use the binary search since we only have 2 crystal balls to break.
Drop the first ball from floors 10, 20, 30, and so on. When it breaks (say at floor 30) you know the critical floor is between 21 and 30. Use the second ball to check 21, 22, 23… until it breaks. Worst case time complexity would be O(n√x).
function crystal_balls(breaks: boolean[]): number {
const jmpAmount = Math.floor(Math.sqrt(breaks.length));
let i = jmpAmount;
for (; i < breaks.length; i += jmpAmount) {
if (breaks[i]) {
break;
}
}
i -= jmpAmount;
for (let j = 0; j < jmpAmount && i < breaks.length; ++j, ++i) {
if (breaks[i]) {
return i;
}
}
return -1;
}Sorting Algorithms
Sorting algorithms are methods used to rearrange elements in a list or array into a specific order, typically numerical or lexicographical. Mathematical definition of a sorted array would be any element x[i] is less than or equal to x[i+1] throughout the entire array.
1. Bubble Sort
Compare adjacent elements and swap them if they are in the wrong order, moving the largest element to the end of the array in each iteration. Time complexity would be O(n²), where n is the number of elements in the array.
function bubble_sort(arr: number[]): void {
for (let i = 0; i < arr.length; ++i) {
for (let j = 0; j < arr.length - 1 - i; ++j) {
if (arr[j] > arr[j + 1]) {
const tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
}
}
}
}1. Quick Sort
Quick sort is a highly efficient, divide-and-conquer sorting algorithm that partitions an array into smaller sub-arrays around a "pivot" element.
function partition(arr: number[], lo: number, hi: number): number {
const pivot = arr[hi];
let idx = lo - 1;
for (let i = lo; i < hi; ++i) {
if (arr[i] <= pivot) {
idx++;
const tmp = arr[i];
arr[i] = arr[idx];
arr[idx] = tmp;
}
}
idx++;
arr[hi] = arr[idx];
arr[idx] = pivot;
return idx;
}
function qs(arr: number[], lo: number, hi: number): void {
if (lo >= hi) {
return arr;
}
const pivotIdx = partition(arr, lo, hi);
qs(arr, lo, pivotIdx - 1);
qs(arr, pivotIdx + 1, hi);
}
function quick_sort(arr: number[]): number[] {
qs(arr, 0, arr.length - 1);
return arr;
}Recursion
Technique where a function calls itself to solve a problem by breaking it down into smaller, similar sub-problems.
1. Path Finding
type Point = {
x: number;
y: number;
};
const dir = [
[-1, 0],
[1, 0],
[0, -1],
[0, 1],
];
function walk(
maze: string[][],
wall: string,
curr: Point,
end: Point,
seen: boolean[][],
path: Point[],
): boolean {
// off the map
if (
curr.x < 0 ||
curr.x >= maze[0].length ||
curr.y < 0 ||
curr.y >= maze.length
) {
return false;
}
// on the wall
if (maze[curr.y][curr.x] === wall) {
return false;
}
// its the end
if (curr.x === end.x && curr.y === end.y) {
path.push(end);
return true;
}
// have we seen it before
if (seen[curr.y][curr.x]) {
return false;
}
// recurse steps
// pre
seen[curr.y][curr.x] = true;
path.push(curr);
// recurse
for (let i = 0; i < dir.length; i++) {
const [x, y] = dir[i];
if (
walk(
maze,
wall,
{
x: curr.x + x,
y: curr.y + y,
},
end,
seen,
path,
)
) {
return true;
}
}
// post
path.pop();
return false;
}
function solve(
maze: string[][],
wall: string,
start: Point,
end: Point,
): Point[] {
const seen: boolean[][] = [];
const path: Point[] = [];
for (let i = 0; i < maze.length; ++i) {
seen.push(new Array(maze[0].length).fill(false));
}
walk(maze, wall, start, end, seen, path);
return path;
}
const maze = [
["#", "#", "#", "#", "#", "#", "#", "#", "#", "#"],
["#", "S", " ", " ", "#", " ", " ", " ", " ", "#"],
["#", " ", "#", " ", "#", " ", "#", "#", " ", "#"],
["#", " ", "#", " ", " ", " ", " ", "#", " ", "#"],
["#", " ", "#", "#", "#", "#", " ", "#", " ", "#"],
["#", " ", " ", " ", " ", "#", " ", "#", " ", "#"],
["#", "#", "#", "#", " ", "#", " ", "#", " ", "#"],
["#", " ", " ", " ", " ", " ", " ", " ", " ", "#"],
["#", " ", "#", "#", "#", "#", "#", "#", "E", "#"],
["#", "#", "#", "#", "#", "#", "#", "#", "#", "#"],
];
const wall = "#";
const start: Point = { x: 1, y: 1 };
const end: Point = { x: 8, y: 8 };
const path = solve(maze, wall, start, end);