Array Data Structure Code Implementations
Production-ready Array Data Structure data structure implementations in C++, Python, Java, and JavaScript on AntInLoop.
Study Array Data Structure Guide ยท Launch Visualizer
CPP Implementation
class Array {
constructor(initialCapacity = 0) {
this.data = new Array(initialCapacity);
this.capacity = initialCapacity;
this.size = 0;
}
// Create from existing array
static from(arr) {
const newArray = new Array(arr.length);
for (let i = 0; i < arr.length; i++) {
newArray.push(arr[i]);
}
return newArray;
}
// Resize internal array
_resize(newCapacity) {
const newData = new Array(newCapacity);
for (let i = 0; i < this.size; i++) {
newData[i] = this.data[i];
}
this.data = newData;
this.capacity = newCapacity;
}
// Element access
get(index) {
if (index < 0 || index >= this.size) {
throw new Error("Index out of bounds");
}
return this.data[index];
}
set(index, value) {
if (index < 0 || index >= this.size) {
throw new Error("Index out of bounds");
}
this.data[index] = value;
}
front() {
if (this.size === 0) throw new Error("Array is empty");
return this.data[0];
}
back() {
if (this.size === 0) throw new Error("Array is empty");
return this.data[this.size - 1];
}
// Modifiers
push(value) {
if (this.size >= this.capacity) {
this._resize(this.capacity === 0 ? 1 : this.capacity * 2);
}
this.data[this.size++] = value;
}
pop() {
if (this.size === 0) {
throw new Error("Array is empty");
}
const value = this.data[--this.size];
this.data[this.size] = undefined; // Clear reference
return value;
}
insert(index, value) {
if (index < 0 || index > this.size) {
throw new Error("Index out of bounds");
}
if (this.size >= this.capacity) {
this._resize(this.capacity === 0 ? 1 : this.capacity * 2);
}
// Shift elements to the right
for (let i = this.size; i > index; i--) {
this.data[i] = this.data[i - 1];
}
this.data[index] = value;
this.size++;
}
erase(index) {
if (index < 0 || index >= this.size) {
throw new Error("Index out of bounds");
}
// Shift elements to the left
for (let i = index; i < this.size - 1; i++) {
this.data[i] = this.data[i + 1];
}
this.size--;
this.data[this.size] = undefined; // Clear reference
}
clear() {
for (let i = 0; i < this.size; i++) {
this.data[i] = undefined;
}
this.size = 0;
}
// Capacity
getSize() {
return this.size;
}
getCapacity() {
return this.capacity;
}
isEmpty() {
return this.size === 0;
}
// Utility methods
toArray() {
return this.data.slice(0, this.size);
}
toString() {
return `[${this.toArray().join(", ")}]`;
}
// Iterator support
*[Symbol.iterator]() {
for (let i = 0; i < this.size; i++) {
yield this.data[i];
}
}
}
// CPU Cache demonstration
function demonstrateCpuCaching() {
const ARRAY_SIZE = 1_000_000;
const arr = Array.from({ length: ARRAY_SIZE }, (_, i) => i);
console.log("JavaScript CPU Caching Demo:");
// Sequential access (cache-friendly)
const start1 = performance.now();
let sum1 = 0;
for (let i = 0; i < ARRAY_SIZE; i++) {
sum1 += arr[i];
}
const end1 = performance.now();
// Random access (cache-unfriendly)
const start2 = performance.now();
let sum2 = 0;
for (let i = 0; i < ARRAY_SIZE; i++) {
const randomIndex = Math.floor(Math.random() * ARRAY_SIZE);
sum2 += arr[randomIndex];
}
const end2 = performance.now();
const sequentialTime = end1 - start1;
const randomTime = end2 - start2;
console.log(`Sequential access time: ${sequentialTime.toFixed(2)}ms`);
console.log(`Random access time: ${randomTime.toFixed(2)}ms`);
console.log(`Performance ratio: ${(randomTime / sequentialTime).toFixed(2)}x slower`);
}
JAVA Implementation
// CacheArray.java
// A cache-friendly dynamic array for Java (primitive-generic via int[] here)
// You can template for other primitives (double, long, etc.)
public class CacheArray {
private int[] data;
private int size;
public CacheArray() {
this(16);
}
public CacheArray(int initialCapacity) {
if (initialCapacity < 1) initialCapacity = 1;
data = new int[initialCapacity];
size = 0;
}
public int size() {
return size;
}
public int capacity() {
return data.length;
}
public boolean isEmpty() {
return size == 0;
}
public void clear() {
size = 0;
}
public void add(int value) {
if (size >= data.length) grow(size + 1);
data[size++] = value;
}
public int get(int index) {
if (index < 0 || index >= size) throw new IndexOutOfBoundsException();
return data[index];
}
public void set(int index, int value) {
if (index < 0 || index >= size) throw new IndexOutOfBoundsException();
data[index] = value;
}
public void removeLast() {
if (size > 0) size--;
}
private void grow(int desired) {
int newCap = Math.max(desired, (int)(data.length * 1.5));
int[] newData = new int[newCap];
System.arraycopy(data, 0, newData, 0, size);
data = newData;
}
// Block iteration: process array in contiguous blocks
public void forEachBlock(int blockSize, java.util.function.IntConsumer blockFunc) {
if (blockSize <= 0) throw new IllegalArgumentException();
for (int i = 0; i < size; i += blockSize) {
int end = Math.min(i + blockSize, size);
for (int j = i; j < end; j++) {
blockFunc.accept(data[j]);
}
}
}
// Expose raw backing array (read-only!)
public int[] rawArray() {
return data;
}
}
JAVASCRIPT Implementation
class Array {
constructor(initialCapacity = 0) {
this.data = new Array(initialCapacity);
this.capacity = initialCapacity;
this.size = 0;
}
// Create from existing array
static from(arr) {
const newArray = new Array(arr.length);
for (let i = 0; i < arr.length; i++) {
newArray.push(arr[i]);
}
return newArray;
}
// Resize internal array
_resize(newCapacity) {
const newData = new Array(newCapacity);
for (let i = 0; i < this.size; i++) {
newData[i] = this.data[i];
}
this.data = newData;
this.capacity = newCapacity;
}
// Element access
get(index) {
if (index < 0 || index >= this.size) {
throw new Error('Index out of bounds');
}
return this.data[index];
}
set(index, value) {
if (index < 0 || index >= this.size) {
throw new Error('Index out of bounds');
}
this.data[index] = value;
}
front() {
if (this.size === 0) throw new Error('Array is empty');
return this.data[0];
}
back() {
if (this.size === 0) throw new Error('Array is empty');
return this.data[this.size - 1];
}
// Modifiers
push(value) {
if (this.size >= this.capacity) {
this._resize(this.capacity === 0 ? 1 : this.capacity * 2);
}
this.data[this.size++] = value;
}
pop() {
if (this.size === 0) {
throw new Error('Array is empty');
}
const value = this.data[--this.size];
this.data[this.size] = undefined; // Clear reference
return value;
}
insert(index, value) {
if (index < 0 || index > this.size) {
throw new Error('Index out of bounds');
}
if (this.size >= this.capacity) {
this._resize(this.capacity === 0 ? 1 : this.capacity * 2);
}
// Shift elements to the right
for (let i = this.size; i > index; i--) {
this.data[i] = this.data[i - 1];
}
this.data[index] = value;
this.size++;
}
erase(index) {
if (index < 0 || index >= this.size) {
throw new Error('Index out of bounds');
}
// Shift elements to the left
for (let i = index; i < this.size - 1; i++) {
this.data[i] = this.data[i + 1];
}
this.size--;
this.data[this.size] = undefined; // Clear reference
}
clear() {
for (let i = 0; i < this.size; i++) {
this.data[i] = undefined;
}
this.size = 0;
}
// Capacity
getSize() { return this.size; }
getCapacity() { return this.capacity; }
isEmpty() { return this.size === 0; }
// Utility methods
toArray() {
return this.data.slice(0, this.size);
}
toString() {
return `[${this.toArray().join(', ')}]`;
}
// Iterator support
*[Symbol.iterator]() {
for (let i = 0; i < this.size; i++) {
yield this.data[i];
}
}
}
// CPU Cache demonstration
function demonstrateCpuCaching() {
const ARRAY_SIZE = 1000000;
const arr = new Array(ARRAY_SIZE).map((_, i) => i);
console.log('JavaScript CPU Caching Demo:');
// Sequential access (cache-friendly)
const start1 = performance.now();
let sum1 = 0;
for (let i = 0; i < ARRAY_SIZE; i++) {
sum1 += arr[i];
}
const end1 = performance.now();
// Random access (cache-unfriendly)
const start2 = performance.now();
let sum2 = 0;
for (let i = 0; i < ARRAY_SIZE; i++) {
const randomIndex = Math.floor(Math.random() * ARRAY_SIZE);
sum2 += arr[randomIndex];
}
const end2 = performance.now();
const sequentialTime = end1 - start1;
const randomTime = end2 - start2;
console.log(`Sequential access time: ${sequentialTime.toFixed(2)}ms`);
console.log(`Random access time: ${randomTime.toFixed(2)}ms`);
console.log(`Performance ratio: ${(randomTime / sequentialTime).toFixed(2)}x slower`);
}PYTHON Implementation
import time
import random
from typing import TypeVar, Generic, Iterator
T = TypeVar('T')
class Array(Generic[T]):
def __init__(self, initial_capacity: int = 0):
self._data = [None] * initial_capacity
self._capacity = initial_capacity
self._size = 0
def _resize(self, new_capacity: int) -> None:
"""Resize the internal array to new capacity"""
new_data = [None] * new_capacity
for i in range(self._size):
new_data[i] = self._data[i]
self._data = new_data
self._capacity = new_capacity
# Element access
def __getitem__(self, index: int) -> T:
if not 0 <= index < self._size:
raise IndexError(f"Index {index} out of range [0, {self._size})")
return self._data[index]
def __setitem__(self, index: int, value: T) -> None:
if not 0 <= index < self._size:
raise IndexError(f"Index {index} out of range [0, {self._size})")
self._data[index] = value
def get(self, index: int) -> T:
return self[index]
def set(self, index: int, value: T) -> None:
self[index] = value
def front(self) -> T:
if self._size == 0:
raise IndexError("Array is empty")
return self._data[0]
def back(self) -> T:
if self._size == 0:
raise IndexError("Array is empty")
return self._data[self._size - 1]
# Modifiers
def push(self, value: T) -> None:
if self._size >= self._capacity:
new_capacity = 1 if self._capacity == 0 else self._capacity * 2
self._resize(new_capacity)
self._data[self._size] = value
self._size += 1
def pop(self) -> T:
if self._size == 0:
raise IndexError("Pop from empty array")
self._size -= 1
value = self._data[self._size]
self._data[self._size] = None # Clear reference
return value
def insert(self, index: int, value: T) -> None:
if not 0 <= index <= self._size:
raise IndexError(f"Index {index} out of range [0, {self._size}]")
if self._size >= self._capacity:
new_capacity = 1 if self._capacity == 0 else self._capacity * 2
self._resize(new_capacity)
# Shift elements to the right
for i in range(self._size, index, -1):
self._data[i] = self._data[i - 1]
self._data[index] = value
self._size += 1
def erase(self, index: int) -> None:
if not 0 <= index < self._size:
raise IndexError(f"Index {index} out of range [0, {self._size})")
# Shift elements to the left
for i in range(index, self._size - 1):
self._data[i] = self._data[i + 1]
self._size -= 1
self._data[self._size] = None # Clear reference
def clear(self) -> None:
for i in range(self._size):
self._data[i] = None
self._size = 0
# Capacity
def size(self) -> int:
return self._size
def capacity(self) -> int:
return self._capacity
def is_empty(self) -> bool:
return self._size == 0
# Special methods
def __len__(self) -> int:
return self._size
def __str__(self) -> str:
elements = [str(self._data[i]) for i in range(self._size)]
return f"[{', '.join(elements)}]"
def __repr__(self) -> str:
return f"Array({self.__str__()})"
def __iter__(self) -> Iterator[T]:
for i in range(self._size):
yield self._data[i]
# Utility methods
def to_list(self) -> list:
return [self._data[i] for i in range(self._size)]
@classmethod
def from_list(cls, lst: list) -> 'Array':
arr = cls(len(lst))
for item in lst:
arr.push(item)
return arr
# CPU Cache demonstration
def demonstrate_cpu_caching():
ARRAY_SIZE = 1000000
arr = list(range(ARRAY_SIZE))
print("Python CPU Caching Demo:")
# Sequential access (cache-friendly)
start1 = time.perf_counter()
sum1 = 0
for i in range(ARRAY_SIZE):
sum1 += arr[i]
end1 = time.perf_counter()
# Random access (cache-unfriendly)
start2 = time.perf_counter()
sum2 = 0
for i in range(ARRAY_SIZE):
random_index = random.randint(0, ARRAY_SIZE - 1)
sum2 += arr[random_index]
end2 = time.perf_counter()
sequential_time = (end1 - start1) * 1000 # Convert to ms
random_time = (end2 - start2) * 1000
print(f"Sequential access time: {sequential_time:.2f}ms")
print(f"Random access time: {random_time:.2f}ms")
print(f"Performance ratio: {random_time / sequential_time:.2f}x slower")
# Example usage
if __name__ == "__main__":
# Create and test array
arr = Array[int]()
for i in range(5):
arr.push(i * 10)
print(f"Array: {arr}")
print(f"Size: {arr.size()}, Capacity: {arr.capacity()}")
# Demonstrate CPU caching
demonstrate_cpu_caching()