Data Structures. Array

1 ноября 2023 г.

This is a short expanded summary of the section about arrays in the book Computer Science Guide by William Springer.

An array is a collection of elements indexed by a key. Elements are stored sequentially.

• The key is represented as an offset relative to the starting position in memory. The first element is at zero distance from the start, so it has index 0.
• Array elements are located in contiguous memory regions, which makes iteration faster (due to fewer cache misses).
• Each array element occupies the same amount of memory, and the entire array takes O(n) space.

Arrays are useful when the number of elements is known in advance.

Based on arrays, we can build lists, stacks, heaps, priority queues (often implemented using heaps), and hash tables.

Insertion and deletion of array elements take O(n) time because elements must be shifted.

Accessing or updating any element takes constant time.

1const array = ['cat', 'dog', 'rabbit', 'apple'];

JavaScript provides built-in methods and properties:

1) Add an element to the end of an array

1array.push(`purple`); //[ 'cat', 'dog', 'rabbit', 'apple', 'purple' ]

2) Removing the Last Element from an Array

1array.pop(); //[ 'cat', 'dog', 'rabbit' ]

3) Adding an Element to the Beginning of an Array

1array.unshift('green'); //[ 'green', 'cat', 'dog', 'rabbit', 'apple' ]

4) Removing an Element from the Beginning of an Array

1array.shift() //[ 'dog', 'rabbit', 'apple' ]

This operation, as well as the previous one, requires traversing all the remaining elements in the array and updating their indices.

5) Array Iteration

1array.forEach((item, index, array) => {
2    console.log(item, index, array);
3});

6) Getting the Length of an Array

1array.length // 4

7) Getting the Index of an Element

1array.indexOf("rabbit") //2

8) Adding/Removing One or More Elements by Index

1// Removes 0 elements at index 2 and inserts "yellow"
2array.splice(2, 0, "yellow") // [ 'cat', 'dog', 'yellow', 'rabbit', 'apple' ]
3
4// Replaces 1 element at index 3 with the element "jam"
5array.splice(3, 1, "jam") // [ 'cat', 'dog', 'yellow', 'jam', 'apple' ]
6
7// Removes the element at index 2
8array.splice(2, 1) // [ 'cat', 'dog', 'jam', 'apple' ]
9
10// Removes elements at indexes 2 and 3
11array.splice(1, 2) // [ 'cat', 'apple' ]