Array Data Structure

Pre-requisites

• Basic programming concepts (data types, variables, operators, conditionals, functions, loops etc) in any programming language

• High-level understanding of memory and complexity analysis

Introduction

An array is a data structure that can store several elements (same data type or different data types) in continuous blocks of memory.
Arrays are referred to as lists in certain programming languages (e.g python); their implementation is fundamentally the same

var myList = ["red", "blue", "green"]
var numbers = [1,2,3,4,5]

There are two types of arrays, dynamic and static arrays.

Static Array

A static array is a type of array that has fixed memory slots. The length of the array is defined at initialization and cannot be changed.

Complexity Analysis of static array operations

• Initialize => Creating a static array runs in O(N) linear space-time complexity

• Get (accessing) an element => O(1) constant time
  explanation: Every element is indexed in memory in equal memory (byte) size and is stored back-to-back sequentially

  The address of the first index is known, so the os multiplies the index of the array we are trying to access say myList[3] and multiplies it by the byte size (of fixed width) to get its location in memory instantly and returns its value.

• Set => to overwrite an element at a given index in constant time and space complexity. Reference explanation above

• Traverse => Iterating through an array takes linear time O(N) and constant space O(1). This usually includes inbuilt array methods like map, reduce etc (with the assumption that no other operation is added)

• Copy => This is a linear space-time operation as it will first traverse the existing array, make a copy, create new back-to-back memory extra slots and store the new copy. Slicing, splicing and similar methods involve copying operation

• Insert (different from set) = > Inserting values into an array will require "shifting" values in memory sometimes and there is no guarantee that there are available slots around to do the shifting operation. Hence the array is actually copied (linear time) but in constant space (because the old space is cleaned out).

Dynamic Arrays

An array type that can change in size. Default arrays in javascript and python are dynamic.

Under the hood, unlike static arrays that have fixed size allocated in memory, dynamic arrays are allocated twice the original size upon initialization. Note that this could be lesser or more depending on the programming language

Complexity analysis of dynamic arrays

Let's start with insertion, an operation that is better optimised in dynamic arrays

• Insert => this operation usually executes faster because more space was allocated in memory during initialization. Shifting (copying) will only happen during an insertion operation.
  This takes constant space-time complexity.
  Inserting at the beginning or middle still takes linear time though

• Pop=> removing from the end is in O(1) time and removing elements from the middle or beginning is in O(N) time complexity

• All other operations have the same complexity as a static array

Resources:

• Github repository that contains sample problems and solutions