← Index

Linear Structures

Array

Contiguous, indexed slots — instant access, expensive middle inserts.

What it is

An array stores elements in contiguous memory, each reachable by index in O(1) because the engine can jump straight to address + (index × size). The tradeoff shows up when you insert or remove anywhere except the end: everything after has to shift, which is O(n).

Real-world examples

• A row of numbered parking spots — you can walk straight to spot #42, but squeezing a new car into spot #10 means every car after it has to shift down one.
• An egg carton: grabbing egg 5 is instant, but inserting a new egg in the middle means shuffling the rest.

Where you've probably used this already

• Every time you use .map(), .filter(), or index into a JS array — this is the default list type in almost every language.
• Noticing .unshift() or .splice() in a loop is slow on a large array — that's the O(n) shift cost showing up.
• Choosing a fixed-size typed array (Int32Array) for perf-sensitive code like canvas/audio processing.

Complexity

Code

// Array — contiguous, indexed slots in memory.
// Reading by index is instant; inserting/removing in the middle is not.

const fruits = ["apple", "banana", "cherry"];

// Access by index — O(1), it's just memory_address + (index * size)
console.log("Access index 1:", fruits[1]); // "banana"

// Push/pop at the END — O(1), no shifting needed
fruits.push("date");
console.log("After push:", fruits); // ["apple","banana","cherry","date"]
fruits.pop();
console.log("After pop:", fruits); // ["apple","banana","cherry"]

// Insert/remove at the START or MIDDLE — O(n), everything after has to shift
fruits.unshift("avocado"); // shifts every element right by 1
console.log("After unshift:", fruits); // ["avocado","apple","banana","cherry"]
fruits.splice(1, 1); // remove 1 item at index 1, shifts everything left
console.log("After splice remove:", fruits); // ["avocado","banana","cherry"]

// Search by value — O(n), no shortcuts, has to check each element
console.log("Index of banana:", fruits.indexOf("banana")); // 1

// --- Implementing push/pop/get manually (what the engine does under the hood) ---
class MyArray {
  constructor() {
    this.length = 0;
    this.data = {};
  }

  get(index) {
    return this.data[index];
  }

  push(item) {
    this.data[this.length] = item;
    this.length++;
    return this.length;
  }

  pop() {
    if (this.length === 0) return undefined;
    const lastItem = this.data[this.length - 1];
    delete this.data[this.length - 1];
    this.length--;
    return lastItem;
  }
}

const myArr = new MyArray();
myArr.push("x");
myArr.push("y");
console.log("MyArray get(0):", myArr.get(0)); // "x"
console.log("MyArray pop():", myArr.pop());   // "y"