Try to explain the Array with lockers

An array is a linear data structure that stores elements of the same type in contiguous memory space. We call the position of an element in the array the index of the element.

Array

Imagine a row of lockers in a school hallway. Each locker has a number on it, and inside each locker is a piece of paper with a name on it. The names are arranged in alphabetical order, so the first locker has the name “Alice” on it, the second locker has the name “Bob” on it, and so on.

Now, suppose you want to find out what name is on the third locker. You could open each locker one by one until you reach the third locker, but that would take a long time and be very inconvenient. Instead, you could use a clever trick. You could notice that the names are arranged in alphabetical order, so you know that the third locker must contain the name that comes after “Bob” in the alphabet. Therefore, you can simply look at the second locker to see what name is on it, and then you know what name is on the third locker.

This is basically how arrays work. Instead of lockers, we have a series of boxes that we can put things in. Instead of names, we have numbers or other pieces of data. Instead of looking at each box one by one, we can use a special formula to figure out where a particular piece of data is located in the array.

For example, suppose we have an array of numbers, and we want to find out what number is in the fifth box. We can use the formula box number = (index - 1) * box size to figure out where the fifth box is located. If the box size is 10, then the fifth box is located at index 40.

Initializing arrays

• Initializing an array without initial values:

Imagine you have a row of lockers in a locker room, and you want to initialize an array to represent the contents of those lockers. However, you don’t know what each locker will hold yet. In this case, you can initialize the array without specifying any initial values.

Here’s an example in JavaScript:

let lockers = []; // initialize an empty array

In this example, the locker array is created with no elements. You can add elements to the array later using the push() method.

• Initializing an array with specified initial values:

Now imagine you have a row of lockers, and you want to initialize an array to represent the contents of those lockers. You know exactly what each locker will hold, so you can specify the initial values when creating the array.

Here’s an example in JavaScript:

let lockers = ['socks', 'shoes', 'jacket']; // initialize an array with specific values
var arr = new Array(5).fill(0); // initialize an array with 0 value

In this example, the lockers array is created with three elements: ‘socks’, ‘shoes’, and ‘jacket’. These elements are assigned to the first, second, and third indices of the array, respectively.

Accessing elements

To access an element in an array, we need to know its index. The index is like a key that unlocks the locker containing the element we want to access. Once we have the key (or index), we can use it to find the corresponding locker (or memory location) where the element is stored.

The formula shown in the figure above helps us determine the memory address of an element in an array. It takes the base address of the array (which is the memory address of the first element) and adds an offset to it, based on the index of the element we want to access. The offset is calculated by multiplying the index by the size of each element in the array.

For example, let’s say we have an array of integers, and we want to access the element at index 5. The base address of the array is 1000, and each integer takes up 4 bytes of memory. To access the element at index 5, we would calculate the memory address as follows:

Memory Address = Base Address + (Index * Element Size)
Memory Address = 1000 + (5 * 4)
Memory Address = 1000 + 20
Memory Address = 1020

Therefore, the memory address of the element at index 5 is 1020.

/* Random access */
function randomAccess(nums) { // Choose a random value in [0, nums.length] const random_index = Math.floor(Math.random() * nums.length); // Get and return a random value const random_num = nums[random_index]; return random_num;
}

Inserting elements

Let’s say you want to insert a new locker in the middle of the row. To do this, you would need to shift all the lockers after the new locker one position back to make room for it.

However, this means that the last locker in the row will now be pushed out of the row, as there is no more space to fit it. This is similar to how inserting an element in an array works, as the fixed length of the array means that there is no extra space to accommodate new elements.

function insert(nums, num, index) { for (let i = nums.length - 1; i > index; i--) { nums[i] = nums[i - 1]; } nums[index] = num;
}

Deleting elements

Delete an element at the index i, all elements following the index i must be moved forward by one position. After deletion, the former last element becomes “meaningless,” hence requiring no specific modification.

function remove(nums, index) { for (let i = index; i < nums.length - 1; i++) { nums[i] = nums[i + 1]; }
}

Traversing arrays

We can traverse an array either by using indices or by directly iterating over each element

function traverse(nums) { let count = 0; for (let i = 0; i < nums.length; i++) { count += nums[i]; } for (const num of nums) { count += num; }
}

Finding elements

Just like how you would need to check each locker to find the one you’re looking for, you would need to check each element in an array to find the one you’re looking for. This process is called “linear search” because it involves checking each element one by one, just like how you would check each locker in a row

function find(nums, target) { for (let i = 0; i < nums.length; i++) { if (nums[i] === target) return i; } return -1;
}

Expanding arrays

If you want to add more lockers to the row, you can’t just magically create more lockers out of thin air. Instead, you need to build a bigger locker room with more lockers.

Similarly, when you need to expand an array, you can’t just magically increase its size. Instead, you need to create a new array with more capacity and then copy the elements from the old array to the new one. This process is called “resizing” the array, and it can be time-consuming for large arrays.

In programming languages, the length of an array is often immutable, meaning it can’t be changed. This is because arrays are designed to be fixed-size data structures, and changing their size can lead to unexpected behavior or errors. To expand an array, you need to create a new array with more capacity and then copy the elements from the old array to the new one. This process has a time complexity of O(n), meaning it can be slow for large arrays.

function extend(nums, enlarge) { const res = new Array(nums.length + enlarge).fill(0); for (let i = 0; i < nums.length; i++) { res[i] = nums[i]; } return res;
}

Advantages and limitations of arrays

Arrays are stored in contiguous memory spaces and consist of elements of the same type.

• High space efficiency: Arrays allocate a contiguous block of memory for data, eliminating the need for additional structural overhead.
• Support for random access: Arrays allow O(1) time access to any element.
• Cache locality: When accessing array elements, the computer not only loads them but also caches the surrounding data, utilizing high-speed cache to enhance subsequent operation speeds.

However, continuous space storage is a double-edged sword, with the following limitations:

• Low efficiency in insertion and deletion: As arrays accumulate many elements, inserting or deleting elements requires shifting a large number of elements.
• Fixed length: The length of an array is fixed after initialization. Expanding an array requires copying all data to a new array, incurring significant costs.
• Space wastage: If the allocated array size exceeds what is necessary, the extra space is wasted.

Ref