Array

Arrays are linear data structures that store multiple data types in a contiguous block of memory. Arrays are implemented in almost all low-level programming languages as the default way to store other data types. They provide fast access to elements but (with the exception of dynamic arrays) cannot have it’s size changed.

%%🖋 Edit in Excalidraw, and the dark exported image%%

Properties §

• A data structure with a set length
• Items are accessed via their index, which is a number that stores their location. They are usually 0-indexed, which means the index starts from 0 (instead of 1)
• They are static (a fixed size) (not to be confused with static in OOP). Specifically, their length cannot be changed once initialised.
• Items are added to arrays by overwriting previous value via index, or by swapping elements.

ADT Signature §

name: Array
import: element,int,bool
ops:
	newArray: int → Array
	append: Array x element x int → Array
	get: Array x int  → element
	isEmpty/isFull: Array → bool
	length: Array → int

Time Complexity §

The time complexity of an array varies depending on whether it is sorted or not.

Basic Operation: Array access

Assumptions:

• $A$ = The array itself
• $n$ = Elements in array
• $c$ = Capacity (storage of the array)
• $0\le i<c$: The index $i$ is a valid index.

To simplify analysis, we assume $c\gg n$, i.e. we would never need to resize the array.

Terminology

Here, I use INSERT and DELETE to mean inserting and deleting by overwriting. That is, we are not changing the capacity $c$ of the array.

Unsorted §

Operation	Operation Description	Worst Case (WC)	Average Case (AC)	Best Case (BC)	Case descriptions
GET	Access an element at index $i$	$\Theta (1)$	$\Theta (1)$	$\Theta (1)$	Basic operation
INSERT	Insert an element $x$ at index $i$, assuming there is space	$\Theta (1)$	$\Theta (1)$	$\Theta (1)$	WC ($i<n$): Increase $n$ by 1, and set $A[n]=A[i]$. Then insert the element by setting $A[i]=x$ BC ($i\ge n$): Inserting at index $n$ or higher involves no shifting
DELETE	Delete an element at index $i$ (via overwriting )	$\Theta (1)$	$\Theta (1)$	$\Theta (1)$	WC ($i<n$): Swap the last element $A[n-1]$ with $A[i]$, then decrement $n$ by 1 BC ($i=n-1$): Decrement $n$ by 1.
SEARCH	Searching for an element $x$ (assuming comparison is $O(1)$)	$\Theta (n)$	$\Theta (n)$	$\Theta (1)$	WC ($A[n-1]=x$ or $x$ not in array): Have to Linear search through array BC ($A[0]==x$): One comparison at the first element AC ($A[0\dots n-1]=x$): See average case derivation

Sorted §

Operation	Operation Description	Worst Case (WC)	Average Case (AC)	Best Case (BC)	Case descriptions
GET	Access an element at index $i$	$\Theta (1)$	$\Theta (1)$	$\Theta (1)$	Basic operation
INSERT	Insert an element $x$	$\Theta (n)$	$\Theta (n)$	$\Theta (1)$	WC ($x$ is not the largest element) : Various methods exist: 1. Modified binary search that returns the index of greatest element lesser than $x$, then shift all elements to right by 1, then insert. 2. Add to the end, then use insertion sort, which runs well when there are few unsorted elements. BC ($x$ is the largest element) : Insert at $A[n]$, increment $n$ after
DELETE	Delete an element at index $i$	$\Theta (n)$	$\Theta (n)$	$\Theta (1)$	WC ($i=0$): Need to shift $n-1$ elements to the right by one using element swaps. BC ($i=n-1$): Decrement $n$ by 1
SEARCH	Searching for an element $x$ (assuming comparison is $O(1)$)	$\Theta (\log (n))$	$\Theta (\log (n))$	$\Theta (1)$	See Binary Search Algorithm. Worst case: $\lfloor {\log }_2(n)\rfloor \in \Theta (\log (n))$, since it is equivalent to going to the lowermost level of a BST.

Implementation §

Most Programming Languages store arrays as references to memory locations. That is, if we create an array, simply trying to assign it to something else will copy the reference, not the value:

In Java §

#todo

{} is the syntax to for new int[] {3,3,5,5} creates a new unique array.