🗃️Arrays

Array - The foundation of storing data

What is an Array?

💡An array is a linear collection of data values that are accessible at numbered indices, starting at index 0.

How The Array Is Stored In The Memory?

Contiguous Allocation:

• Array elements are stored consecutively in memory, one after the other, starting from a specific memory address.

• This allows for efficient random access to elements using their indices.

Memory Size:

• The total memory occupied by an array is the product of the number of elements and the size of each element.

• For example, an array of 10 integers (each 4 bytes) would occupy 40 bytes of memory.

Memory Allocation:

The location where an array is stored in memory depends on how it's declared:

• Global or static arrays: Typically stored in a data segment, a fixed region of memory reserved for static data.

• Local arrays within functions: Usually allocated on the stack, a LIFO (last-in, first-out) structure is used for function calls and local variables.

• Dynamically allocated arrays (using malloc in C or new in C++): Stored on the heap, a region of memory for dynamic memory allocation.

Accessing Elements:

• The array has a base address, which points to the first element's memory location.

• To access any element, the computer calculates its offset from the base address using its index.

Accessing an array element involves:

• Calculating the memory address: Base address of the array + (index * size of each element)

• Reading or writing data at that memory address.

Example:

Consider an integer array:

let array = [1, 2, 3, 4, 5];

If the base address of the array is 0x1000:

• numbers[0] is at address 0x1000 (1st element)

• numbers[2] is at address 0x1008 (3rd element, offset by 2 * 4 bytes)

Multidimensional Arrays:

• Stored in row-major order (elements of each row are stored consecutively, followed by elements of the next row).

How array is stored in the memory?

Big O Notation of Array Operations

Operations	Time Complexity
Accessing at a given index	$O(1)$
Updating at a given index	$O(1)$
Inserting at the beginning	$O(n)$
Inserting in the middle	$O(n)$
Inserting at the end	$O(1)$ for dynamic array $O(n)$ for static array
Removing at the beginning	$O(n)$
Removing in the middle	$O(n)$
Removing at the end	$O(1)$
Copying the array	$O(n)$

Implementation of Array In JavaScript

Here's an example implementation of common array operations in JavaScript:

Creating an array:

// Array literal syntax
const myArray = [1, "hello", true];

// Using the Array constructor
const myArray2 = new Array(3); // Creates an empty array with a length of 3

// Filling an array with a specific value
const filledArray = Array(5).fill(0); // Creates an array of 5 zeros

Accessing elements:

const firstElement = myArray[0]; // firstElement will be 1
const lastElement = myArray[myArray.length - 1]; // lastElement will be "true"

// Accessing using negative indexes (starts from the end)
const secondToLast = myArray[-2]; // secondToLast will be "hello"

Adding elements:

// Push adds to the end
myArray.push(5); // Adds 5 to the end of the array

// Unshift adds to the beginning
myArray.unshift(0); // Adds 0 to the beginning of the array

// Splice adds/removes elements at specific positions
myArray.splice(2, 1, "world"); // Replaces element at index 2 with "world"

Removing elements:

// Pop removes from the end
const removedElement = myArray.pop(); // removedElement will be "true"

// Shift removes from the beginning
const firstRemoved = myArray.shift(); // firstRemoved will be 0

// Splice removes elements at specific positions
myArray.splice(1, 2); // Removes elements at indexes 1 and 2 (inclusive)

Iterating over elements:

// For loop with index
for (let i = 0; i < myArray.length; i++) {
  console.log(myArray[i]);
}

// For...of loop for values
for (const element of myArray) {
  console.log(element);
}

// Array.forEach method
myArray.forEach((element) => {
  console.log(element);
});

Searching for an element:

// indexOf returns the index of the first occurrence, or -1 if not found
const index = myArray.indexOf("hello"); // index will be 1

// includes checks if an element exists (true/false)
const found = myArray.includes("world"); // found will be false

Sorting elements:

// Sort method sorts the array in ascending order
myArray.sort(); // Modifies the original array

// Using comparison function for custom sorting
myArray.sort((a, b) => b - a); // Sorts in descending order