Array

An array is a collection of items of same data type stored at contiguous memory locations.

• Index: In an array, elements are identified by their indexes. Array index starts from 0.

• element: Elements are items stored in an array and can be accessed by their index.

• length: The length of an array is determined by the number of elements it can contain.

Types of Arrays

Static arrays:

• The size or number of elements in static arrays is fixed. (After an array is created and memory space allocated, the size of the array cannot be changed.)

• The array's content can be modified, but the memory space allocated to it remains constant.

Dynamic arrays:

• The size or number of elements in a dynamic array can change. (After an array is created, the size of the array can be changed – the array size can grow or shrink.)

• Dynamic arrays allow elements to be added and removed at the runtime. (The size of the dynamic array can be modified during the operations performed on it.)

Types of arrays:

• One-dimensional array: You can imagine a 1d array as a row, where elements are stored one after another.

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

class MyArray {
    constructor() {
        this.length = 0;
        this.data = {};
    }

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

    all() {
        const allElements = [];
        for (let i = 0; i < this.length; i++) {
            allElements.push(this.data[i]);
        }
        return allElements;
    }

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

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

    delete(index) {
        const item = this.data[index];
        for (let i = index; i < this.length - 1; i++) {
            this.data[i] = this.data[i + 1];
        };
        delete this.data[this.length - 1];
        this.length--;
        return item;
    }
}

const myNewArray = new MyArray();

myNewArray.push('hi');

myNewArray.push('you');

myNewArray.push('!');

myNewArray.pop();

myNewArray.delete(1);

console.log(myNewArray.all());

• Two-dimensional array: arrays can be considered as an array of arrays or as a matrix consisting of rows and columns.

  

let twoDimArray = [
  [1, 2, 3],
  [4, 5, 6],
  [7, 8, 9]
];

• Three-dimensional array: array contains three dimensions, so it can be considered an array of two-dimensional arrays.

  

let threeDimArray = [
  [
    [1, 2],
    [3, 4]
  ],
  [
    [5, 6],
    [7, 8]
  ],
  [
    [9, 10],
    [11, 12]
  ]
];

Operations:

• Traversal: Traverse through the elements of an array.

• Insertion: Inserting a new element in an array.

• Deletion: Deleting element from the array.

• Searching: Search for an element in the array.

• Sorting: Maintaining the order of elements in the array.

Function	Big O
push	O(1)
pop	O(1)
shift	O(n)
unshift	O(n)
concat	O(n)
slice	O(n)
splice	O(n)
forEach	O(n)
map	O(n)
filter	O(n)
reduce	O(n)
find	O(n)
findIndex	O(n)
indexOf	O(n)
includes	O(n)
every	O(n)
some	O(n)
sort	O(n)
reverse	O(n)
join	O(n)

Applications:

• They are used in the implementation of other data structures such as array lists, heaps, hash tables, vectors, and matrices.

• Database records are usually implemented as arrays.

• It is used in lookup tables by computer.

• It is used for different sorting algorithms such as bubble sort insertion sort, merge sort, and quick sort.

Advantages:

• Allow random access to elements. This makes accessing elements by position faster.

• Have better cache locality which makes a pretty big difference in performance.

• Represent multiple data items of the same type using a single name.

• Store multiple data of similar types with the same name.

• Array data structures are used to implement the other data structures like linked lists, stacks, queues, trees, graphs, etc.

Disadvantages:

• As arrays have a fixed size, once the memory is allocated to them, it cannot be increased or decreased, making it impossible to store extra data if required. An array of fixed size is referred to as a static array.

• Allocating less memory than required to an array leads to loss of data. An array is homogeneous in nature so, a single array cannot store values of different data types.

• Arrays store data in contiguous memory locations, which makes deletion and insertion very difficult to implement. This problem is overcome by implementing linked lists, which allow elements to be accessed sequentially.

Time Complexity

Algorithm	Average case	Worst case
Access	O(1)	O(1)
Search	O(n)	O(n)
Insertion	O(n)	O(n)
Deletion	O(n)	O(n)

Arrays Good at 😀:

• Fast lookups

• Fast push/pop

• Ordered

Arrays Bad at 😒:

• Slow inserts

• Slow deletes

• Fixed size* (if using static array)